[Busec] Tuesday Oded Goldreich at MIT

Sharon Goldberg goldbe at cs.bu.edu
Sat Sep 17 10:20:47 EDT 2011

A talk by Oded Goldreich (but not about crypto):

---------- Forwarded message ----------
From: Be Blackburn <be at csail.mit.edu>
Date: Sat, Sep 17, 2011 at 10:18 AM
Subject: [Theory-seminars] Tuesday's TOC COlloq w/Oded Goldreich
To: theory-seminars at csail.mit.edu

The Next TOC Colloquium
                                      Open to the public

A Property Testing Double-Feature of Short Talks

Speaker: Oded Goldreich, Weizmann Institute of Science, Israel
Date:      Tuesday, September 20 2011
Time:      4:15PM to 5:15PM
Snacks:   3:45PM in 32-G5 RSA lounge
Location: 32-124
Host:       Dana Moshkovitz, CSAIL, MIT


I will present two overview talks on the subject of property testing,
preceeded by a brief introduction to the area. Abstracts of the two
corresponding works, follow.

1. Testing Graph Blow-Up (joint work with Lidor Avigad)
Referring to the query complexity of testing graph properties in the
adjacency matrix model, we advance the study of the class of
properties that can be tested non-adaptively within complexity that is
inversely proportional to the proximity parameter. Arguably, this is
the lowest meaningful complexity class in this model, and we show that
it contains a very natural class of graph properties. Specifically,
for every fixed graph $H$, we consider the set of all graphs that are
obtained by a (possibly unbalanced) blow-up of $H$.

2. Proximity Oblivious Testing and the Role of Invariances (joint work
with Tali Kaufman)
We present a general notion of properties that are characterized by
local conditions that are invariant under a sufficiently rich class of
symmetries. Our framework generalizes two popular models of testing
graph properties as well as the algebraic invariances studied by
Kaufman and Sudan (STOC'08). Our focus is on the case that the
property is characterized by a constant number of local conditions and
a rich set of invariances. We show that, in the aforementioned models
of testing graph properties, characterization by such invariant local
conditions is closely related to proximity oblivious testing (as
defined by Goldreich and Ron, STOC'09). In contrast to this relation,
we show that, in general, characterization by invariant local
conditions is neither necessary nor sufficient for proximity oblivious

Theory-seminars mailing list
Theory-seminars at lists.csail.mit.edu

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list