Wed Sep 21	Minshen Zhu Purdue	TBD, 1:30-2:30pm. Title: 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. Based on joint work with Xiang Peng.
Fri Sep 23	Samson Zhou Purdue	TBD, 1:30-2:30pm. Title: Nearly Optimal Sparse Group Testing 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.
Fri Sep 30	Petros Drineas Purdue	LWSN 3102, 2-3pm Title: A Randomized Rounding Algorithm for Sparse PCA 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.
Wed Oct 5	Elena Grigorescu Purdue	LWSN 3102, 1-2pm Title: Testing K-Monotonicity 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.
Wed Oct 19	Sam Wagstaff Purdue	LWSN 3102, 1-2pm Title: Complexity of Factoring and Primality Testing Abstract:
Nov 2	Venkat Guruswami CMU	Krannert (part of Krannert colloquium) Title: Abstract:

Link to schedule for Fall 2015 . Spring 2015 , Fall 2014. Spring 2014, Fall 2013. Spring 2013. Fall 2012.