Some 3CNF Properties Are Hard to Test

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)

zbMATH Keywords

lower bounds; property testing; locally testable codes; sublinear algorithms; CNF formulae

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Local Testing of Lattices, Erasure-Resilient Property Testing, Unnamed Item, 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, Unnamed Item, Unnamed Item, Unnamed Item, A unified framework for testing linear‐invariant properties, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, From Local to Robust Testing via Agreement Testing, Constant-Query Testability of Assignments to Constraint Satisfaction Problems, A combination of testability and decodability by tensor products, An Algebraic Characterization of Testable Boolean CSPs, Erasures versus errors in local decoding and property testing, 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, Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting), 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