Theoretical CS Reading Group

The reading group meets once a week usually, Monday 1:30-2:30pm to discuss a particular paper or topic.

Please join our mailing list to get notifications about the weekly meetings and discussions.

You might also be interested in the
Theory Seminar.

Fall 2017
Spring 2017
Fall 2016
Spring & Summer 2016
Fall 2015
Spring & Summer 2015
Fall 2014
Spring 2014
Summer & Fall 2013

Fall 2016

Wednesday, 24th August 2016 — John Kim, Swastik Kopparty
Decoding Reed-Muller codes over product sets
Presenter: GV

Friday, 9th September 2016 — Marc Bury, Chris Schwiegelshohn
Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
Presenter: Samson Zhou

Wednesday, 14th September 2016 — Peter S. Landweber, Emanuel A. Lazar, and Neel Patel
On Fiber Diameters of Continuous Maps
Presenter: Abhiram Natarajan

Click to view Abstract

A surprisingly short proof that for any continuous map f : R^n -> R^m, n > m, there exists no bound on the diameter of fibers of f will be presented. Moreover, it will also be shown that when m = 1, the union of small fi bers of f is bounded; and when m > 1, the union of small fibers need not be bounded.

Friday, 23rd September 2016 — Theory Seminar - Samson Zhou, Purdue University
Nearly Optimal Sparse Group Testing

Click to view Abstract

Group testing is the process of pooling arbitrary subsets from a set of n items so as to identify, with a minimal number of disjunctive tests, a ``small'' subset of d defective items. Motivated by physical considerations, we study group testing models in which the testing procedure is constrained to be ``sparse''. Specifically, we consider (separately) scenarios in which (a) items are finitely divisible and hence may participate in at most g tests; and (b) tests are size-constrained to pool no more than r items per test. For both scenarios we provide information-theoretic lower bounds on the number of tests required to guarantee high probability recovery. Based on joint work with Venkata Gandikota, Elena Grigorescu, Sidharth Jaggi.

Monday, 26th September 2016 — Theory Seminar - Minshen Zhu, Purdue University
FPTAS for Counting Proper Four Colorings on Cubic Graphs

Click to view Abstract

Graph coloring is arguably the most exhaustively studied problem in the area of approximate counting. It is conjectured that there is a fully polynomial-time (randomized) approximation scheme (FPTAS/FPRAS) for counting the number of proper colorings as long as q >= D + 1, where q is the number of colors and D is the maximum degree of the graph. This bound of q = D + 1 is the uniqueness threshold. However, the conjecture remained open even for any fixed D >= 3 (The cases of D = 1, 2 are trivial). In this paper, we provide an FPTAS for counting the number of 4-colorings on graphs with maximum degree of 3 and thus confirms the conjecture in the case of D = 3. This is the first time to achieve this optimal bound of q = D + 1. Previous, the best FPRAS is for q > 11/6 D and the best deterministic FPTAS is for q > 2.581D + 1 on general graphs. For the case of D = 3, the best previous result is an FPRAS for counting 5-colorings. We note that there is a barrier to go beyond q = D + 2 for Glauber dynamics based FPRAS and we overcome this by correlation decay approach. Moreover, we develop a couple of new techniques for the correlation decay approach which can find applications in other approximate counting problems. This is joint work with Xiang Peng.

Wednesday, 28th September 2016TCS+ Talk - Swastik Kopparty, Rutgers University
High rate locally-correctable codes and locally-testable codes with subpolynomial query complexity.

Friday, 30th September 2016 — Theory Seminar - Prof. Petros Drineas, Purdue University
A Randomized Rounding Algorithm for Sparse PCA

Click to view Abstract

We present and analyze a simple, two-step algorithm to approximate the optimal solution of the sparse PCA problem. Our approach first solves a L1 penalized version of the NP-hard sparse PCA optimization problem and then uses a randomized rounding strategy to sparsify the resulting dense solution. Our main theoretical result guarantees an additive error approximation and provides a tradeoff between sparsity and accuracy. Our experimental evaluation indicates that our approach is competitive in practice, even compared to state-of-the-art toolboxes such as Spasm.

Wednesday, 5th October 2016 — Theory Seminar - Prof. Elena Grigorescu, Purdue University
Testing K-monotonicity

Click to view Abstract

Boolean functions are commonly used to represent a diverse set of objects: voting schemes, graphs, error-correcting codes, or concept classes.

In this talk I will introduce Boolean k-monotone functions, which are functions defined over a finite poset domain D that alternate between the values 0 and 1 at most k times on any ascending chain in D. Hence, k-monotone functions are natural generalizations of the classical monotone functions, which are the 1-monotone functions.

We initiate a systematic study of k-monotone functions in the property testing model. In this model the goal is to distinguish functions that are k-monotone (or are close to being k-monotone) from functions that are far from being k-monotone. This work is motivated by the recent interest in k-monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing.

I will present several results for testing k-monotonicity on the hypercube and hypergrid domains, outline some connections with distribution testing and with some learning problems, and discuss a few important open questions. Joint work with Clement Canonne, Siyao Guo, Akash Kumar, Karl Wimmer.

Wednesday, 19th October 2016 — Theory Seminar - Prof. Sam Wagstaff, Purdue University
Complexity of Factoring and Primality Testing

Wednesday, 26th October 2016TCS+ Talk - Claire Mathieu, ENS
Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics

Wednesday, 2nd November 2016 — Ning Chen, Arpita Ghosh, and Sergei Vassilvitskii
Optimal Envy-Free Pricing with Metric Substitutability
Presenter: Young-San Lin

Wednesday, 9th November 2016 — Peter S. Landweber, Emanuel A. Lazar, and Neel Patel
Fast and Near-Optimal Algorithms for Approximating Distributions by Histograms
Presenter: Abhiram Natarajan

Monday, 21st November 2016 — Ryan O'Donnell
SOS is not obviously automatizable, even approximately
Presenter: Akash Kumar