Differences

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

Link to this comparison view

en:projects:details:mah02 [2009/06/05 23:14]
cangiani
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.