Superlinear lower bounds for bounded-width branching programs

DOI10.1006/JCSS.1995.1029MaRDI QIDQ1894446zbMATH OpenOpenAlexFDO

Authors David A. Mix Barrington, Howard Straubing

Publication date 21 August 1995

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1995.1029

zbMATH Keywords

circuit complexitythreshold functionsbounded-width branching program

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 706832
• A superpolynomial lower bound for \((1,+k(n))\)-branching programs
• scientific article; zbMATH DE number 3913677
• Bounds for Width Two Branching Programs
• scientific article; zbMATH DE number 36617
• scientific article; zbMATH DE number 5899238
• Stochastic Algorithms: Foundations and Applications
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• scientific article; zbMATH DE number 2086405
• New lower bounds and hierarchy results for restricted branching programs

Cited in

(24)

• Bounds for Width Two Branching Programs
• Circuit complexity before the dawn of the new millennium
• Meanders and their applications in lower bounds arguments
• The power of diversity
• Learning read-constant polynomials of constant degree modulo composites
• Non-uniform automata over groups
• A note on a theorem of Barrington, Straubing and Thérien
• SOLVABLE MONOIDS WITH COMMUTING IDEMPOTENTS
• Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Learning expressions and programs over monoids
• Localizability of the approximation method
• Nonuniform ACC circuit lower bounds
• scientific article; zbMATH DE number 36617 (Why is no real title available?)
• Learning Read-Constant Polynomials of Constant Degree Modulo Composites
• On uniformity within \(NC^ 1\)
• A topological approach to non-uniform complexity
• Superpolynomial lower bounds for monotone span programs
• An impossibility gap between width-4 and width-5 permutation branching programs
• scientific article; zbMATH DE number 5899238 (Why is no real title available?)
• On lower bounds for read-\(k\)-times branching programs
• Efficient oblivious branching programs for threshold and mod functions
• An ergodic theorem for read-once non-uniform deterministic finite automata
• Languages defined with modular counting quantifiers

This page was built for publication: Superlinear lower bounds for bounded-width branching programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894446)