Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- 5 June 2010
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 251-260
- https://doi.org/10.1145/1806689.1806725
Abstract
No abstract availableThis publication has 27 references indexed in Scilit:
- The PCP theorem by gap amplificationJournal of the ACM, 2007
- Invitation to data reduction and problem kernelizationACM SIGACT News, 2007
- Testing subgraphs in directed graphsJournal of Computer and System Sciences, 2004
- Simple analysis of graph tests for linearity and PCPRandom Structures & Algorithms, 2003
- Testing subgraphs in large graphsRandom Structures & Algorithms, 2002
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- Property testing and its connection to learning and approximationJournal of the ACM, 1998
- Matrix multiplication via arithmetic progressionsJournal of Symbolic Computation, 1990
- Some consequences of non-uniform conditions on uniform classesTheoretical Computer Science, 1983
- Intersection Theorems for Systems of SetsJournal of the London Mathematical Society, 1960