Property Testing

• Regular algorithms: Read all the input and solve the problem.

• Property testing: Solve the problem by only reading a small part of the input.

• The concept of ε-farness:

  • ε: A constant threshold.
  • Is it possible to determine with a certain probability whether a given property is likely to hold or not (ε-far from the property)? Is this what property testing does?

• Why do property testing?

  • When data becomes huge, even polynomial time algorithms can be slow.
    • With property testing, it is possible to solve the problem in constant time or even linear time.
  • Even if the problem is NP-hard, there is a possibility that property testing can be done.
  • It can be used for pruning before solving the problem exactly (rejecting possibilities that are not feasible).

• Connections with other fields:

  • Approximation algorithms:
    • Approximation algorithms usually provide guarantees based on multiplication, such as “$0.878n”.
    • Property testing has a slightly different way of providing guarantees.
      • However, the techniques of property testing can be applied in some cases.
  • Distributed algorithms:
    • Distributed algorithms determine the output by randomly looking at a part of a Graph or other structures.
    • The approach is similar to property testing.

• Advantages of property testing:

  • The algorithms are simple, and the more difficult part is the analysis.
    • Experts can handle that.
  • It reveals the relationship between global/macro structures and local/micro structures.

• Property testing is studied for various subjects:

  • Monotonicity Property Testing
  • Testing Properties of Graphs
  • Goal: Obtain necessary and sufficient conditions for properties that can be solved in constant time.
    • Some research has succeeded (impressive).
    • However, since it is not possible to read all inputs in the first place, information-theoretic methods are used.

• (Master of Information Science)