Theoretical CS Reading Group

The reading group meets once a week usually, Friday 12-2pm 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 2014

Friday, 21th Nov 2014 — Theory Seminar - Prof. Robert McGrail, Bard College
CSPs and Connectedness: P/NP Dichotomy for Idempotent, Right Quasigroups

Click to view Abstract

In the 1990's, Jeavons showed that every finite algebra corresponds to a class of constraint satisfaction problems. Vardi later conjectured that idempotent algebras exhibit P/NP dichotomy: Every non NP-complete algebra in this class must be tractable. Here we discuss how tractability corresponds to connectivity in Cayley graphs. In particular, we show that dichotomy in finite idempotent, right quasigroups follows from a very strong notion of connectivity. Moreover, P/NP membership is first-order axiomatizable over involutory quandles

Friday, 7th Nov 2014 — Evolving Sets - II
Presenter: Akash Kumar

Friday, 31th Oct 2014 — Evolving Sets - I
Presenter: Akash Kumar

Friday, 24th Oct 2014 — Theory Seminar - Prof. Thanh Nguyen, Purdue
"Near Feasible Stable Matchings with Complementarities"

Click to view Abstract

The National Resident Matching program strives for a stable matching of medical students to teaching hospitals. With the presence of couples, stable matchings need not exist. For any student preferences, we show that each instance of a stable matching problem has a `nearby' instance with a stable matching. The nearby instance is obtained by perturbing the capacities of the hospitals. Our approach is general and applies to other type of complementarities, as well as matchings with side constraints and contracts. Joint work with Robert Vohra.

Friday, 17th Oct 2014 — Theory Seminar - Karthik Chandrasekaran, UIUC
Finding small stabilizers for unstable graphs

Click to view Abstract

An undirected graph G is stable if its inessential vertices (those that are exposed by at least one maximum matching) form a stable set. Stable graphs play an important role in cooperative game theory and network bargaining. In this talk, I will focus on the following edge-deletion problem: given a graph G, can we find a minimum cardinality subset of edges whose removal yields a stable graph? I will show that the removal of any such minimum cardinality subset of edges does not decrease the cardinality of the maximum matching in the graph. This insight will be used to show that the problem is vertex-cover hard and also to develop efficient approximation algorithms for sparse graphs and for regular graphs.
Based on joint work with Adrian Bock, Jochen Koenemann, Britta Peis and Laura Sanita.

Friday, 26th Sept 2014 — R. G. McKilliam and A. Grant, "Finding short vectors in a lattice of Voronoi's first kind"
Presenter: GV

Click to view Abstract

A polynomial time algorithm to solve the Shortest vector problem on a family of Lattices known as Voronoi's First Kind lattices.

Friday, 19th Sept 2014 — Buchbinder N, Feldman M, Naor J, et al. "Submodular Maximization with Cardinality Constraints"
Presenter: Peng Zhang

Click to view Abstract

The talk would be on approximation algorithms for (non-monotone) submodualr maximization with cardinality constraints.

Friday, 12th Sept 2014 — Yuchen Zhang, John C. Duchi, Michael I. Jordan, Martin J. Wainwright, "Information-theoretic lower bounds for distributed statistical estimation with communication constraints"
Presenter: Abhiram Natarajan

Click to view Abstract

The talk will be about the recent results on lower bounds for minimax risk in distributed statistical estimation problems with communication constraints. The focus would mostly be on the techniques which are used to obtain such lower bounds and will also cover the main results of the paper.

Friday, 5th Sept 2014 — J.H.Kim, V.H.Vu, "Sandwiching random graphs"
Presenter: Abram Manger

Click to view Abstract

The goal of this paper is to establish a connection between two classical models of random graphs: the random graph G(n, p) and the random regular graph G_d(n). This connection appears to be very useful in deriving properties of one model from the other. In particular, one immediately obtains one-line proofs of several highly non-trivial and recent results on G_d(n).