Anup Bhattacharya - reading-group-sublinear

Reading Group on Sublinear Algorithms and Property Testing

We were organizing a weekly seminar series on sublinear algorithms and property testing.

Date/Time: 2-4 PM on Thursdays at ACMU Seminar Room (6th Floor)

Lecture 1 (22/08/2019): Introduction to Property Testing by Sourav Chakraborty. A good set of lecture notes on topics related to the reading group can be found here.

Lecture 2 (29/08/2019): Introduction to Streaming Algorithms by Arijit Bishnu (Slides)

Lecture 3 (05/09/2019): Introduction to Streaming Algorithms (continued from earlier lecture) by Gopinath Mishra (Slides)

Lecture 4 (12/09/2019): Sublinear Algorithms for (\Delta+1)-Coloring by Anup Bhattacharya. The talk will be based on this paper.

Lecture 5 (19/09/2019): Sampling Edges Almost Uniformly by Gopinath Mishra. The talk will be based on this paper.

Lecture 6 (24/10/2019): Anup Bhattacharya presented the paper "Optimal Quantile Approximation in Streams" by Zohar Karnin, Kevin Lang, Edo Liberty (FOCS 2016)

Lecture 7 (31/10/2019): Sourav Chakraborty presented the results of the paper "Property Testing Lower Bounds Via Communication Complexity".

Lecture 8 (14/11/2019): Sayantan Sen presented the paper "Sublinear Time Algorithms for Earth Mover's Distance".

Suggested papers for the reading group are as follows. We plan to keep on adding papers to this list.

Sublinear Algorithms for (∆ + 1) Vertex Coloring by Sepehr Assadi, Yu Chen, Sanjeev Khanna in (SODA 2019)
Testing Graph Clusterability: Algorithms and Lower Bounds by Chiplunkar et al. (FOCS 2018)
Finding forbidden minors in sublinear time by Akash Kumar, C. Seshadhri, and Andrew Stolman (FOCS) 2018
Heavy Hitters via Cluster-Preserving Clustering By Larsen et al. (FOCS 2016)
The Sketching Complexity of Graph and Hypergraph Counting by Kallaugher et al. (FOCS 2018)
Optimal Quantile Approximation in Streams by Zohar Karnin, Kevin Lang, Edo Liberty (FOCS 2016)
Perfect L_p Sampling in a Data Stream by Jayaram, Woodruff (FOCS 2018)
Towards Optimal Moment Estimation in Streaming and Distributed Models by Jayaram, Woodruff (Approx 2019)
New Notions and Constructions of Sparsification for Graphs and Hypergraphs by Bansal et al. (FOCS 2019)
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs by Assadi et al. (SODA'19)
Analyzing Graph Structure via Linear Measurements by Ahn et al. (SODA 2012)
An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube by Chakrabarty, Seshadhri (SICOMP 2016)
Optimal streaming and tracking distinct elements with high probability by Błasiok (SODA 2018)
Simple analyses of sparse Johnson-Lindenstrauss Lemma by Cohen et al. (SOSA 2018)
Continuous Monitoring of l_p Norms in Data Streams by Blasiok et al. (Approx-Random 2017)
Optimality of the Johnson-Lindenstrauss Lemma by Larsen and Nelson (FOCS 2017)
Active Learning a Convex Body in Low Dimensions by Har-Peled et al. (SOCG 2019)

Google Sites

Report abuse