Some 3CNF Properties Are Hard to Test
From MaRDI portal
Publication:5700567
DOI10.1137/S0097539704445445zbMath1086.68045MaRDI QIDQ5700567
Prahladh Harsha, Sofya Raskhodnikova, Eli Ben-Sasson
Publication date: 28 October 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Local Testing of Lattices, Erasure-Resilient Property Testing, Algorithmic Aspects of Property Testing in the Dense Graphs Model, Hierarchy Theorems for Property Testing, Limitation on the Rate of Families of Locally Testable Codes, Property Testing of Massively Parametrized Problems – A Survey, Invariance in Property Testing, Symmetric LDPC Codes and Local Testing, A unified framework for testing linear‐invariant properties, A combination of testability and decodability by tensor products, An Algebraic Characterization of Testable Boolean CSPs, Bounds on 2-query locally testable codes with affine tests, Testing list \(H\)-homomorphisms, Hierarchy theorems for property testing, Composition of semi-LTCs by two-wise tensor products, Symmetric LDPC codes and local testing, On the benefits of adaptivity in property testing of dense graphs, The power and limitations of uniform samples in testing properties of figures, Towards lower bounds on locally testable codes via density arguments, Characterizations of locally testable linear- and affine-invariant families, An adaptivity hierarchy theorem for property testing, 2-transitivity is insufficient for local testability, Sparse affine-invariant linear codes are locally testable, Lower bounds for testing triangle-freeness in Boolean functions, A combinatorial characterization of smooth LTCs and applications, On the power of conditional samples in distribution testing, Testing low-degree polynomials over prime fields, Limits on the Rate of Locally Testable Affine-Invariant Codes, A query efficient non-adaptive long code test with perfect completeness, On the Query Complexity of Testing Orientations for Being Eulerian
