Property testing. Current research and surveys

DOI10.1007/978-3-642-16367-8zbMATH Open1197.68012OpenAlexW4255563008WikidataQ105583383 ScholiaQ105583383MaRDI QIDQ708444FDOQ708444

Authors:

Publication date: 12 October 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Randomized algorithms (68W20) Collections of articles of miscellaneous specific interest (00B15) Approximation algorithms (68W25) Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited In (27)

• Almost optimal distribution-free junta testing
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Subgaussianity is hereditarily determined
• Testing for forbidden posets in ordered rooted forests
• Non-interactive proofs of proximity
• Estimating parameters associated with monotone properties
• An adaptivity hierarchy theorem for property testing
• Testing probability distributions using conditional samples
• Planar graphs: random walks and bipartiteness testing
• A survey of challenges for runtime verification from advanced application domains (beyond software)
• On one-sided testing affine subspaces
• The subgraph testing model
• Exponentially improved algorithms and lower bounds for testing signed majorities
• A characterization of constant-sample testable properties
• Property testing lower bounds via communication complexity
• A chasm between identity and equivalence testing with conditional queries
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
• Deterministic vs non-deterministic graph property testing
• Testing outerplanarity of bounded degree graphs
• An optimal tester for \(k\)-Linear
• Almost Optimal Testers for Concise Representations.
• Non-deterministic graph property testing
• Learning \(k\)-modal distributions via testing
• Title not available (Why is that?)
• The power and limitations of uniform samples in testing properties of figures
• Partially symmetric functions are efficiently isomorphism testable
• Big data on the rise? Testing monotonicity of distributions

This page was built for publication: Property testing. Current research and surveys

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