Tata Institute of Fundamental Research
Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
STCS Student Seminar
Speaker:
Santhoshini Velusamy (VSRP Student
Indian Institute of Technology
Chennai 600036)
Organiser:
Suhail Sherif
Date:
Friday, 16 Jun 2017, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
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
| Speaker: | Santhoshini Velusamy (VSRP Student Indian Institute of Technology Chennai 600036) |
| Organiser: | Suhail Sherif |
| Date: | Friday, 16 Jun 2017, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
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
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