Robust simulations and significant separations (Q2407096): Difference between revisions

@@ Property / cites work @@
+Q4440438
@@ Property / cites work: Q4440438 / rank @@
+Normal rank
@@ Property / cites work @@
+Non-deterministic exponential time has two-prover interactive protocols
+Normal rank
@@ Property / cites work @@
+Unconditional Lower Bounds against Advice
@@ Property / cites work: Unconditional Lower Bounds against Advice / rank @@
+Normal rank
@@ Property / cites work @@
+Q4258566
@@ Property / cites work: Q4258566 / rank @@
+Normal rank
@@ Property / cites work @@
+Short propositional formulas represent nondeterministic computations
+Normal rank
@@ Property / cites work @@
+Uniformly hard languages.
@@ Property / cites work: Uniformly hard languages. / rank @@
+Normal rank
@@ Property / cites work @@
+Time-space lower bounds for satisfiability
@@ Property / cites work: Time-space lower bounds for satisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+Time-space tradeoffs for satisfiability
@@ Property / cites work: Time-space tradeoffs for satisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+In search of an easy witness: Exponential time vs. probabilistic polynomial time.
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Easiness assumptions and hardness tests: Trading time for zero error
+Normal rank
@@ Property / cites work @@
+Circuit-size lower bounds and non-reducibility to sparse sets
+Normal rank
@@ Property / cites work @@
+Turing machines that take advice
@@ Property / cites work: Turing machines that take advice / rank @@
+Normal rank
@@ Property / cites work @@
+Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Q3758729
@@ Property / cites work: Q3758729 / rank @@
+Normal rank
@@ Property / cites work @@
+Natural proofs
@@ Property / cites work: Natural proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549623
@@ Property / cites work: Q3549623 / rank @@
+Normal rank
@@ Property / cites work @@
+Separating Nondeterministic Time Complexity Classes
+Normal rank
@@ Property / cites work @@
+A note on the circuit complexity of PP
@@ Property / cites work: A note on the circuit complexity of PP / rank @@
+Normal rank
@@ Property / cites work @@
+A generic time hierarchy with one bit of advice
@@ Property / cites work: A generic time hierarchy with one bit of advice / rank @@
+Normal rank
@@ Property / cites work @@
+Improving exhaustive search implies superpolynomial lower bounds
+Normal rank
@@ Property / cites work @@
+A Turing machine time hierarchy
@@ Property / cites work: A Turing machine time hierarchy / rank @@
+Normal rank