Mysore Park Theory Workshop 2016

List of Talk Titles and Abstracts

Speaker:Anima Anandkumar

Title of Talk: Guaranteed Non-convex Learning Algorithms through Tensor Decomposition

Astract: Most learning problems can be cast as optimization tasks which are non-convex. Developing fast and guaranteed approaches for solving non-convex problems is a grand challenge. I will show how spectral optimization can reach the globally optimal solution for many learning problems despite being non-convex. This includes unsupervised learning of latent variable models, training neural networks and reinforcement learning of partially observable Markov decision processes. It involves spectral decomposition of moment matrices and tensors. Tensors are rich structures that can encode higher order relationships in data. In practice, tensor methods yield enormous gains both in running times and learning accuracy over traditional methods such as variational inference. Recent experiments also show gains in atari game play by incorporating hidden environment variables. I will also address other issues that arise in nonconvex optimization such as saddle points. These positive results demonstrate that many challenging learning tasks can be solved with guarantees using efficient non-convex approaches.
Speaker:Sayan Bhattacharya

Title of Talk: Design of dynamic algorithms via primal-dual method.

Astract: The primal-dual method is a general technique that is widely used to design efficient (static) algorithms for optimization problems. We present the first application of this technique in a dynamic setting.
We consider the problem of maintaining an approximately maximum matching in a dynamic graph. Specifically, we have an input graph G = (V, E) with n nodes. The node-set of the graph remains unchanged over time, but the edge-set is dynamic. At each time-step an adversary either inserts an edge into the graph, or deletes an already existing edge from the graph. The goal is to maintain a matching of approximately maximum size in G with small update time.
We present a clean primal-dual algorithm for this problem that maintains a (2+\epsilon)-approximate maximum fractional matching in O(\log n/\epsilon^2) amortized update time. We also describe several extensions to this basic framework, which allow us to obtain new efficient dynamic algorithms for maintaining a (2+\epsilon)-approximate maximum integral matching and f-approximate minimum set cover (where f denotes the maximum frequency of an element).
Joint work with M. Henzinger, G. F. Italiano [SODA' 15, ICALP' 15] and M. Henzinger, D. Nanongkai [STOC' 16].
Speaker:Eshan Chattopadhyay

Title of Talk: Explicit Constructions of Two-Source Extractors

Astract: Randomness is widely used in various areas of computer science, and many of the applications require uniform, uncorrelated bit. However, most sources of randomness in nature are defective and at best, only contain some amount of entropy. This leads to the area of randomness extraction, where an extractor is a deterministic procedure to produce pure random bits from a weak source. A central problem in this area is to extract from 2 independent weak sources(it is known that it is impossible to extract from just 1 weak source). This problem was raised by Chor and Goldreich, and Santha and Vazirani in the 80's.
In joint work with David Zuckerman, we resolve this problem. I will discuss the main ideas we use to solve this problem. Some of the ingredients that we use interestingly arise from cryptography and distributed computing.
As a corollary of our 2-source extractor, we obtain explicit constructions of Ramsey graphs within quasi-polynomial factors of the existential bound proved by Erdos in 1947, in his seminal paper introducing the probabilistic method. This is in a line of work spanning the last 67 years in an attempt to meet Erdos' challenge of matching the probabilistic bound.
Speaker:Anirban Dasgupta

Title of Talk: Approximate Modularity

Astract: A set function on a ground set of size n is approximately modular if it satisfies every modularity requirement to within an additive error;approximate modularity is the set analog of approximate linearity. In this work we study how close, in additive error, can approximately modular functions be to truly modular functions. While approximately linear functions have been extensively studied in the literature, there has been no study on approximate modularity to the best of our knowledge.
We first obtain polynomial time algorithms that, given any approximately modular function, reconstructs a modular function that is O(n^1/2) close. We also show an almost matching lower bound. In a striking contrast to these near-tight computational reconstruction bounds, we then show that for any approximately modular function, there exists a modular function that is O(log n)-close.
Joint work with Flavio Chiericetti, Abhimanyu Das, Ravi Kumar in Proceedings of FOCS 2015
Speaker:Samir Datta

Title of Talk: Dynamic Complexity: the import of old ideas

Astract: Dynamic complexity studies the computational complexity of updates for maintaining a property when there are 'small' changes in the input. Typical properties include reachability and perfect matching.
Traditionally, it has been a subfield of descriptive complexity and therefore logic. Recently the area has been viewed from the vantage point of circuit complexity revealing new connections with areas such as randomised algorithms and linear algebra. The consequent import of techniques has enabled the resolution of a long standing conjecture in the field. The hope is that further techniques from these more active fields will help resolve the open questions that abound Dynamic Complexity.
This talk will focus on some upper bound results that have appeared in the past couple of years and will touch upon open questions that need resolution.
Speaker: Amit Deshpande

Title of Talk: An interplay of SVD and k-means

Astract: Low-rank matrix approximation by SVD (Singular Value Decomposition) and clustering by k-means are two indispensable tools in any data science toolkit. Leveraging randomized algorithms and sampling techniques makes them applicable even to big data with provable guarantees (e.g., Stochastic SVD and k-means++). I'll survey some recent randomized algorithms and dimension reduction results to highlight an interplay of ideas used in these two problems.
Speaker: Rohit Gurjar

Title of Talk: Bipartite matching is in quasi-NC

Astract: We show that the bipartite perfect matching problem is in quasi-NC2. That is, it has uniform circuits of quasi-polynomial size and O(log2n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.
Speaker:Prahladh Harsha

Title of Talk: On polynomial approximations to AC0

Astract: In this talk, we will survey questions related to polynomial approximations of AC0. A classic result due to Tarui (1991) and Beigel, Reingold, and Spielman (1991), that any AC0 circuit of size s and depth d has an ε--error probabilistic polynomial over the reals of degree (log(s/ε)))^{O(d)}. We will have a re-look at this construction and show how to improve the bound to (log s)^{O(d)}log(1/ε),, which is much better for small values of ε.
As an application of this result, we show that (log s)^{O(d)}log(1/ε)--wise independence fools AC0, improving on Tal's strengthening of Braverman's theorem that (log(s/ε))^{O(d)}-wise independence fools AC0. Time permitting, we will also discuss some lower bounds on the best polynomial approximations to AC0.
[Joint work with Srikanth Srinivasan]
Speaker:Prateek Jain

Title of Talk: Near-Optimal Robust Matrix Completion via Non-convex Optimization

Astract: Several important applications require completion a low-rank matrix in presence of gross outliers. Examples include robust PCA with missing entries, robust recommendation system, foreground background separation in sublinear time etc. Existing solutions for this problem do not scale for large data and do not have optimal sample complexity/outlier complexity bounds.
In this talk, we will present a simple non-convex optimization based method that is scalable, easy to implement and needs few parameters. Moreover, despite using a non-convex optimization approach, we show that our method achieves linear rate of convergence and sloves the problem in nearly optimal time, using nearly optimal number of samples and outliers, thus significantly improving upon the existing state-of-the-art results. Moreover, our experiments show that the method is an order of magnitude faster than the existing methods and leads to a video foreground extraction technique that significantly outperforms existing standard techniques for the problem.
Speaker:Daniel Lokshtanov

Title of Talk: Lossy Kernelization

Astract: Kernelization is often presented as the first rigourous mathematical model for the study of polynomial time pre-processing of instances of NP-hard problems. An important drawback of the current definition of a kernel is that it does not capture *lossy* pre-processing where an opimal solution to the compressed instance does not necessarily translate to an optimal solution to the original instance. We propose a slightly modified definition of kernelization that also captures lossy pre-processing, and show that several problems that do not admit polynomial kernels in the traditional sense, admit lossy kernels of polynomial size, where the "loss" may be made arbitrarily small.
This is based on joint work with Fahad Panolan, M.S. Ramanujan and Saket Saurabh.
Speaker: Danupon Nanongkai

Title of Talk: A survey on dynamic graph algorithms and complexity

Astract: In this talk I will survey exciting past progresses and future opportunities in developing algorithms and complexity theory for dynamic graph problems. I will discuss barriers and intermediate steps in resolving some of the central graph problems in the area, such as connectivity, minimum spanning tree, shortest paths and maximum matching, I will also discuss how ideas and techniques from other areas -- such as spectral method, sketching, algebraic techniques, primal/dual method, and distributed/parallel algorithms -- came into play in developing dynamic graph algorithms.
Speaker: Venkatesh Raman

Title of Talk: 25 years of parameterizations

Astract: Parameterized complexity, pioneered by Downey and Fellows in the early 90s, enlarges the notion of feasible computation to allow exponential (or worse) time of some small parameter, in addition to polynomial time on the input. The area has grown in leaps and bounds, and this talk will survey the area with the theme of "parameterizations".
In the past 25 years, various parameterizations have been studied including (a) functions of the input (treewidth, distance to some special instance) and (b) functions of the output (solution size and above or below guaranteed bounds).
The talk will survey them in the context of parameterized complexity and the related notion of kernelization.
Speaker:Rahul Santhanam

Title of Talk: Only Connect - From Learning to Primes

Astract: I will discuss two superficially unrelated results from recent work. The first result states that any exponential-time algorithm for learning polynomial-size circuits can be sped up to run in subexponential time. The second states that primes can be generated pseudo-deterministically in subexponential time. I will sketch the proofs of these results, and give some intuition about the deep theory that underlies them both.
Joint work with Igor Carboni Oliveira.
Speaker:Saket Saurabh

Title of Talk: 25 Years of Kernelization, Compressed to 55 Minutes

Astract: Polynomial time preprocessing is ubiquitous through computer science; however its mathematical formulation was not possible until the advent of parameterized complexity. Polynomial time preprocessing is termed kernelization in the framework of parameterized complexity. In this time we will give historical development of kernelization within the framework of parmeterized complexity; highlighting the main developments as well as techniques and tools developed in the last 25 years.
Speaker:Srikanth Srinivasan

Title of Talk: A Recent Average Case Depth Hierarchy Theorem for Constant-Depth Circuits

Astract: A well-known result of Hastad from the 80s shows that Boolean Circuits (made up AND, OR and NOT gates) of constant depth d are exponentially weaker than those of depth d+1. More precisely, Hastad showed that for every d and n, there is a Boolean function F_d on n variables that has a poly(n)-size circuit of depth d+1 but no subexponential-size circuit C of depth at most d. This was used by Hastad to prove, for example, that there is an oracle w.r.t. which all levels of the Polynomial Hierarchy are distinct.
The circuit lower bound of Hastad was a worst case lower bound, in the sense that it only guaranteed that F_d differed from C on a small fraction of inputs. Recently, a breakthrough result of Rossman, Servedio and Tan (FOCS 2015 Best paper) showed how to strengthen this to an *average case* lower bound. Formally, there is a function G_d on n variables that has a poly(n)-size circuit of depth d+1 but no subexponential-size circuit C of depth at most d can compute G_d on more than a 0.51 fraction of inputs (since G_d is {0,1}-valued, computing it on half its inputs is trivial). This was also used by authors to get a stronger consequence for oracles: w.r.t. a random oracle, all levels of the Polynomial Hierarchy are distinct with probability 1.
I will talk about the result of Rossman, Servedio and Tan. The talk will be addressed to a general theory audience.
Speaker:Rajesh Sundaresan

Title of Talk: An overview of the cavity method and the BP algorithm

Astract: The talk will be an overview of the cavity method and the belief propagation algorithm as applied to random instances of some classical problems such as matching, its variants, edge-cover, TSP, etc. I will focus first on the general approach and will later touch upon the variations arising from problem specifics.
Speaker:Ola Svensson

Title of Talk: Lift-and-Round to Improve Scheduling on Unrelated Machines

Astract: Weighted completion time and makespan are some of the most relevant and well-studied measures of quality of service in scheduling and resource allocation problems. While these objectives have been studied since the 50's, a systematic study of their approximability was started in the 90's. Since then, impressive progress has led to a complete understanding of these objectives in simple machine models, such as identical machines. In contrast, it remains a notorious problem to understand the approximability in the more general unrelated machine setting: the classic algorithms developed in the 90's resisted any improvements while having guarantees that are far from the strongest known lower bounds. In this talk, we overview recent developments with a focus on our recent approximation algorithm that improves upon the barrier of 3/2 for the weighted completion time objective. The improvement is based on a new lift-and-project based SDP relaxation and a general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties. This is based on joint work with Nikhil Bansal and Aravind Srinivasan (http://arxiv.org/abs/1511.07826).
Speaker: Nisheeth Vishnoi

Title of Talk: Finding Sparse Vectors in an Affine Space