Constructive separations and their consequences

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Computational Complexity
$\Sigma_ 1^ 1$-formulae on finite structures
The Probabilistic Communication Complexity of Set Intersection
Computational Complexity
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
Simple strategies for large zero-sum games with applications to complexity theory
Parity, circuits, and the polynomial-time hierarchy
Pseudorandom bits for constant depth circuits
NP is as easy as detecting unique solutions
Oracles and queries that are sufficient for exact learning
An information statistics approach to data stream and communication complexity
Randomness vs time: Derandomization under a uniform assumption
Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
The complexity of constructing pseudorandom generators from hard functions
Pseudorandomness and average-case complexity via uniform reductions
If NP languages are hard on the worst-case, then it is easy to find their hard instances
Low-End Uniform Hardness versus Randomness Tradeoffs for AM
Natural proofs
The Shrinkage Exponent of de Morgan Formulas is 2
On the distributional complexity of disjointness
Algebrization
In search of an easy witness: Exponential time vs. probabilistic polynomial time.
Time-space lower bounds for satisfiability
Time-space tradeoffs for SAT on nonuniform machines
Easiness assumptions and hardness tests: Trading time for zero error
Circuit lower bounds in bounded arithmetics
Approximate counting in bounded arithmetic
Circuit minimization problem
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
Power from Random Strings
Derandomizing Arthur-Merlin games under uniform assumptions
Proof Complexity
Natural proofs versus derandomization
Feasibly constructive proofs of succinct weak circuit lower bounds
Hardness magnification near state-of-the-art lower bounds
Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
Sharp threshold results for computational complexity
On derandomizing algorithms that err extremely rarely
Implementing geometric complexity theory: on the separation of orbit closures via symmetries
New non-uniform lower bounds for uniform classes
Unexpected hardness results for Kolmogorov complexity under uniform reductions
Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
Succinct Permanent Is NEXP-Hard with Many Hard Instances
Improving on Gutfreund, Shaltiel,and Ta-Shma’s Paper “If NP Languages Are Hard on the Worst-Case, Then It Is Easy to Find Their Hard Instances”
When Arthur has neither random coins nor time to spare: superfast derandomization of proof systems

This page was built for publication: Constructive separations and their consequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6566463)