Automata, Languages and Programming
From MaRDI portal
Publication:5716847
DOI10.1007/11523468zbMath1085.68061WikidataQ56656999 ScholiaQ56656999MaRDI QIDQ5716847
Kristoffer Arnsfelt Hansen, Arkadev Chattopadhyay
Publication date: 10 January 2006
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11523468
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
New algorithms and lower bounds for circuits with linear threshold gates, Near-optimal pseudorandom generators for constant-depth read-once formulas, Exponential lower bound for bounded depth circuits with few threshold gates, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates, Depth Reduction for Circuits with a Single Layer of Modular Counting Gates