Constructive separations and their consequences

Cites work

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

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)