Relations and equivalences between circuit lower bounds and karp-lipton theorems (Q5091782): Difference between revisions

@@ label / en / label / en @@
+Relations and equivalences between circuit lower bounds and karp-lipton theorems
@@ 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 / cites work @@
+Robust simulations and significant separations
@@ Property / cites work: Robust simulations and significant separations / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse sets in NP-P: EXPTIME versus NEXPTIME
@@ Property / cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME / rank @@
+Normal rank
@@ Property / cites work @@
+Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
+Normal rank
@@ Property / cites work @@
+Q5121895
@@ Property / cites work: Q5121895 / rank @@
+Normal rank
@@ Property / cites work @@
+In search of an easy witness: Exponential time vs. probabilistic polynomial time.
+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 @@
+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 @@
+Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
+Normal rank
@@ Property / cites work @@
+Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
+Normal rank
@@ Property / cites work @@
+Hardness magnification near state-of-the-art lower bounds
+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 @@
+PP is as Hard as the Polynomial-Time Hierarchy
@@ Property / cites work: PP is as Hard as the Polynomial-Time Hierarchy / 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 @@
+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 @@
+Some consequences of non-uniform conditions on uniform classes
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.4230/lipics.ccc.2019.30
+Normal rank
@@ Property / OpenAlex ID @@
+W2964773335
@@ Property / OpenAlex ID: W2964773335 / rank @@
+Normal rank
@@ Property / title @@
+Relations and equivalences between circuit lower bounds and karp-lipton theorems (English)
+Normal rank