Some 3CNF Properties Are Hard to Test
- 1 January 2005
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 35 (1), 1-21
- https://doi.org/10.1137/s0097539704445445
Abstract
No abstract availableThis publication has 12 references indexed in Scilit:
- Testing graphs for colorability properties*Random Structures & Algorithms, 2004
- Functions that have read-twice constant width branching programs are not necessarily testableRandom Structures & Algorithms, 2004
- Testing satisfiabilityJournal of Algorithms, 2003
- Three theorems regarding testing graph propertiesRandom Structures & Algorithms, 2003
- Property Testing in Bounded Degree GraphsAlgorithmica, 2002
- Regular Languages are Testable with a Constant Number of QueriesSIAM Journal on Computing, 2001
- Efficient Testing of Large GraphsCombinatorica, 2000
- Property testing and its connection to learning and approximationJournal of the ACM, 1998
- Randomized AlgorithmsPublished by Cambridge University Press (CUP) ,1995
- Many hard examples for resolutionJournal of the ACM, 1988