Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

Speaker:
Santhoshini Velusamy
Organiser:
Suhail Sherif
Date:
Friday, 16 Jun 2017, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
Abstract
This paper is joint work with Venkatesan Guruswami and Ameya Vellingker, to appear in APPROX 17.

We studied the complexity of estimating the optimum value of a Boolean 2CSP (arity two constraint satisfaction problem) in the single-pass streaming setting, where the algorithm is presented the constraints in an arbitrary order. We give a streaming algorithm to estimate the optimum within a factor approaching 2/5 using logarithmic space, with high probability. This beats the trivial factor 1/4 estimate obtained by simply outputting 1/4 th of the total number of constraints.

The inspiration for our work is a lower bound of Kapralov, Khanna, and Sudan (SODA '15) who showed that a similar trivial estimate (of factor 1/2) is the best one can do for Max CUT. This lower bound implies that beating a factor 1/2 for Max 2CSP, in particular, to distinguish between the case when the optimum is m/2 versus when it is at most (1/4+ \eps) m, where m is the total number of constraints, requires polynomial space. We complement this hardness result by showing that one can distinguish between the case in which the optimum exceeds (1/2 + \eps)m and the case in which it is close to m/4.

We also prove that estimating the size of the maximum acyclic subgraph of a graph, when its edges are presented in a single-pass stream, within a factor better than 7/8 requires polynomial space.

In this talk, I'll present the main results of the paper. The proofs are quite simple and would not require any previous knowledge