[A&C seminar] Testing Odd-Cycle Freeness of Boolean Functions
Speaker: Elena Grigorescu , Georgia Tech
Date: April 25 2011
Time: 4:00PM to 5:15PM
Location: 32-G575
Host: Arnab Bhattacharyya, MIT
Contact: Arnab Bhattacharyya, 617-253-9302, abhatt@mit.edu
Relevant URL: http://people.csail.mit.edu/madry/algcompsem/
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. 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
See other events that are part of
See other events happening in April 2011
