Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses (Q5501928): Difference between revisions

@@ Property / cites work @@
+Random <i>k</i>‐SAT: Two Moments Suffice to Cross a Sharp Threshold
+Normal rank
@@ Property / cites work @@
+The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
+Normal rank
@@ Property / cites work @@
+Testing subgraphs in large graphs
@@ Property / cites work: Testing subgraphs in large graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient testing of large graphs
@@ Property / cites work: Efficient testing of large graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Testing Triangle-Freeness in General Graphs
@@ Property / cites work: Testing Triangle-Freeness in General Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Testing subgraphs in directed graphs
@@ Property / cites work: Testing subgraphs in directed graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002762
@@ Property / cites work: Q3002762 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5501357
@@ Property / cites work: Q5501357 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
+Normal rank
@@ Property / cites work @@
+Kernel(s) for problems with no kernel
@@ Property / cites work: Kernel(s) for problems with no kernel / rank @@
+Normal rank
@@ Property / cites work @@
+On problems without polynomial kernels
@@ Property / cites work: On problems without polynomial kernels / rank @@
+Normal rank
@@ Property / cites work @@
+Kernel Bounds for Disjoint Cycles and Disjoint Paths
+Normal rank
@@ Property / cites work @@
+Nondeterminism within $P^ *  $
@@ Property / cites work: Nondeterminism within $P^ * $ / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for kernelizations and other preprocessing procedures
+Normal rank
@@ Property / cites work @@
+Matrix multiplication via arithmetic progressions
@@ Property / cites work: Matrix multiplication via arithmetic progressions / rank @@
+Normal rank
@@ Property / cites work @@
+Improved bound for complexity of matrix multiplication
+Normal rank
@@ Property / cites work @@
+The PCP theorem by gap amplification
@@ Property / cites work: The PCP theorem by gap amplification / rank @@
+Normal rank
@@ Property / cites work @@
+Incompressibility through Colors and IDs
@@ Property / cites work: Incompressibility through Colors and IDs / rank @@
+Normal rank
@@ Property / cites work @@
+An improved construction of progression-free sets
@@ Property / cites work: An improved construction of progression-free sets / rank @@
+Normal rank
@@ Property / cites work @@
+Intersection Theorems for Systems of Sets
@@ Property / cites work: Intersection Theorems for Systems of Sets / rank @@
+Normal rank
@@ Property / cites work @@
+A generalization of Nemhauser and Trotter's local optimization theorem
+Normal rank
@@ Property / cites work @@
+Infeasibility of instance compression and succinct PCPs for NP
+Normal rank
@@ Property / cites work @@
+Sharp thresholds of graph properties, and the $k$-sat problem
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Property testing and its connection to learning and approximation
+Normal rank
@@ Property / cites work @@
+A Note on Elkin’s Improvement of Behrend’s Construction
+Normal rank
@@ Property / cites work @@
+On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
+Normal rank
@@ Property / cites work @@
+Simple analysis of graph tests for linearity and PCP
+Normal rank
@@ Property / cites work @@
+NONDETERMINISTICALLY SELECTIVE SETS
@@ Property / cites work: NONDETERMINISTICALLY SELECTIVE SETS / rank @@
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+On self-reducibility and weak P-selectivity
@@ Property / cites work: On self-reducibility and weak P-selectivity / rank @@
+Normal rank
@@ Property / cites work @@
+Point Line Cover
@@ Property / cites work: Point Line Cover / rank @@
+Normal rank
@@ Property / cites work @@
+Two Edge Modification Problems without Polynomial Kernels
+Normal rank
@@ Property / cites work @@
+Node-Deletion NP-Complete Problems
@@ Property / cites work: Node-Deletion NP-Complete Problems / rank @@
+Normal rank
@@ Property / cites work @@
+The node-deletion problem for hereditary properties is NP-complete
+Normal rank
@@ Property / cites work @@
+Q5710169
@@ Property / cites work: Q5710169 / rank @@
+Normal rank
@@ Property / cites work @@
+On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
+Normal rank
@@ Property / cites work @@
+Multiplying matrices faster than coppersmith-winograd
+Normal rank
@@ Property / cites work @@
+Q3762226
@@ Property / cites work: Q3762226 / rank @@
+Normal rank
@@ Property / cites work @@
+Some consequences of non-uniform conditions on uniform classes
+Normal rank