# 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

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"

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

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

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

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

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

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