Property Testing of Massively Parametrized Problems – A Survey

DOI10.1007/978-3-642-16367-8_8zbMath1309.68227OpenAlexW1602276996MaRDI QIDQ4933366

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)

Related Items (10)

Proofs of proximity for context-free languages and read-once branching programs ⋮ Testing list \(H\)-homomorphisms ⋮ An Algebraic Characterization of Testable Boolean CSPs ⋮ Non-interactive proofs of proximity ⋮ TESTING FOR FORBIDDEN POSETS IN ORDERED ROOTED FORESTS ⋮ Unnamed Item ⋮ Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP ⋮ Short Locally Testable Codes and Proofs ⋮ A Brief Introduction to Property Testing ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Space complexity vs. query complexity
• On the strength of comparisons in property testing
• Regular Languages are Testable with a Constant Number of Queries
• Testing Membership in Languages that Have Small Width Branching Programs
• Property testing and its connection to learning and approximation
• An extremal function for contractions of graphs
• On the Query Complexity of Testing Orientations for Being Eulerian
• Monotonicity testing over general poset domains
• Testing st-Connectivity
• Testing properties of directed graphs: acyclicity and connectivity*
• Testing subgraphs in large graphs
• Transitive-Closure Spanners
• Some 3CNF Properties Are Hard to Test
• The PCP theorem by gap amplification

This page was built for publication: Property Testing of Massively Parametrized Problems – A Survey