Lower bounds against weakly-uniform threshold circuits
From MaRDI portal
Publication:486977
DOI10.1007/s00453-013-9823-yzbMath1314.68142OpenAlexW2078952510MaRDI QIDQ486977
Jeff Kinne, Ruiwen Chen, Valentine Kabanets
Publication date: 19 January 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-013-9823-y
permanentthreshold circuitscounting hierarchyadvice complexity classesalternating Turing machinessuccinct circuitsuniform circuit lower boundsweakly-uniform circuits
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Turing machine time hierarchy
- The complexity of computing the permanent
- Turing machines that take advice
- Languages to diagonalize against advice classes
- The complexity of combinatorial problems with succinct input representation
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Parallel computation with threshold functions
- On uniform circuit complexity
- On ACC
- The power of the middle bit of a \(\#\)P function
- On uniformity within \(NC^ 1\)
- Lower Bounds against Weakly Uniform Circuits
- On TC0 Lower Bounds for the Permanent
- Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth
- Parity, circuits, and the polynomial-time hierarchy
- Circuit-size lower bounds and non-reducibility to sparse sets
- PP is as Hard as the Polynomial-Time Hierarchy
- Nonuniform lower bounds for exponential time classes
- Alternation
- #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
- Log Space Recognition and Translation of Parenthesis Languages
- Complexity classes defined by counting quantifiers
- A Uniform Circuit Lower Bound for the Permanent
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Computational Complexity
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Natural proofs
- Derandomizing polynomial identity tests means proving circuit lower bounds
This page was built for publication: Lower bounds against weakly-uniform threshold circuits
