On lower bounds for read-\(k\)-times branching programs
From MaRDI portal
Publication:2366719
DOI10.1007/BF01200404zbMath0777.68043OpenAlexW2095012419MaRDI QIDQ2366719
Alexander A. Razborov, Allan Borodin, Roman Smolensky
Publication date: 30 August 1993
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01200404
Related Items
On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs ⋮ A simple function that requires exponential size read-once branching programs ⋮ On multi-partition communication complexity ⋮ Communication Complexity and Lower Bounds on Multilective Computations ⋮ Finding the Median (Obliviously) with Bounded Space ⋮ Comparing the sizes of nondeterministic branching read-k-times programs ⋮ Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice ⋮ On the hierarchy of nondeterministic branching k-programs ⋮ Expanders and time-restricted branching programs ⋮ Branching Programs for Tree Evaluation ⋮ Top-down lower bounds for depth-three circuits ⋮ Randomization and nondeterminism are comparable for ordered read-once branching programs ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth ⋮ Efficient oblivious branching programs for threshold and mod functions ⋮ Neither reading few bits twice nor reading illegally helps much ⋮ No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth ⋮ A lower bound on branching programs reading some bits twice ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Classical and Quantum Computations with Restricted Memory ⋮ MCSP is hard for read-once nondeterministic branching programs ⋮ On arithmetic branching programs ⋮ A lower bound for integer multiplication on randomized ordered read-once branching programs. ⋮ Yet harder knapsack problems ⋮ BDDs -- design, analysis, complexity, and applications. ⋮ Incremental branching programs ⋮ A note on read-$k$ times branching programs ⋮ Limitations of incremental dynamic programming ⋮ Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication ⋮ New lower bounds and hierarchy results for restricted branching programs ⋮ A nondeterministic space-time tradeoff for linear codes ⋮ On BPP versus \(NP\cup coNP\) for ordered read-once branching programs ⋮ Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae ⋮ Lower bounds for restricted read-once parity branching programs ⋮ Unnamed Item ⋮ Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication ⋮ Satisfiability algorithm for syntactic read-\(k\)-times branching programs ⋮ Width hierarchy for \(k\)-OBDD of small width ⋮ Unnamed Item ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs ⋮ Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs ⋮ A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs ⋮ Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs. ⋮ A hierarchy result for read-once branching programs with restricted parity nondeterminism ⋮ On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs ⋮ On the computational power of probabilistic and quantum branching program ⋮ A very simple function that requires exponential size read-once branching programs. ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs ⋮ Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity ⋮ Time-space tradeoffs for branching programs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds to the complexity of symmetric Boolean functions
- Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
- A lower bound for read-once-only branching programs
- Meanders and their applications in lower bounds arguments
- Time-space tradeoffs for algebraic problems on general sequential machines
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- The computational complexity of universal hashing
- Superlinear lower bounds for bounded-width branching programs
- Relationships between nondeterministic and deterministic tape complexities
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- Generalized String Matching
- Nondeterministic Space is Closed under Complementation
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
- A note on read-$k$ times branching programs
