Local Reductions (Q3448833): Difference between revisions

@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+In search of an easy witness: Exponential time vs. probabilistic polynomial time.
+Normal rank
@@ Property / cites work @@
+Explicit lower bound of             <i>4.5n - o(n)</i>             for boolena circuits
+Normal rank
@@ Property / cites work @@
+Reducing the complexity of reductions
@@ Property / cites work: Reducing the complexity of reductions / rank @@
+Normal rank
@@ Property / cites work @@
+A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
+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 @@
+A Survey of Lower Bounds for Satisfiability and Related Problems
+Normal rank
@@ Property / cites work @@
+Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
+Normal rank
@@ Property / cites work @@
+Towards a Study of Low-Complexity Graphs
@@ Property / cites work: Towards a Study of Low-Complexity Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Amplifying lower bounds by means of self-reducibility
+Normal rank
@@ Property / cites work @@
+-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
+Normal rank
@@ Property / cites work @@
+On the concrete efficiency of probabilistically-checkable proofs
+Normal rank
@@ Property / cites work @@
+A 5n − o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function
+Normal rank
@@ Property / cites work @@
+Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
+Normal rank
@@ Property / cites work @@
+Natural Proofs versus Derandomization
@@ Property / cites work: Natural Proofs versus Derandomization / rank @@
+Normal rank
@@ Property / cites work @@
+Improving Exhaustive Search Implies Superpolynomial Lower Bounds
+Normal rank
@@ Property / cites work @@
+New algorithms and lower bounds for circuits with linear threshold gates
+Normal rank
@@ Property / cites work @@
+Short PCPs with Projection Queries
@@ Property / cites work: Short PCPs with Projection Queries / rank @@
+Normal rank
@@ Property / cites work @@
+Two-Tape Simulation of Multitape Turing Machines
@@ Property / cites work: Two-Tape Simulation of Multitape Turing Machines / rank @@
+Normal rank
@@ Property / cites work @@
+Q4164821
@@ Property / cites work: Q4164821 / rank @@
+Normal rank
@@ Property / cites work @@
+Satisfiability Is Quasilinear Complete in NQL
@@ Property / cites work: Satisfiability Is Quasilinear Complete in NQL / rank @@
+Normal rank
@@ Property / cites work @@
+An improved exponential-time algorithm for             <i>k</i>             -SAT
+Normal rank
@@ Property / cites work @@
+Relations Among Complexity Measures
@@ Property / cites work: Relations Among Complexity Measures / rank @@
+Normal rank
@@ Property / cites work @@
+On uniform circuit complexity
@@ Property / cites work: On uniform circuit complexity / rank @@
+Normal rank
@@ Property / cites work @@
+A Boolean function requiring 3n network size
@@ Property / cites work: A Boolean function requiring 3n network size / rank @@
+Normal rank
@@ Property / cites work @@
+Short propositional formulas represent nondeterministic computations
+Normal rank
@@ Property / cites work @@
+Q3826533
@@ Property / cites work: Q3826533 / rank @@
+Normal rank
@@ Property / cites work @@
+On O(Tlog T) reduction from RAM computations to satisfiability
+Normal rank
@@ Property / cites work @@
+On the power of small-depth threshold circuits
@@ Property / cites work: On the power of small-depth threshold circuits / rank @@
+Normal rank
@@ Property / cites work @@
+Searching for Primitive Roots in Finite Fields
@@ Property / cites work: Searching for Primitive Roots in Finite Fields / rank @@
+Normal rank
@@ Property / cites work @@
+Majority gates vs. general weighted threshold gates
+Normal rank
@@ Property / cites work @@
+Threshold circuits of bounded depth
@@ Property / cites work: Threshold circuits of bounded depth / rank @@
+Normal rank
@@ Property / cites work @@
+Nearly-linear size holographic proofs
@@ Property / cites work: Nearly-linear size holographic proofs / rank @@
+Normal rank
@@ Property / cites work @@
+On ACC
@@ Property / cites work: On ACC / rank @@
+Normal rank
@@ Property / cites work @@
+Q4393484
@@ Property / cites work: Q4393484 / rank @@
+Normal rank