On uniformity and circuit lower bounds
From MaRDI portal
Publication:488049
DOI10.1007/s00037-014-0087-yzbMath1314.68139OpenAlexW2030202224MaRDI QIDQ488049
Rahul Santhanam, R. Ryan Williams
Publication date: 23 January 2015
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://www.pure.ed.ac.uk/ws/files/19475310/Santhanam_Williams_2014_On_Uniformity_and_Circuit_Lower_Bounds.pdf
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Nonuniform ACC Circuit Lower Bounds ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ On uniformity and circuit lower bounds ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds ⋮ Typically-correct derandomization for small time and space
Cites Work
- Unnamed Item
- Unnamed Item
- On uniformity and circuit lower bounds
- Speedups of deterministic machines by synchronous parallel machines
- Parallel computation with threshold functions
- On uniform circuit complexity
- Randomness vs time: Derandomization under a uniform assumption
- The complexity of constructing pseudorandom generators from hard functions
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- On uniformity within \(NC^ 1\)
- Improving exhaustive search implies superpolynomial lower bounds
- Circuit-size lower bounds and non-reducibility to sparse sets
- Local Reductions
- Amplifying lower bounds by means of self-reducibility
- The Shrinkage Exponent of de Morgan Formulas is 2
- Short PCPs with Projection Queries
- Computational Complexity
- On the Computational Complexity of Algorithms
- Extractors and pseudorandom generators
- Two-Tape Simulation of Multitape Turing Machines
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
