Robust simulations and significant separations

DOI10.1016/j.ic.2017.07.002zbMath1376.68049arXiv1012.2034MaRDI QIDQ2407096

Rahul Santhanam, Lance J. Fortnow

Publication date: 28 September 2017

Published in: Information and Computation, Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.2034

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Relations and equivalences between circuit lower bounds and karp-lipton theorems, Circuit lower bounds from NP-hardness of MCSP under turing reductions, Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking, Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly, Robust simulations and significant separations, Complexity with Rod, NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Turing machine time hierarchy
• Non-deterministic exponential time has two-prover interactive protocols
• Turing machines that take advice
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
• Short propositional formulas represent nondeterministic computations
• Hardness vs randomness
• Time-space tradeoffs for satisfiability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Uniformly hard languages.
• Robust simulations and significant separations
• A generic time hierarchy with one bit of advice
• A note on the circuit complexity of PP
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Improving exhaustive search implies superpolynomial lower bounds
• Nondeterministic Separations
• Circuit-size lower bounds and non-reducibility to sparse sets
• Time-space lower bounds for satisfiability
• Unconditional Lower Bounds against Advice
• Separating Nondeterministic Time Complexity Classes
• Natural proofs
• Easiness assumptions and hardness tests: Trading time for zero error