Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, II piano
Aula C2

Abstract:
A property testing algorithm for a graph property P is an algorithm that, given access to the representation of a graph G, accepts with high probability if G has property P, rejects with high probability if G is ``epsilon-far'' from having property P (that is, one has to change an epsilon fraction of the representation of G in order to get the representation of a graph with property P), and may behave arbitrarily in all other cases. The complexity of a testing problem is very dependent on the representation being used, for example bipartiteness can be tested in time depending only on epsilon (specifically, in time about O(1/epsilon^2)) in the adjacency matrix representation, while it requires sqrt(n) time in the adjacency list representation, where n is the number of vertices.
We prove that every property tester for 3-coloring in bounded degree graphs in the adjacency list representation must look at Omega(n) entries in the representation of the graph. Our proof also shows that no sub-linear time approximation algorithm can approximate Max 3SAT to within a factor better than 7/8 (it was known that no polynomial-time algorithm could do so, unless P=NP, but our result is unconditional). We also show that no algorithm for checking bipartiteness in the adjacency matrix representation can have complexity o(1/epsilon^(1.5)), and that no non- adaptive algorithm can have complexity o(1/epsilon^2).

These results are joint work with Andrej Bogdanov and Kenji Obata