A note on a theorem of Barrington, Straubing and Thérien

DOI10.1016/0020-0190(96)00029-4zbMath0875.68426OpenAlexW2151774774MaRDI QIDQ1351160

Hervé Caussinus

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00029-4

zbMATH Keywords

Computational complexityPolynomialsLower bounds

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Correlation lower bounds from correlation upper bounds ⋮ A lower bound for depth-3 circuits with MOD \(m\) gates ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Non-uniform automata over groups
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Superlinear lower bounds for bounded-width branching programs
• Finite monoids and the fine structure of NC ¹
• Lower bounds for depth-three circuits with equals and mod-gates