Property Testing Workshop

  • Date/Time
    Date(s) - 17/06/2013 - 18/06/2013
    All Day

    Dan Carmel Hotel

    Categories No Categories

    Organizers: Eldar Fischer (CS Technion) and Ilan Newman (CS Haifa University)

    When trying to decide a whether an input satisfies a given property, the most common scenario is where most of the input has to be read to obtain enough information for determining the decision problem. Thus follows an almost trivial lower bound of Theta(n) on the time complexity of the deciding algorithm, where n is the input size.

    Property testing deals with a notion of approximation that many times has the effect of allowing an answer that does not require a full reading of the input. In its general setting, instead of deciding whether the input satisfies the property, it is deemed sufficient to accept any input that satisfies the property, while rejecting any input that is far from any alternative that satisfies the property. Such a testing algorithm has a "random read" (oracle) access to the input, and needs only to follow the above acceptance and rejection requirements with sufficiently high probability.

    Not having to read the entire input sometimes (but not always) also allows for sublinear time algorithms, algorithms whose running time is o(n). At times, instead of a gap decision problem as above, parameter approximation problems are considered, one example being approximating the actual distance of the input from the property, rather than merely distinguishing the two cases outlined above.

    Property testing first emerged for algebraic properties (such as a function being linear) in the context of proof and program verification, and about a decade later has entered the realm of combinatorial properties. The last two decades saw rapid growth in the investigation of property testing, including some recent classification results. Additional growth took place in related areas, such as sublinear time algorithms, approximation of properties of distributions through sampling, proofs of proximity, and other topics.

    The workshop's scope includes property testing, sublinear time algorithms, and their related topics.

    Program is available here


    This workshop is primarily funded by the European Research Council under the European Union's Seventh Framework Programme (FP/2007-2013), ERC grant agreement number 202405.







    Monday, June 17
    Welcoming address
    Eldar Fischer (CS, Technion)
    Ilan Newman (CS Haifa University)
    Session 1  
    Sofya Raskhodnikova (Pennsylvania State University)
    Gilad Tsur (Weizmann Institute of Science)
    11:00-11:30 Coffee Break
    Session 2  
    Optimal Testing of Multivariate Polynomials over Small Prime Fields
    Elad Haramati (Technion)
    On the Max-cut Problem
    Mario Szegedy (Rutgers University)
    Reut Levi (Tel-Aviv University)
    13:00-14:30 Lunch
    Session 3  
    Deterministic vs Non-deterministic Graph Property Testing
    Asaf Shapira (Tel-Aviv University)
    Yonatan Goldhirsh (Technion)
    15:30-16:00 Coffee Break
    Session 4  
    Arie Matsliah (Google)
    Eric Blais (Massachusetts Institute of Technology)
    Tuesday, June 18
    Session 5
    Christian Sohler (Technische Universität Dortmund)
    Ning Xie (Florida International University)
    11:00-11:30 Coffee Break
    Session 6  
    C. Seshadhri (Sandia National Laboratories)
    Local Decompression
    Ronitt Rubinfeld (Massachusetts Institute of Technology)
    Sourav Chakraborty (Chennai Mathematical Institute)
    13:00-14:30 Lunch
    Session 7  
    Dana Ron (Tel-Aviv University)
    Oded Goldreich (Weizmann Institute of Science)
    16:00-16:30 Coffee Break
    Session 8  
    16:30-17:30 Open problems session and closing address