Seminar Series and Reading Group

List of talks in reserve chronological order

• Streaming lower bounds for MaxCut

  Speaker: Madhu Sudan

  Date: August 11, 2017.

  Time: 11:30am to 12:30pm.

  Venue: 105, New CC, first floor.

  [Abstract +]

  Abstract: Streaming algorithms consider the task of analyzing a large stream of data with limited memory. While the study of streaming algorithms for general data has seen lots of progress lately, study of graph data has lagged bahind. In this talk we explore the limits of estimating the size of the maximum "cut" (MaxCut), where a cut is simply a bipartition of the vertices and its size is the number of edges with one endpoint each on each side of the bipartition. The streaming model we consider is when the vertices of the graph are known, and edges appear in a stream one at a time. It is trivial to get a 2-approximation simply by counting the number of of edges in the graph. Approximation factors arbitrarily close to 1 can also be determined with memory roughly linear in the n, the number of vertices in the graph. Nothing better seems feasible. We report partial progress towards resolving the approximability of MaxCut. We show that a better than 2-approximation requires space sqrt{n}. And we show that in linear space the approximability is bounded away from 1. Our proof techniques rely on the analysis of some natural algorithms on random graphs and then the use of Fourier analysis to convert these to statements about all algorithms.
  
  Based on joint works with Michael Kapralov, Sanjeev Khanna and Ameya Velingker.




• Derandomizing Isolation Lemma: A geometric approach

  Speaker: Rohit Gurjar

  Date: July 31, 2017.

  Time: 2pm to 3pm.

  Venue: Conference Room, KreSIT, first floor.

  [Abstract +]

  We present a geometric approach towards derandomizing the Isolation lemma for a given family of subsets, i.e., deterministically constructing a weight assignment which ensures a unique minimum weight set in the family. The idea is to work with a polytope corresponding to the family of sets. In this talk, we present the approach in terms of general polytopes and describe a sufficient condition on the polytope for this approach to work. The approach gives a quasi-polynomially bounded weight assignment. Finally, we show that two specific families - perfect matchings in bipartite graphs and common base sets of two matroids - satisfy the required condition and thus, we get an isolating weight assignment for these cases. This also puts the two problems in quasi-NC. Based on joint works with Stephen Fenner and Thomas Thierauf.