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 10 of 10 for “"Randomness extractors"”.
-
Randomness extractors for independent sources and applications
… are impossible to solve without access to randomness. In computer science, access to randomness is usually modeled as access to a string of uncorrelated uniformly random bits. Although it is widely believed that many physical phenomena are inherently unpredictable, there is a gap between …
-
Expander graphs, randomness extractors and error correcting codes
Ο σκοπός της εργασίας είναι να κάνει μια εισαγωγή από τρεις έννοιες που είναι σημαντικές στη Θεωρία Πολυπλοκότητας, στην Κρυπτογραφία αλλά και στη Θεωρία Ψευδοτυχαιότητας γενικότερα. Οι έννοιες αυτές είναι οι Expander Γράφοι, Εξαγωγή Τυχαιότητας και Κώδικες Διόρθωσης Λαθών με Λίστα. Οι expander …
-
On the use of randomness extractors for practical committee selection
In this thesis, we look into the problem of forming and maintaining good committees that can represent a distributed network. The solution to this problem can be used as a sub-routine for Byzantine Agreement that only costs sub-quadratic message complexity. Most importantly, we make no …
-
A ULTRA-FAST QUANTUM RANDOM NUMBER GENERATOR
We describe a series of Randomness Extractors for removing bias and residual correlations in random numbers generated from measurements on noisy physical systems. The structures of the randomness extractors are based on Linear Feedback Shift Registers (LFSR). This leads to a significant …
-
Extractors for Additive Structures and Space-bounded Computation
Randomness is a powerful resource in computer science, with rich applications in algorithm design, cryptography, distributed computing, etc. Most of the applications assume access to a sequence of uniform and independent random bits. However, the randomness we collect from nature (e.g., activity of …
-
Pseudorandom Constructions: Computing in Parallel and Applications to Edit Distance Codes
… We study such constructions mainly for randomness extractors, secret sharing schemes and their applications. Randomness extractors are functions which transform biased random bits to uniform ones. They can be used to recycle random bits in computations if there are some entropies …
-
Distributed computing and cryptography with general weak random sources
The use of randomness in computer science is ubiquitous. Randomized protocols have turned out to be much more efficient than their deterministic counterparts. In addition, many problems in distributed computing and cryptography are impossible to solve without randomness. However, these applications …
-
Seedless Extractors
Randomness is a powerful tool, exploited almost everywhere in computer science – from cryptography, to distributed computing, to algorithm design and more. Unfortunately, most of these applications require access to perfectly uniform bits, while randomness harvested from nature (e.g., atmospheric …
-
Explicit two-source extractors and more
… truly random bits from imperfect sources of randomness. This is motivated by the wide use of randomness in computer science, and the fact that most accessible sources of randomness generate correlated bits, and at best contain some amount of entropy. We follow Chor and Goldreich [CG88] and …
-
Linearity, locality, and lower bounds: a unified perspective through randomness
Randomness plays two seemingly opposed roles in computation. On the one hand, it can be harnessed as a resource, allowing simple algorithms and data structures to accomplish tasks that would be impossible deterministically. On the other hand, it can be deployed as an analytic tool, exposing the …