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"”.

  1. 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.

    waterloo Repository record for Lower Bounds and Derandomization (opens in a new tab)

  2. 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 …

    texas Repository record for Efficient derandomization and simulation of BPP under assumptions (opens in a new tab)

  3. 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 …

    cau-kiel Repository record for Efficient derandomization of the Lovász Local Lemma and applications to coloring and packing problems (opens in a new tab)

  4. 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 …

    aalto Repository record for Vertex Connectivity via Local Computation: Breaking Quadratic Time, Poly-logarithmic Max-flows, and Derandomization (opens in a new tab)

  5. 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 …

    iastate Repository record for Probabilistic computations: Mild derandomizatons and zero-knowledge classes (opens in a new tab)

  6. 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 …

    cau-kiel Repository record for Derandomizing Concentration Inequalities with dependencies and their combinatorial applications (opens in a new tab)

  7. 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 …

    iastate Repository record for Randomness in completeness and space-bounded computations (opens in a new tab)

  8. 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" …

    texas Repository record for Derandomizing space-bounded computation via pseudorandom generators and their generalizations (opens in a new tab)

  9. 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 …

    toronto-retro Repository record for Constructions, Lower Bounds, and New Directions in Cryptography and Computational Complexity (opens in a new tab)

  10. 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 …

    gatech Repository record for Theoretical Aspects of Randomization in Computation (opens in a new tab)

  11. 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 …

    nus Repository record for PROBLEMS IN QUANTUM TAMPER RESILIENT CRYPTOGRAPHY AND QUANTUM COMMUNICATION COMPLEXITY (opens in a new tab) Download file for PROBLEMS IN QUANTUM TAMPER RESILIENT CRYPTOGRAPHY AND QUANTUM COMMUNICATION COMPLEXITY (opens in a new tab)

  12. 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 …

    maryland Repository record for LEARNING ABOUT QUANTUM STATES AND PROCESSES: A MODERN APPROACH (opens in a new tab)

  13. 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 …

    iastate Repository record for Fractals in complexity and geometry (opens in a new tab)

  14. 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 …

    toronto-retro Repository record for New Lower Bounds in Algebraic Complexity and Connections to Polynomial Identity Testing (opens in a new tab)

  15. Extractors for Additive Structures and Space-bounded Computation

    … new weighted pseudorandom generators and derandomization bounds for small-space algorithms.

    cornell Repository record for Extractors for Additive Structures and Space-bounded Computation (opens in a new tab)

  16. 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 …

    bristol Repository record for Reducing Communication Costs in Multi-Party Computation (opens in a new tab) Download PDF for Reducing Communication Costs in Multi-Party Computation (opens in a new tab)

  17. 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 …

    nebraska Repository record for A study of correlation-immune, resilient and related cryptographic functions (opens in a new tab)

  18. 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.

    freiburg-diss Repository record for Distributed approximation algorithms for graph problems (opens in a new tab)

  19. 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 …

    texas Repository record for Computational applications of invariance principles (opens in a new tab)

Page 1 of 2