Some 3CNF Properties Are Hard to Test

DOI10.1137/S0097539704445445zbMATH Open1086.68045MaRDI QIDQ5700567FDOQ5700567

Authors: Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova 

Publication date: 28 October 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• Some 3CNF properties are hard to test
• Testing formula satisfaction
• Property testers for dense constraint satisfaction programs on finite domains
• Testing Read-Once Formula Satisfaction
• Linearity testing in characteristic two

zbMATH Keywords

lower boundsproperty testinglocally testable codessublinear algorithmsCNF formulae

Mathematics Subject Classification ID

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

Cited In (41)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Erasure-Resilient Property Testing
• Towards lower bounds on locally testable codes via density arguments
• Title not available (Why is that?)
• On the power of conditional samples in distribution testing
• Bounds on 2-query locally testable codes with affine tests
• Some 3CNF properties are hard to test
• An adaptivity hierarchy theorem for property testing
• A combination of testability and decodability by tensor products
• Hierarchy theorems for property testing
• Hierarchy theorems for property testing
• Erasures versus errors in local decoding and property testing
• On the benefits of adaptivity in property testing of dense graphs
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
• A unified framework for testing linear‐invariant properties
• A combinatorial characterization of smooth LTCs and applications
• Characterizations of locally testable linear- and affine-invariant families
• Symmetric LDPC codes and local testing
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Invariance in property testing
• Testing list \(H\)-homomorphisms
• An Algebraic Characterization of Testable Boolean CSPs
• From Local to Robust Testing via Agreement Testing
• Sparse affine-invariant linear codes are locally testable
• Title not available (Why is that?)
• Composition of semi-LTCs by two-wise tensor products
• Testing low-degree polynomials over prime fields
• Local Testing of Lattices
• Lower bounds for testing triangle-freeness in Boolean functions
• A query efficient non-adaptive long code test with perfect completeness
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• On the Query Complexity of Testing Orientations for Being Eulerian
• 2-transitivity is insufficient for local testability
• Testing formula satisfaction
• The power and limitations of uniform samples in testing properties of figures
• Constant-Query Testability of Assignments to Constraint Satisfaction Problems
• Symmetric LDPC codes and local testing
• Limitation on the Rate of Families of Locally Testable Codes
• Property testing of massively parametrized problems -- a survey

This page was built for publication: Some 3CNF Properties Are Hard to Test

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5700567)