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 5 of 5 for “"Space-bounded Computation"”.
-
Extractors for Additive Structures and Space-bounded Computation
… which are uniform distributions over affine subspaces; and more generally the sum of two independent sources, which is a surprisingly general model that contains many other natural sources such as independent sources, affine sources and sources samplable by space-bounded computation. For both …
-
Derandomizing space-bounded computation via pseudorandom generators and their generalizations
… extent is randomness necessary for efficient computation? We study the problem of deterministically simulating randomized algorithms with low space overhead. The traditional approach to this problem is to try to design sufficiently powerful pseudorandom generators (PRGs). PRG constructions …
-
Techniques for analyzing the computational power of constant-depth circuits and space-bounded computation
The subject of computational complexity theory is to analyze the difficulty of solving computational problems within different models of computation. Proving lower bounds is easier in less powerful models and proving upper bounds is easier in the more powerful models. This dissertation studies …
-
Lower bound methods for multiparty communication complexity
… are of importance in many areas including time-space tradeoffs and lower bounds for VLSI and Boolean circuits, as well as constructions of universal traversal sequences and pseudorandom generators for space bounded computation. Currently, the largest known lower bounds for explicit functions are …
-
The Complexity of Composition: New Approaches to Depth and Space
… for two measures: __formula depth__ and __space complexity.__ The KRW conjecture [KRW95] states that the formula depth required to compute f ◦g is approximately depth(f)+depth(g), where f ◦g is the function given by replacing every input variable of f with a disjoint copy of g. This …