CS Events Monthly View
Qualifying ExamGraph Streaming Lower Bounds via a Streaming XOR Lemma |
|
||
Friday, April 02, 2021, 03:00pm - 05:00pm |
|||
Speaker: Vishvajeet Nagargoje
Location : Remote via Zoom
Committee:
Prof. Swastik Kopparty (advisor)
Prof. Sepehr Assadi
Prof. Eric Allender
Prof. Sudarsun Kannan
Event Type: Qualifying Exam
Abstract: We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected or cycle-free versus being far from these properties. We develop a new lower bound technique that proves that for many problems of interest, including all the above, obtaining a (1 + ε)-approximation requires either near-linear space or Ω(1/ε) passes, even on highly restricted families of graphs such as bounded-degree planar graphs. For multiple of these problems, this bound matches those of existing algorithms and is thus (asymptotically) optimal.One key ingredient of our proofs is a simple streaming XOR Lemma, a generic hardness amplification result, that we prove: informally speaking, if a p-pass s-space streaming algorithm can only solve a decision problem with advantage δ > 0 over random guessing, then it cannot solve XOR of L independent copies of the problem with advantage much better than δ^L. This result can be of independent interest and useful for other streaming lower bounds as well.In this talk, I will be giving a brief overview of our results and techniques. Based on joint work with Prof. Sepehr Assadi.
: