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 18 of 18 for “"branching programs"”.

  1. Proof complexity of systems of branching programs

    … about deterministic and non-deterministic branching programs (BPs and NBPs respectively). It is based on work by Buss, Das and Knop, where they defined the systems eLpNqDT reasoning with (N)BPs by using extension variables/axioms to represent the dag-structure, over a language of …

    birmingham Download PDF for Proof complexity of systems of branching programs (opens in a new tab)

  2. Circuits and branching programs in meta-complexity

    … meta-complexity functions via circuits and branching programs, and connections between them. Studying such connections improves the understanding of structural complexity. * We show that it is unconditionally hard to decide a meta-complexity problem called the Minimum Circuit Size Problem …

    bu Repository record for Circuits and branching programs in meta-complexity (opens in a new tab)

  3. Laconic Evaluation of Branching Programs from the Diffie-Hellman Assumption

    … giving a laconic protocol for the evaluation of branching programs (BPs) from the Diffie-Hellman assumption. In this setting, the receiver holds a large branching program BP and the sender holds a short input x. Our protocol allows the receiver to learn x if and only if BP(x) =1, and nothing …

    waterloo Repository record for Laconic Evaluation of Branching Programs from the Diffie-Hellman Assumption (opens in a new tab)

  4. Branching Program Lower Bounds

    … bounds on the size of a restricted model of branching programs called semantic read-once 3-ary nondeterministic branching programs solving a polytime computable function, in particular the polynomial evaluation problem. In the second part, we prove lower bounds against branching programs …

    toronto-retro Repository record for Branching Program Lower Bounds (opens in a new tab)

  5. Derandomizing space-bounded computation via pseudorandom generators and their generalizations

    … including unbounded-width permutation branching programs, read-once AC⁰ formulas, and superlinear-size constant-depth threshold circuits. The first two PRGs are unconditionally near-optimal; substantially improving the third would require a breakthrough in circuit lower bounds. Each PRG …

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

  6. Efficient Protocols for Multi-Party Computation

    … secure function evaluation protocols for branching programs, where the communication complexity is linear in the size of the inputs, and polynomial in the security parameter. Our result is based on the circular security of the Paillier's encryption scheme. Our work followed the …

    cuny-grad Repository record for Efficient Protocols for Multi-Party Computation (opens in a new tab)

  7. Growth processes on formulas and reversible circuits

    … other models of computation such as permutation branching programs (Barrington, 1985), based on a new measure that we call bandwidth. By leveraging these relationships, we exhibit a natural gap between two families of reversible circuits that correspond to width-4 and width-5 permutation …

    ubc Repository record for Growth processes on formulas and reversible circuits (opens in a new tab) Download PDF for Growth processes on formulas and reversible circuits (opens in a new tab)

  8. New Lower Bounds in Algebraic Complexity and Connections to Polynomial Identity Testing

    … set-multilinear formulas and set-multilinear branching programs. These results suggest pathways towards the ultimate, decades-old goal of proving super-polynomial lower bounds for the corresponding general models. The second part of this thesis addresses Polynomial Identity Testing (PIT): …

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

  9. Extractors for Additive Structures and Space-bounded Computation

    … requirement, and a new lower bound for linear branching programs. Finally, we develop more results regarding randomness and space-bounded computation, including 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)

  10. Frontiers in Lattice Cryptography and Program Obfuscation

    … efficiently-testable property for any two branching programs, called partial inequivalence, which we show is sufficient for launching an ``annihilation attack'' against several obfuscation candidates based on Garg-Gentry-Halevi multilinear maps.

    maryland Repository record for Frontiers in Lattice Cryptography and Program Obfuscation (opens in a new tab)

  11. Collusion resistant traitor tracing systems

    … can be used to encode many different types of programs, but is only secure as long as the attacker sees a bounded number of such ciphertexts. We first show how to combine Mixed FE with Attribute-Based Encryption to achieve traitor tracing. Second we build Mixed FE systems for polynomial sized …

    texas Repository record for Collusion resistant traitor tracing systems (opens in a new tab)

  12. User-Controlled Computations in Untrusted Computing Environments

    … construction supports the computation class of branching programs. Previous works for this computation class achieved either short keys or tighter security reductions but not both. 2) We formally model the primitive of trusted hardware inspired by Intel's Software Guard eXtensions (SGX). We then …

    waterloo Repository record for User-Controlled Computations in Untrusted Computing Environments (opens in a new tab)

  13. ATTRIBUTE-BASED ENCRYPTIONS AND FORMAL VERIFICATION OF LATTICE-BASED CRYPTOGRAPHY

    … Encryption (ABE) scheme for all polynomial-size Branching Programs from Learning With Errors assumption (Regev STOC’05). Attribute based encryption (ABE) is an advanced encryption system with a built-in mechanism to generate keys associated with functions which in turn provide restricted access …

    cornell Repository record for ATTRIBUTE-BASED ENCRYPTIONS AND FORMAL VERIFICATION OF LATTICE-BASED CRYPTOGRAPHY (opens in a new tab)

  14. Randomness in completeness and space-bounded computations

    … of probabilistic time-bounded machines under branching program lower bounds. The standard method of derandomizing time-bounded probabilistic machines depends on various circuit lower bounds, which are notoriously hard to prove. We show that the derandomization of low-degree polynomial identity …

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

  15. Time-Space Tradeoffs and Query Complexity in Statistics, Coding Theory, and Quantum Computing

    Computational complexity is the field that studies the computational resources needed by algorithms to correctly solve computational problems. In this thesis, we derive lower bounds on the computational complexity of different problems for different classes of algorithms. The computational …

    washington Repository record for Time-Space Tradeoffs and Query Complexity in Statistics, Coding Theory, and Quantum Computing (opens in a new tab)

  16. Linearity, locality, and lower bounds: a unified perspective through randomness

    … improved pseudorandom generators for width-2 branching programs reading many bits at a time, and strong correlation bounds for set-multilinear polynomials.

    texas Repository record for Linearity, locality, and lower bounds: a unified perspective through randomness (opens in a new tab)

  17. Program reliability through algorithmic design and analysis

    … and efficient design and analysis of reliable programs. In the first and second parts of this dissertation, we focus on the development of programs that are free from programming errors. The intent is not to eliminate the human programmer, but instead to complement his or her expertise, with …

    texas Repository record for Program reliability through algorithmic design and analysis (opens in a new tab)