Algorithms and Complexity Seminar
Testing Odd-Cycle Freeness of Boolean Functions
Elena Grigorescu (Georgia Tech)
In the Property Testing model an algorithm is required to distinguish between the case
that an objecthas a property or is far from having the property. One of the main
questions in the area has been that of characterizing the properties that are testable
with a constant number of queries. Kaufman and Sudan suggested that linear invariance
plays a key role in testing algebraic families. Indeed, linear invariance has been
explicitly exploited in recent studies of properties of Boolean functions.
A natural question that emerged from this line of work is whether there are non-trivial
Boolean families with testers making only a polynomial number of queries.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 for any k there is no x_1, x_2, .., x_2k+1 with f(x_i)=1 and sum 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 eigenvalue
considerations and the second uses Fourier analytic techniques. I will also mention
several related open problems.
Based on joint work with Arnab Bhattacharyya, Prasad Raghavendra,Asaf Shapira