Average-case rigidity lower bounds (Q2117087): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1007/978-3-030-79416-3_11
+Normal rank
@@ Property / OpenAlex ID @@
+W3177031611
@@ Property / OpenAlex ID: W3177031611 / rank @@
+Normal rank
@@ Property / cites work @@
+Short PCPs with Projection Queries
@@ Property / cites work: Short PCPs with Projection Queries / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
+Normal rank
@@ Property / cites work @@
+Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
+Normal rank
@@ Property / cites work @@
+Strong average-case lower bounds from non-trivial derandomization
+Normal rank
@@ Property / cites work @@
+Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
+Normal rank
@@ Property / cites work @@
+An average-case lower bound against \(\mathsf{ACC}^0\)
+Normal rank
@@ Property / cites work @@
+A hierarchy for nondeterministic time complexity
@@ Property / cites work: A hierarchy for nondeterministic time complexity / rank @@
+Normal rank
@@ Property / cites work @@
+On Yao’s XOR-Lemma
@@ Property / cites work: On Yao’s XOR-Lemma / rank @@
+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 @@
+Q5875692
@@ Property / cites work: Q5875692 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5005182
@@ Property / cites work: Q5005182 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
+Normal rank
@@ Property / cites work @@
+Separating Nondeterministic Time Complexity Classes
+Normal rank
@@ Property / cites work @@
+Q4164821
@@ Property / cites work: Q4164821 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
+Normal rank
@@ Property / cites work @@
+Improving exhaustive search implies superpolynomial lower bounds
+Normal rank
@@ Property / cites work @@
+Natural Proofs versus Derandomization
@@ Property / cites work: Natural Proofs versus Derandomization / 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 @@
+A Turing machine time hierarchy
@@ Property / cites work: A Turing machine time hierarchy / rank @@
+Normal rank