Bounds for Width Two Branching Programs
From MaRDI portal
Publication:3718153
DOI10.1137/0215040zbMath0589.68034OpenAlexW2021039182MaRDI QIDQ3718153
Danny Dolev, Allan Borodin, Wolfgang J. Paul, Faith E. Fich
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215040
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
On learning width two branching programs ⋮ Entropy of contact circuits and lower bounds on their complexity ⋮ Skew Circuits of Small Width ⋮ Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) ⋮ Skew circuits of small width ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Collusion Resistant Traitor Tracing from Learning with Errors ⋮ Deterministic compression with uncertain priors ⋮ Lattice-based FHE as secure as PKE ⋮ Cryptogenography ⋮ Limits of random oracles in secure computation ⋮ Non-commutative arithmetic circuits with division ⋮ Decision trees, protocols and the entropy-influence conjecture ⋮ Locally testable codes and cayley graphs ⋮ Invitation games and the price of stability ⋮ Welfare maximization and truthfulness in mechanism design with ordinal preferences ⋮ Coordination mechanisms from (almost) all scheduling policies ⋮ Private interactive communication across an adversarial channel ⋮ Tree codes and a conjecture on exponential sums ⋮ Capacity of non-malleable codes ⋮ Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications ⋮ Adversarial hypothesis testing and a quantum stein's lemma for restricted measurements ⋮ Sequential decision making with vector outcomes ⋮ Learning mixtures of arbitrary distributions over large discrete domains ⋮ Why do simple algorithms for triangle enumeration work in the real world? ⋮ Black-box obfuscation for d-CNFs ⋮ Candidate weak pseudorandom functions in AC 0 ○ MOD 2 ⋮ Iterated group products and leakage resilience against NC1 ⋮ Building one-time memories from isolated qubits ⋮ Attribute-efficient evolvability of linear functions ⋮ Energy-efficient circuit design ⋮ Rate-independent computation in continuous chemical reaction networks ⋮ Testers and their applications ⋮ On the automorphism groups of strongly regular graphs I ⋮ Faster private release of marginals on small databases ⋮ Mechanism design in large games ⋮ Redrawing the boundaries on purchasing data from privacy-sensitive individuals ⋮ Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems ⋮ Complexity of approximating CSP with balance / hard constraints ⋮ Integer feasibility of random polytopes ⋮ Multireference alignment using semidefinite programming ⋮ Partial tests, universal tests and decomposability ⋮ High dimensional expanders and property testing ⋮ Parameterized testability ⋮ Direct sum fails for zero error average communication ⋮ Rational arguments ⋮ Time-space tradeoffs for algebraic problems on general sequential machines ⋮ Lower bounds on the complexity of real-time branching programs ⋮ On the size of binary decision diagrams representing Boolean functions ⋮ \(NC^ 1\): The automata-theoretic viewpoint ⋮ Towards optimal simulations of formulas by bounded-width programs ⋮ On the structure of Boolean functions with small spectral norm ⋮ The truth behind the myth of the folk theorem ⋮ Expanders with respect to Hadamard spaces and random graphs ⋮ Limits of local algorithms over sparse random graphs ⋮ The Power of Diversity ⋮ Decompositions of Triangle-Dense Graphs ⋮ Unnamed Item ⋮ Separating Semantic and Circular Security for Symmetric-Key Bit Encryption from the Learning with Errors Assumption
This page was built for publication: Bounds for Width Two Branching Programs
