Property testing of massively parametrized problems -- a survey

DOI10.1007/978-3-642-16367-8_8MaRDI QIDQ4933366zbMATH OpenOpenAlexFDO

Authors Ilan Newman

Publication date 12 October 2010

Published in Property Testing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16367-8_8

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 1241385
• Three theorems regarding testing graph properties
• scientific article; zbMATH DE number 1792102
• Property testing and its connection to learning and approximation
• Property testing. Problems and techniques

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• An extremal function for contractions of graphs
• Monotonicity testing over general poset domains
• On the Query Complexity of Testing Orientations for Being Eulerian
• On the strength of comparisons in property testing
• Property testing and its connection to learning and approximation
• Regular languages are testable with a constant number of queries
• Some 3CNF Properties Are Hard to Test
• Space complexity vs. query complexity
• Testing Membership in Languages that Have Small Width Branching Programs
• Testing properties of directed graphs: acyclicity and connectivity*
• Testing st-Connectivity
• Testing subgraphs in large graphs
• The PCP theorem by gap amplification
• Transitive-closure spanners

Cited in

(10)

• An algebraic characterization of testable Boolean CSPs
• Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
• Non-interactive proofs of proximity
• Testing for forbidden posets in ordered rooted forests
• Constant-query testability of assignments to constraint satisfaction problems
• Proofs of proximity for context-free languages and read-once branching programs
• A Brief Introduction to Property Testing
• The subgraph testing model
• Short locally testable codes and proofs
• Testing list H-homomorphisms

This page was built for publication: Property testing of massively parametrized problems -- a survey

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