CS Events

Qualifying Exam

Graph Streaming Lower Bounds via a Streaming XOR Lemma


Download as iCal file

Friday, April 02, 2021, 03:00pm - 05:00pm


Speaker: Vishvajeet Nagargoje

Location : Remote via Zoom


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.


Join Zoom Meeting

Join by SIP
This email address is being protected from spambots. You need JavaScript enabled to view it.

Meeting ID: 993 2925 6107
Password: 770937

One tap mobile
+13126266799,,99329256107#,,,,0#,,770937# US (Chicago)
+16465588656,,99329256107#,,,,0#,,770937# US (New York)

Join By Phone
+1 312 626 6799 US (Chicago)
+1 646 558 8656 US (New York)
+1 301 715 8592 US (Washington DC)
+1 346 248 7799 US (Houston)
+1 669 900 9128 US (San Jose)
+1 253 215 8782 US (Tacoma)
Meeting ID: 993 2925 6107
Password: 770937
Find your local number: https://rutgers.zoom.us/u/ak9bbRyYg

Join by Skype for Business