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 29 for “"derandomization"”.
-
Lower Bounds and Derandomization
… such as BPP, AM, and MA have any nontrivial derandomization. This thesis investigates the derandomization of two randomized versions of the polynomial hierarchy.
-
Efficient derandomization and simulation of BPP under assumptions
… This thesis demonstrates that efficient derandomization and simulation is plausible. First, under stronger assumptions, we show that any randomized algorithm running in time t has a deterministic counterpart running in time t². Second, we show that under a natural assumption about the …
-
Efficient derandomization of the Lovász Local Lemma and applications to coloring and packing problems
We use algorithmic versions of Lovasz Local Lemma (LLL) to deal with the following two packing type problems: (i) a particular kind of hypergraph coloring problem, and (ii) vector packing problem. The hypergraph coloring problem is connected to the resource constrained scheduling problem and vector …
-
Vertex Connectivity via Local Computation: Breaking Quadratic Time, Poly-logarithmic Max-flows, and Derandomization
Vertex connectivity is a classic graph-theoretic notion, that roughly measures the robustness of a network against vertex failure. Vertex connectivity k of an n-vertex m-edge graph is the minimum number of vertices to be removed to disconnect the graph. A major open problem asked almost 50 years …
-
Probabilistic computations: Mild derandomizatons and zero-knowledge classes
… The primary goal in studying random algorithmsis derandomization – some method to simulate random algorithms without actually using random-ness. While full derandomization is quite difficult, we show some weak derandomization results –one using advice, and one using multi-pseudodeterminism. We …
-
Derandomizing Concentration Inequalities with dependencies and their combinatorial applications
… result or the randomized algorithm. The derandomization of C. McDiarmid's bounded differences inequality was an open problem. The main result in Chapter 3 is an efficient derandomization of the bounded differences inequality, with the time required to compute the conditional expectation …
-
Randomness in completeness and space-bounded computations
… to establish an interesting connection between derandomization of such probabilistic <i>space-bounded</i> machines and the derandomization of probabilistic <i>time-bounded</i> machines. In particular, we show that if we can derandomize a multipass machine even with a small number of passes over …
-
Derandomizing space-bounded computation via pseudorandom generators and their generalizations
… of computation and have applications beyond derandomization. There are other approaches based on generalizations of the PRG concept that are potentially easier to construct yet still valuable for derandomization. One such generalization is a hitting set generator (HSG), a standard "one-sided" …
-
Constructions, Lower Bounds, and New Directions in Cryptography and Computational Complexity
… perspective bringing together Streaming, Derandomization, and older works in Stack Machines. Our technical developments relate this new model with previous works in derandomization. For example, we show that to derandomize parts of BPP it is in some sense sufficient to derandomize BPNC (a …
-
Theoretical Aspects of Randomization in Computation
… use randomness to obtain efficient algorithms? Derandomization: How (and when) can we "remove" our dependence on random bits? In this thesis, we consider important problems in these three prominent and diverse areas pertaining to randomness. In randomness extraction, we present extractors for …
-
PROBLEMS IN QUANTUM TAMPER RESILIENT CRYPTOGRAPHY AND QUANTUM COMMUNICATION COMPLEXITY
… privacy-amplification (PA), pseudo-randomness, derandomization, expanders, combinatorics, and cryptography. Extractors are functions that are useful in extracting almost truly random bits from imperfect sources of randomness. While non-malleable extractors provide a stronger notion of randomness …
-
LEARNING ABOUT QUANTUM STATES AND PROCESSES: A MODERN APPROACH
… bring together finite-depth classical shadows, derandomization, and tensor network simulation to present an algorithm for tailoring a sequence of measurements to a set of observables of interest, demonstrating the effectiveness of our technique for a number of tasks in quantum chemistry and …
-
Fractals in complexity and geometry
… the power of nontrivial fractals in terms of derandomization, the fractal dimension of certain complexity classes, and some relationship between fractal dimension and normality. For fractal geometry, we will discuss some new results in computable analysis, which will include an effective …
-
New Lower Bounds in Algebraic Complexity and Connections to Polynomial Identity Testing
… about computational hardness for efficient derandomization, but we come up with standard, minimal assumptions that we show to be both necessary and (nearly) sufficient. This considerably tightens the relationship between algebraic hardness and randomness, offering a clearer roadmap for …
-
Extractors for Additive Structures and Space-bounded Computation
… new weighted pseudorandom generators and derandomization bounds for small-space algorithms.
-
Reducing Communication Costs in Multi-Party Computation
… MPC as function evaluation is expensive, whereas derandomization is cheap. In this thesis, a generic method is given for outsourcing preprocessing to a set of servers, which means that low-powered clients who wish to evaluate functions on their data can do so.<br/><br/> The final contribution is a …
-
A study of correlation-immune, resilient and related cryptographic functions
… are resilient and correlation-immune functions, derandomization of algorithms, random pattern testing of VLSI chips, authentication codes, universal hash functions, threshold schemes, and perfect local randomisers. This dissertation is a study of correlation-immune and resilient functions from a …
-
Distributed approximation algorithms for graph problems
… function-based approach, we believe that this derandomization framework can be applied to a broader range of important distributed graph problems, and exploring its full scope constitutes an interesting direction for future research.
-
Computational applications of invariance principles
… complexity theory. Our work addresses such derandomization questions for natural and basic geometric concept classes such as halfspaces, polynomial threshold functions (PTFs) and polytopes. We develop a reasonably generic framework for obtaining pseudorandom generators (PRGs) from invariance …
Page 1 of 2