# 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. |

Spring 2019 Fall 2018 Spring 2018 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 2016** —
TCS+ 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 2016** —
TCS+ 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