Constructive separations and their consequences
From MaRDI portal
Publication:6566463
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)