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

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.

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.

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

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

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.

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