On uniformity and circuit lower bounds
DOI10.1007/S00037-014-0087-YzbMATH Open1314.68139OpenAlexW2030202224MaRDI QIDQ488049FDOQ488049
Authors: 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
Recommendations
- Lower bounds against weakly uniform circuits
- Proving Circuit Lower Bounds in High Uniform Classes
- A Uniform Circuit Lower Bound for the Permanent
- Some results on uniform arithmetic circuit complexity
- Easiness amplification and uniform circuit lower bounds
- scientific article; zbMATH DE number 806749
- On the limit of some algorithmic approach to circuit lower bounds
- Circuit lower bounds in bounded arithmetics
- P-uniform circuit complexity
- On circuit lower bounds from derandomization
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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 (22)
- New non-uniform lower bounds for uniform classes
- On circuit diameter bounds via circuit imbalances
- Extensional Uniformity for Boolean Circuits
- P-uniform circuit complexity
- Amplifying lower bounds by means of self-reducibility
- A Uniform Circuit Lower Bound for the Permanent
- Uniform Derandomization from Pathetic Lower Bounds
- The lower reaches of circuit uniformity
- Nonuniform ACC circuit lower bounds
- Mathematical Foundations of Computer Science 2004
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- 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
- Amplifying circuit lower bounds against polynomial time, with applications
- Typically-correct derandomization for small time and space
- Uniform derandomization from pathetic lower bounds
- Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
- Easiness amplification and uniform circuit lower bounds
- Non-uniform depth of polynomial time and space simulations.
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)
