Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma (Q5130843): Difference between revisions

@@ Property / author @@
-R. Ryan Williams
@@ Property / author: R. Ryan Williams / rank @@
-Normal rank
@@ Property / author @@
+R. Ryan Williams
@@ Property / author: R. Ryan Williams / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q124882178
@@ Property / Wikidata QID: Q124882178 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum Computability
@@ Property / cites work: Quantum Computability / rank @@
+Normal rank
@@ Property / cites work @@
+Q4266552
@@ Property / cites work: Q4266552 / rank @@
+Normal rank
@@ Property / cites work @@
+\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
+Normal rank
@@ Property / cites work @@
+Short PCPs with Projection Queries
@@ Property / cites work: Short PCPs with Projection Queries / rank @@
+Normal rank
@@ Property / cites work @@
+On ACC
@@ Property / cites work: On ACC / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
+Normal rank
@@ Property / cites work @@
+Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
+Normal rank
@@ Property / cites work @@
+Some New Consequences of the Hypothesis That P Has Fixed Polynomial-Size Circuits
+Normal rank
@@ Property / cites work @@
+Efficient learning algorithms yield circuit lower bounds
+Normal rank
@@ Property / cites work @@
+New non-uniform lower bounds for uniform classes
@@ Property / cites work: New non-uniform lower bounds for uniform classes / rank @@
+Normal rank
@@ Property / cites work @@
+Robust simulations and significant separations
@@ Property / cites work: Robust simulations and significant separations / 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 @@
+Local Reductions
@@ Property / cites work: Local Reductions / rank @@
+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 @@
+New Collapse Consequences of NP Having Small Circuits
+Normal rank
@@ Property / cites work @@
+Algebraic methods for interactive proof systems
@@ Property / cites work: Algebraic methods for interactive proof systems / rank @@
+Normal rank
@@ Property / cites work @@
+Q4938667
@@ Property / cites work: Q4938667 / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Q5111148
@@ Property / cites work: Q5111148 / rank @@
+Normal rank
@@ Property / cites work @@
+Circuit Lower Bounds for Merlin–Arthur Classes
@@ Property / cites work: Circuit Lower Bounds for Merlin–Arthur Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Separating Nondeterministic Time Complexity Classes
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators without the XOR lemma
@@ Property / cites work: Pseudorandom generators without the XOR lemma / rank @@
+Normal rank
@@ Property / cites work @@
+On uniformity and circuit lower bounds
@@ Property / cites work: On uniformity and circuit lower bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandomness and average-case complexity via uniform reductions
+Normal rank
@@ Property / cites work @@
+Pseudo-random generators for all hardnesses
@@ Property / cites work: Pseudo-random generators for all hardnesses / rank @@
+Normal rank
@@ Property / cites work @@
+New algorithms and lower bounds for circuits with linear threshold gates
+Normal rank
@@ Property / cites work @@
+Nonuniform ACC Circuit Lower Bounds
@@ Property / cites work: Nonuniform ACC Circuit Lower Bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Improving Exhaustive Search Implies Superpolynomial Lower Bounds
+Normal rank
@@ Property / cites work @@
+Q5121894
@@ Property / cites work: Q5121894 / rank @@
+Normal rank
@@ Property / cites work @@
+Natural Proofs versus Derandomization
@@ Property / cites work: Natural Proofs versus Derandomization / rank @@
+Normal rank
@@ Property / cites work @@
+A Turing machine time hierarchy
@@ Property / cites work: A Turing machine time hierarchy / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/18m1195887
+Normal rank
@@ Property / OpenAlex ID @@
+W3009964738
@@ Property / OpenAlex ID: W3009964738 / rank @@
+Normal rank