Mysore Park Theory Workshop 2012

List of Talks (with abstracts)

Manindra Agrawal (IIT Kanpur)
Tutorial: Arithmetic Complexity and Polynomial Identity Testing [ pdf ]
Deeparnab Chakrabarty (Microsoft Research India)
Tutorial: A Few Vignettes from Algorithmic Game Theory and Economics. [ pdf ]

Abstract: The past decade has seen an explosion of work in the field that is now called Algorithmic Game Theory and Economics (AGT/E). This has, for good reason, coincided with the explosive rise of the Internet. Over the years, the field has chalked out definitive sub-areas while some nascent sub-areas are still maturing. In this talk, I will try to describe some of these areas, try to point out the challenging questions which have been left unanswered, and ponder on what the future might hold.
Sourav Chakraborty (Chennai Mathematical Institute)
Tutorial: Introduction to Property Testing [ pdf ]

Abstract: When we want to answer is a given input has a certain property often reading/accessing the full input is very costly or even impossible. In such cases one has to make intelligent decisions by reading only a very small fraction of the input. Usually this means one cannot give the correct answer always - a certain amount of error cannot be removed. Property testing is the subject of answering whether a given input satisfies a particular property by looking at a small (usually constant) part of the input. The property testing algorithms are usually randomized. Moreover the algorithms are allowed to make mistakes for certain kind of inputs - like when the input does not satisfy the property but yet is very close to satisfying the property.
This subject is kind of related to statistical analysis. Property of combinatorial objects or Boolean functions started in the early nineties by the works of Sudan-Rubinfeld, Blum-Luby-Rubinfeld and Goldreich-Goldwasser-Ron. In the past two decades lot of progress has been made in this field and many connections to other fields of computer science have been observed. In this talk I will present a overview on the subject of property testing by looking at various properties and their testing algorithms and some classic results in this field.
Sourav Chakraborty (Chennai Mathematical Institute)
Testing of Boolean Function Isomorphism [ pdf ]

Abstract: Testing Isomorphism among various objects is a very important problem is Computer Science. We consider the problem of testing the property: whether two given functions are isomorphic under permutation of the inputs. In other words we want to check if two Boolean functions are same up to a relabeling of it inputs variables or are they "far" from having this property. We want to test it by looking at a very small number of bits of the truth-table. It is one of the most well studied problem in Property Testing and in the past couple of year we have made significant progress in understanding the problem.
We can now give non-trivial upper bounds and lower bounds on the query complexity for testing isomorphism for various classes of Boolean functions. Other function properties - like dictatorship - can be framed as a Boolean function isomorphism problem. Hence our new results on function isomorphism also helps to understand various other function properties. We will look at various of these recent results. Most of these are from joint works with Noga Alon, Eric Blais, Eldar Fischer, David Garcia Sariano and Arie Mastliah.
Jugal Garg (IIT Bombay)
Linear Complementarity Problem and Market Equilibria [ pdf ]

Abstract:Linear complementarity problems (LCPs) arise in engineering, economics and optimization due to their ability to capture interesting cases of quadratic programming: Not only are LCPs powerful enough to capture tractable problems such as linear programming and convex quadratic programming, several hard problems such as Nash-Equilibrium in 2-player games and Knapsack can also be formulated as LCPs. In spite of their ability to capture very general problems, there is a rich mathematical theory around it: in particular a method due to Lemke which is aimed at solving any LCP. The trouble with Lemke's method is that it may not terminate in general, let alone in polynomial time and, hence, can be dismissed at a first glance. However, I will show that for the problem of computing equilibrium prices in several markets, for which one can derive LCP-like formulations, the insights from this machinery can be used to obtain novel structural and complexity-theoretic results and, surprisingly, extremely efficient algorithms in various settings.
No background in either LCPs or market equilibrium will be assumed.
This talk is based on joint works with Ruta Mehta, Milind Sohoni, Vijay Vazirani and Nisheeth Vishnoi.
Naveen Garg (IIT Delhi)
The Santa Claus Problem [ pptx ]

Abstract: The Santa Claus problem is the problem of giving gifts to children so that the happiness of the most unhappy child is maximised. A gift , i, is sought only by a subset of the children and gives happiness h_i to all children in the subset. The total happiness of a child is the sum of the happiness of all the gifts received by the child.
Asadpour et.al. showed that a natural LP-relaxation for this problem has a integrality gap of 1/4. This proof, however, did not provide a polynomial time algorithm for the problem. In a recent paper Polacek & Svensson give a simple quasi-polynomial time 4-approximation algorithm and I will be presenting this result.Lukas Polacek, Ola Svensson: Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
Vipul Goyal (Microsoft Research India)
Constructing Non-Malleable Commitments [ ppt ]

Abstract: Non-malleable commitments are a fundamental building block in cryptography. They are useful in preventing man-in-the-middle attacks in a variety of scenarios like secure auctions etc.
We provide the first constant round constructions of non-malleable commitment based only on one-way functions. This improves upon several previous (incomparable) works which required either: (a) super-constant number of rounds, or, (b) non-standard or sub-exponential complexity assumptions, or, (c) PCPs and collision resistant hash functions. Such a construction has a variety of applications towards constructing secure cryptographic protocols. We also outline a recent idea to improve the efficiency of the scheme and make it “black-box”.
In this talk, I will provide some background and motivation for non-malleable commitments and then explain the basic idea behind our new technique.
Parts of this work have appeared in FOCS 2012 and STOC 2011
Venkat Guruswami (Carnegie Mellon University)
Tutorial: Introduction to Lasserre hierarchy and its use in (approximate) combinatorial optimization
Venkat Guruswami (Carnegie Mellon University)
Lasserre hierarchy, higher eigenvalues, and graph partitioning [ pptx ]

Abstract: Partitioning the vertices of a graph into two (roughly) equal parts to minimize the weight of edges cut is a fundamental optimization problem, arising in diverse applications. Despite intense research, there remains a huge gap in our understanding of the approximability of these problems: the best algorithms achieve a super-constant approximation factor, whereas even a factor 1.1 approximation is not known to be NP-hard.
We describe an approximation scheme for various graph partitioning problems such as sparsest cut, minimum bisection, and small set expansion. Specifically, we give an algorithm running in time n^{O_epsilon(r)} with approximation ratio (1+epsilon)/min(1,lambda_r), where lambda_r is the r'th smallest eigenvalue of the normalized graph Laplacian matrix. This perhaps indicates why even showing very weak hardness for these problems has been elusive, since the reduction must produce hard instances with slowly growing spectra.
Our algorithm is based on a rounding procedure for semidefinite programming relaxations from a strong class called the Lasserre hierarchy. The analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix.
Our methods apply more broadly to optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes other notorious problems such as Unique Games, which we again show to be easy when the normalized Laplacian doesn't have too many small eigenvalues.
Joint work with Ali Kemal Sinop.
Ruta Mehta (IIT Bombay)
Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm [ pdf ]

Abstract: Given a rank-1 two-player finite (bimatrix) game (A,B), i.e., where rank(A+B)=1, we construct a suitable linear subspace of the rank-1 game space and show that this subspace is homeomorphic to its Nash equilibrium correspondence. Using this homeomorphism, we give the first polynomial time algorithm for computing an exact Nash equilibrium of a rank-1 bimatrix game. This settles an open question posed by Kannan and Theobald (SODA'07). In addition, we give a novel algorithm to enumerate all the Nash equilibria of a rank-1 game and show that a similar technique may also be applied to find a Nash equilibrium of any bimatrix game. Our approach also provides new proofs of important classical results such as the existence and oddness of Nash equilibria, and the index theorem (Shapley'74) for bimatrix games. Further, we extend the rank-1 homeomorphism result to a fixed rank game space, and give a fixed point formulation on [0,1]^k for solving a rank-k game. The homeomorphism maps and the fixed point formulation are piece-wise linear but considerably simpler than classical constructions.
Chandan Saha (Max Planck Institute for Informatics)
Identity testing and lower bounds using algebraic independence [ pdf ]

Abstract: A polynomial in many variables, when written down verbosely as a sum of monomials, might have a humongous expression. Arithmetic circuits, on the other hand, provide a succinct way to represent multivariate polynomials. An arithmetic circuit, consisting of addition and multiplication gates, takes several variables as input and outputs a polynomial in those variables. The study of arithmetic circuits - as to which algorithmic questions on polynomials can be resolved efficiently in this model of computation, and which polynomials do not admit any polynomial-sized circuit representation (lower bounds) - form the foundation of algebraic complexity theory.
One particular algorithmic question, the problem of 'polynomial identity testing' (PIT), occupies a pivotal position in the theory of arithmetic circuit complexity. It is the problem of deciding if the output of a given arithmetic circuit is an identically zero polynomial.
This talk will be about a single, common tool that strictly subsumes ALL known cases of polynomial-time (blackbox) PIT that have been hitherto solved using diverse tools and techniques. This tool is based upon the theme of algebraic independence & the Jacobian.
The same Jacobian based approach can be used to prove exponential lower bounds for the same circuit models for which PIT algorithms are given. This reinforces the intimate connection between identity testing and lower bounds by exhibiting a concrete mathematical tool - the Jacobian - that is equally effective in solving both the problems on certain interesting and previously well-investigated (but not quite well understood) models of computations.
This is a joint work with Manindra Agrawal, Nitin Saxena and Ramprasad Saptharishi.
Nikhil Srivastava (Microsoft Research India)
Tutorial: Spectral Sparsification of Graphs and Matrices, with Applications

Abstract: We begin by studying the following question: given a weighted graph G=(V,E,w), is there a weighted graph H=(V,F,w'), on the same set of vertices as G, which (1) is sparse, i.e., |F|<<|E|, ideally F=O(n); and (2) approximates G in some well-defined sense? There are many reasonable notions of approximation, for instance approximating the weights of all cuts w(S,V-S) (Benczur and Karger) and approximating all pairwise shortest path distances d(u,v) between vertices u,v \in V (Chew). We consider a spectral notion of approximation introduced by Spielman and Teng, which subsumes the cut notion and is motivated by applications to solving linear systems arising from graphs.
We show that every graph has a spectral approximation with O(n\log n) edges which may be found in nearly linear time, and a nearly optimal one with O(n) edges which may be found in poly(n) time. These results are special cases of more general theorems in linear algebra which say that a sum of rank one symmetric matrices can always be approximated by a sparse sum.
We then survey recent developments in this area -- for instance faster/streaming algorithms, generalizations to higher rank matrices -- as well as applications of the theorems and techniques to other areas -- numerical linear algebra, metric embeddings, and probability theory.
Kavitha Telikepalli (TIFR)
Popular Matchings [ pdf ]

Abstract: Given a graph G = (V,E) where each vertex has a strict ranking of its neighbors, the problem is to compute a matching M in G that is "popular". Such matchings always exist when G is bipartite, a simple linear time algorithm to compute a maximum cardinality such matching is presented here. For general graphs G, there is always a matching that is not very unpopular and such a matching can be computed in linear time.