- Series
- Combinatorics Seminar
- Time
- Friday, April 22, 2011 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Elena Grigorescu – College of Computing, Georgia Tech
- Organizer
- Xingxing Yu
In the Property Testing model an algorithm is required to distinguish between the
case that an object has a property or is far from having the property. Recently, there
has been a lot of interest in understanding which properties of Boolean functions
admit testers making only a constant number of queries, and a common theme
investigated in this context is linear invariance. A series of gradual results has
led to a conjectured characterization of all testable linear invariant properties.
Some of these results consider properties where the query upper bounds are towers of
exponentials of large height dependent on the distance parameter. A natural question
suggested by these bounds is whether there are non-trivial families with testers
making only a polynomial number of queries in the distance parameter.In this talk I
will focus on a particular linear-invariant property where this is indeed the
case: odd-cycle freeness.Informally, a Boolean function fon n variables is odd-cycle
free if there is no x_1, x_2, .., x_2k+1 satisfying f(x_i)=1 and sum_i x_i = 0.This
property is the Boolean function analogue of bipartiteness in the dense graph model.
I will discuss two testing algorithms for this property: the first relies on graph
eigenvalues considerations and the second on Fourier analytic techniques. I will
also mention several related open problems.
Based on joint work with Arnab Bhattacharyya, Prasad Raghavendra, Asaf Shapira