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