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)
Related Items (39)
Bounds on 2-query locally testable codes with affine tests ⋮ An adaptivity hierarchy theorem for property testing ⋮ A query efficient non-adaptive long code test with perfect completeness ⋮ Testing list \(H\)-homomorphisms ⋮ Local Testing of Lattices ⋮ An Algebraic Characterization of Testable Boolean CSPs ⋮ On the benefits of adaptivity in property testing of dense graphs ⋮ On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing ⋮ Unnamed Item ⋮ Erasures versus errors in local decoding and property testing ⋮ 2-transitivity is insufficient for local testability ⋮ Hierarchy theorems for property testing ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Erasure-Resilient Property Testing ⋮ Algorithmic Aspects of Property Testing in the Dense Graphs Model ⋮ On the power of conditional samples in distribution testing ⋮ On the Query Complexity of Testing Orientations for Being Eulerian ⋮ Hierarchy Theorems for Property Testing ⋮ The power and limitations of uniform samples in testing properties of figures ⋮ Composition of semi-LTCs by two-wise tensor products ⋮ Symmetric LDPC codes and local testing ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Sparse affine-invariant linear codes are locally testable ⋮ 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 ⋮ Testing low-degree polynomials over prime fields ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ From Local to Robust Testing via Agreement Testing ⋮ A unified framework for testing linear‐invariant properties ⋮ Characterizations of locally testable linear- and affine-invariant families ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ A combination of testability and decodability by tensor products ⋮ Lower bounds for testing triangle-freeness in Boolean functions
This page was built for publication: Some 3CNF Properties Are Hard to Test
