Lower Bounds against Weakly Uniform Circuits
DOI10.1007/978-3-642-32241-9_35zbMATH Open1364.68217OpenAlexW2284184122MaRDI QIDQ2914345FDOQ2914345
Ruiwen Chen, Valentine Kabanets
Publication date: 25 September 2012
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-32241-9_35
permanentthreshold circuitscounting hierarchyadvice complexity classesalternating Turing machinessuccinct circuitsuniform circuit lower boundsweakly uniform circuits
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (8)
- Feasibly constructive proofs of succinct weak circuit lower bounds
- P-uniform circuit complexity
- Mathematical Foundations of Computer Science 2004
- Proving Circuit Lower Bounds in High Uniform Classes
- Lower bounds against weakly-uniform threshold circuits
- On uniformity and circuit lower bounds
- Amplifying circuit lower bounds against polynomial time, with applications
- Lower Bounds for Coin-Weighing Problems
This page was built for publication: Lower Bounds against Weakly Uniform Circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2914345)
