Differences

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.