Lesson plan
Property testing
Property testing is a field of theoretical computer science, concerned with the design of super-fast algorithms for approximate decision making, where the decision refers to properties or parameters of huge objects. A property testing algorithm for a decision problem is an algorithm whose query complexity (the number of queries made to its input) is much smaller than the instance size of the problem. Typically, property testing algorithms are used to determine whether some combinatorial structure (such as a graph or a boolean function) satisfies some property , or is "far" from having this property (meaning that an -fraction of the representation of must be modified to make satisfy ), using only a small number of "local" queries to the object. For example, the following promise problem admits an algorithm whose query complexity is independent of the instance size (for an arbitrary constant ): :"Given a graph on vertices, decide whether it is bipartite, or cannot be made bipartite even after removing an arbitrary subset of at most edges." Property testing algorithms are central to the definition of probabilistically checkable proofs, as a probabilistically checkable proof is essentially a proof that can be verified by a property testing algorithm.
Article summary
Property testing is a field of theoretical computer science, concerned with the design of super-fast algorithms for approximate decision making, where the decision refers to properties or parameters of huge objects. A property testing algorithm for a decision problem is an algorithm whose query complexity (the number of queries made to its input) is much smaller than the instance size of the problem. Typically, property testing algorithms are used to determine whether some combinatorial structure (such as a graph or a boolean function) satisfies some property , or is "far" from having this property (meaning that an -fraction of the representation of must be modified to make satisfy ), using only a small number of "local" queries to the object. For example, the following promise problem admits an algorithm whose query complexity is independent of the instance size (for an arbitrary constant ): :"Given a graph on vertices, decide whether it is bipartite, or cannot be made bipartite even after removing an arbitrary subset of at most edges." Property testing algorithms are central to the definition of probabilistically checkable proofs, as a probabilistically checkable proof is essentially a proof that can be verified by a property testing algorithm.
Key claims
- publication date: 1998 — source: Wikipedia · confidence 0.95
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- The record states that the publication date is "1998". What evidence would count against this claim?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
- Wikipedia https://en.wikipedia.org/w/index.php?oldid=1368880627
Key claims and bibliography are generated from the same tracked claims and sources as the article page.