Superlinear lower bounds for bounded-width branching programs

DOI10.1006/JCSS.1995.1029zbMath0837.68056OpenAlexW2025481592MaRDI QIDQ1894446

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

threshold functionscircuit complexitybounded-width branching program

Mathematics Subject Classification ID

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

Related Items (18)

On lower bounds for read-\(k\)-times branching programs ⋮ A note on a theorem of Barrington, Straubing and Thérien ⋮ On uniformity within \(NC^ 1\) ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ SOLVABLE MONOIDS WITH COMMUTING IDEMPOTENTS ⋮ Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) ⋮ Efficient oblivious branching programs for threshold and mod functions ⋮ Learning Read-Constant Polynomials of Constant Degree Modulo Composites ⋮ Learning read-constant polynomials of constant degree modulo composites ⋮ Learning expressions and programs over monoids ⋮ A topological approach to non-uniform complexity ⋮ The Power of Diversity ⋮ Circuit complexity before the dawn of the new millennium ⋮ Localizability of the approximation method ⋮ An impossibility gap between width-4 and width-5 permutation branching programs ⋮ An ergodic theorem for read-once non-uniform deterministic finite automata ⋮ Languages defined with modular counting quantifiers ⋮ Non-uniform automata over groups

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