Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 437 for “"succinct"”.
-
Succinct Indexes
This thesis defines and designs succinct indexes for several abstract data types (ADTs). The concept is to design auxiliary data structures that ideally occupy asymptotically less space than the information-theoretic lower bound on the space required to encode the given data, and support an …
-
Succinct Data Structures
… In the case of bioinformatics, understanding succinct representations of DNA sequences could lead to a more fundamental understanding of the nature of our own "data stream," perhaps even giving hints on secondary and tertiary structure, gene evolution, and other important topics.In this …
-
Finding Succinct Representations For Clusters
… Davidson et al., and Sambaturu et al., based on succinct representations of clusters. Given a set of objects S, a partition of S (into clusters), and a universe T of descriptors such that each element in S is associated with a subset of descriptors, the goal is to find a representative set of …
-
Succinct Representation of Trees and Graphs
In this thesis, we study succinct representations of trees and graphs. A succinct representation of a combinatorial object is a space efficient representation that supports a reasonable set of operations and queries on the object in constant or near constant time on the RAM with logarithmic word …
-
Succinct Data Structures for Chordal Graphs
… of 1 in O(1) time. We study the problem of succinctly storing a static chordal graph to answer adjacency, degree, neighbourhood and shortest path queries. Let G be a chordal graph with n vertices. We design a data structure using the information theoretic minimal n^2/4 + o(n^2) bits of space …
-
Xiezhi: Toward Succinct Proofs of Solvency
… setting (secp256k1) and more ideal settings for succinctness (e.g., pairing-based cryptography) with a novel mapping approach. Finally, we discuss how to adapt the protocol to the concrete parameters of bls12-381 (which is relevant because the bit-decomposition of all user balances will exceed …
-
Succinct function representations for simulation and verification
… represent Boolean functions exponentially more succinctly than BDDs, and double-exponentially more succinctly than decision trees, in the best case. They have the potential to permit applications to (i) execute much faster, and (ii) handle much larger problem instances than has been possible …
-
On the Succinct Representation of Equivalence Classes
Given a set of n elements that are partitioned into equivalence classes, we study the problem of assigning unique labels to these elements in order to support the query that asks whether the elements corresponding to two given labels belong to the same equivalence class. This problem has been …
-
Inducing succinct rules in machine learning problems
Machine Learning techniques, in particular induction algorithms, have been applied to the field of expert systems development in an effort to overcome the knowledge acquisition bottleneck. Many different induction algorithms have been developed. These utilise a number of different knowledge …
-
Succinct publicly auditable MPC with universal setup
… robust MPC that supports fast verification, succinct proof size with one time universal, and updatable setup. Importantly,we provide auditability without significantly compromising the performance of the underlying Shamir secret shared MPC protocol, i.e, adding auditability only incurs a …
-
Succinct and Compact Data Structures for Intersection Graphs
… we first resolve an open problem with regards to succinctly representing ordinal trees that is able to convert between the index of a node in a depth-first traversal (i.e. pre-order) and in a breadth-first traversal (i.e. level-order) of the tree. Using this, we are able to augment previous …
-
Succinct non-interactive arguments for bounded depth computations
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms
-
Succinct Σ-Proofs of Partial Knowledge from Boring Assumptions
Often the correctness of a piece of information, is not easily verified; Alice holds an encryption of Bob's secret and in the absence of Bob's key she must trust that Bob shared the correct encryption with her. In a cryptographic setting it is assumed that some, possibly all, parties participating …
-
Universal and succinct source coding of deep neural networks
Deep neural networks have shown incredible performance for inference tasks in a variety of domains. Unfortunately, most current deep networks are enormous cloud-based structures that require significant storage space, which limits scaling of deep learning as a service (DLaaS) and use for on-device …
-
From spatio-temporal trajectories to succinct and semantically meaningful patterns
… four challenges that hinder the discovery of succinct and semantically meaningful trajectory patterns: spatial uncertainty, trajectory complexity, pattern complexity, and semantic meaning. The first challenge, spatial uncertainty, is present in many GPS trajectories. As the global positioning …
-
Succinct Data Structures for Parameterized Pattern Matching and Related Problems
Let T be a fixed text-string of length n and P be a varying pattern-string of length |P| <= n. Both T and P contain characters from a totally ordered alphabet Sigma of size sigma <= n. Suffix tree is the ubiquitous data structure for answering a pattern matching query: report all the positions i in …
-
A Survey of Zero-Knowledge Succinct Non-Interactive Arguments with preprocessing
Σε αυτή τη διπλωματική εργασία μελετάμε την έννοια των μηδενικής-γνώσεις συνοπτικών μη-διαλογικών επιχειρημάτων (zkSNARGs) με προεπεξεργασία. Δοθέντος ενός αριθμητικού κυκλώματος C, δημόσιας εισόδου x, ιδιωτικής εισόδου w και δημόσιας εξόδου y, ένα zkSNARG αποτελεί ένα πρωτόκολλο το οποίο επιτρέπει …
-
REGULAR LANGUAGES: TO FINITE AUTOMATA AND BEYOND - SUCCINCT DESCRIPTIONS AND OPTIMAL SIMULATIONS
È noto che i linguaggi regolari — o di tipo 3 — sono equivalenti agli automi a stati finiti. Tuttavia, in letteratura sono presenti altre caratterizzazioni di questa classe di linguaggi, in termini di modelli riconoscitori e grammatiche. Per esempio, limitando le risorse computazionali di modelli …
-
Space Efficient Data Structures and Algorithms in the Word-RAM Model
… topic. One way of reducing storage is using succinct and compact data structures which maintain the data in compressed form with extra data structures over it in a way that allows efficient access and query of the data. In this thesis we study space-efficient data structures for various …
Page 1 of 22