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
Cites work
- scientific article; zbMATH DE number 1351078 (Why is no real title available?)
- scientific article; zbMATH DE number 2019636 (Why is no real title available?)
- Amplifying lower bounds by means of self-reducibility
- Circuit-size lower bounds and non-reducibility to sparse sets
- Computational Complexity
- Extractors and pseudorandom generators
- Improving exhaustive search implies superpolynomial lower bounds
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Local reductions
- On the Computational Complexity of Algorithms
- On uniform circuit complexity
- On uniformity and circuit lower bounds
- On uniformity within \(NC^ 1\)
- Parallel computation with threshold functions
- Randomness vs time: Derandomization under a uniform assumption
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Short PCPs with projection queries
- Speedups of deterministic machines by synchronous parallel machines
- The Shrinkage Exponent of de Morgan Formulas is 2
- The complexity of constructing pseudorandom generators from hard functions
- Two-Tape Simulation of Multitape Turing Machines
Cited in
(22)- Extensional Uniformity for Boolean Circuits
- New non-uniform lower bounds for uniform classes
- The lower reaches of circuit uniformity
- Uniform derandomization from pathetic lower bounds
- Mathematical Foundations of Computer Science 2004
- P-uniform circuit complexity
- Rigid matrices from rectangular PCPs
- Easiness amplification and uniform circuit lower bounds
- On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
- Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
- Proving Circuit Lower Bounds in High Uniform Classes
- Amplifying circuit lower bounds against polynomial time, with applications
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- Uniform Derandomization from Pathetic Lower Bounds
- On circuit diameter bounds via circuit imbalances
- A Uniform Circuit Lower Bound for the Permanent
- On uniformity and circuit lower bounds
- Nonuniform ACC circuit lower bounds
- Non-uniform depth of polynomial time and space simulations.
- Amplifying lower bounds by means of self-reducibility
- Typically-correct derandomization for small time and space
- Polynomial time ultrapowers and the consistency of circuit lower bounds
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)
