EPFL

Algo+LMA

This shows you the differences between two versions of the page.

en:projects:details:mah02 [2010/09/13 16:30] 127.0.0.1 external edit |
en:projects:details:mah02 [2016/06/23 11:26] |
||
---|---|---|---|

Line 1: | Line 1: | ||

- | ---- dataentry project ---- | ||

- | title : Property Testing | ||

- | contactname: Mahdi Cheraghchi | ||

- | contactmail_mail: mahdi.cheraghchi@epfl.ch | ||

- | contacttel: 021 6931316 | ||

- | contactroom: BC 148 | ||

- | type : master thesis, master semester | ||

- | status : available | ||

- | table : projects | ||

- | created_dt : 2009-01-01 | ||

- | taken_dt : | ||

- | completed_dt : | ||

- | by : | ||

- | output_media : | ||

- | ====== | ||

- | template:datatemplates:project | ||

- | ---- | ||

- | |||

- | Let P be a property over a family of discrete objects which is true for some of the objects and false | ||

- | for the others. For example, the family can be the set of all undirected graphs over a fixed set of | ||

- | vertices, and the property can be the existence of a triangle, i.e., a subset of three mutually-connected | ||

- | vertices. The property testing problem is the following: Given a member of the family, decide whether | ||

- | it satisfies the property P or is far from satisfying P. | ||

- | |||

- | In general the complexity of the problem highly depends on the particular property in question, | ||

- | and so many problems can be regarded as an instance of the property testing problem. However, in | ||

- | almost all interesting situations, one aims to develop a reliable procedure for testing a particular | ||

- | property that is as efficient as possible and only looks at a small fraction of the bit-representation | ||

- | of the given object. Because of the fact that reading the input is costly and the tester can only read | ||

- | a small portion of the input, property testers are almost always randomized, as otherwise an adversary | ||

- | can produce an input object that hides the property in the portion of the input that is never examined | ||

- | by the tester. Also the tester is often allowed to err with some small probability over the choice of its | ||

- | internal coin flips because of the same reason. | ||

- | Therefore, a more precise and common formulation | ||

- | defines a property tester as a randomized procedure that: | ||

- | * Accepts all the objects that satisfy P with probability one (perfect completeness) or very close to one. | ||

- | * Rejects all the objects that are far from satisfying P, with high probability (soundness). | ||

- | * Does not read more than q bits of the input, for some small (ideally constant) q. | ||

- | * Runs in time polynomial (ideally sublinear) in the length of the input. | ||

- | The goal of this project, which is a purely theoretical project, is to study several settings of the | ||

- | property testing problem. It will include testing combinatorial properties (e.g., properties in graphs) | ||

- | as well as certain algebraic properties (e.g., testing whether a functionn computes a low-degree | ||

- | polynomial). A fair amount of mathematical maturity and basic knowledge of elementary notions in | ||

- | algebra (e.g., polynomials, finite fields, etc) and probability is required for the project. Understanding | ||

- | of the basic notions can also be acquired during the course of the project. | ||