Publication:2407096: Difference between revisions
From MaRDI portal
Publication:2407096
Created automatically from import240129110113 |
EloiFerrer (talk | contribs) m EloiFerrer moved page Robust simulations and significant separations to Robust simulations and significant separations: Duplicate |
(No difference)
|
Latest revision as of 15:31, 2 May 2024
DOI10.1016/j.ic.2017.07.002zbMath1376.68049arXiv1012.2034OpenAlexW2736246298MaRDI 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
Related Items
Robust simulations and significant separations ⋮ Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking ⋮ Complexity with Rod ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions ⋮ Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
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