On uniformity and circuit lower bounds
DOI10.1007/S00037-014-0087-YzbMATH Open1314.68139OpenAlexW2030202224MaRDI QIDQ488049FDOQ488049
Rahul Santhanam, 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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computational Complexity
- On the Computational Complexity of Algorithms
- On uniform circuit complexity
- On uniformity within \(NC^ 1\)
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Parallel computation with threshold functions
- Randomness vs time: Derandomization under a uniform assumption
- The complexity of constructing pseudorandom generators from hard functions
- Improving exhaustive search implies superpolynomial lower bounds
- The Shrinkage Exponent of de Morgan Formulas is 2
- Speedups of deterministic machines by synchronous parallel machines
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Circuit-size lower bounds and non-reducibility to sparse sets
- Amplifying lower bounds by means of self-reducibility
- Two-Tape Simulation of Multitape Turing Machines
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Local Reductions
- On uniformity and circuit lower bounds
- Short PCPs with Projection Queries
- Extractors and pseudorandom generators
Cited In (14)
- On circuit diameter bounds via circuit imbalances
- Extensional Uniformity for Boolean Circuits
- P-uniform circuit complexity
- Uniform Derandomization from Pathetic Lower Bounds
- Mathematical Foundations of Computer Science 2004
- Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma
- Proving Circuit Lower Bounds in High Uniform Classes
- On uniformity and circuit lower bounds
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Rigid matrices from rectangular PCPs
- On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
- Nonuniform ACC Circuit Lower Bounds
- Typically-correct derandomization for small time and space
- Uniform derandomization from pathetic lower bounds
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Lower Bounds against Weakly Uniform Circuits 👍 👎
- P-uniform circuit complexity 👍 👎
- On circuit lower bounds from derandomization 👍 👎
- Circuit lower bounds in bounded arithmetics 👍 👎
- On the Limit of Some Algorithmic Approach to Circuit Lower Bounds 👍 👎
- Some results on uniform arithmetic circuit complexity 👍 👎
- A Uniform Circuit Lower Bound for the Permanent 👍 👎
- Proving Circuit Lower Bounds in High Uniform Classes 👍 👎
This page was built for publication: On uniformity and circuit lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q488049)
