Rutgers/DIMACS Theory of Computing Seminar
Fall 2013

Place: CoRE 431 
Time: Wednesdays 11:00 am -- 12:00 Noon
Organizers: Swastik Kopparty and Shubhangi Saraf


For those arriving by train to New Brunswick station, the best way to get to the seminar room is by Rutgers bus. The directions are available by clicking here.
For those driving in, the best strategy is to pre-arrange to pick up a parking tag from one of the organizers upon arrival, and park in lot 64. For directions to Lot 64, click on this 


      The Rutgers discrete math seminar.

      Other Math and CS seminars at Rutgers.

      Theory of Computing seminars from previous semesters.



September 11


Aravindan Vijayaraghavan


Uniqueness of Tensor Decompositions with Applications to

Learning Latent Variable Models


We give a robust version of the celebrated result of Kruskal on the uniqueness of tensor decompositions: we prove that given a tensor whose decomposition satisfies a robust form of fairly general condition called the Kruskal's rank condition, it is possible to recover the terms of the decomposition if the tensor is known up to a sufficiently small (inverse polynomial) error.


Kruskal's theorem has found many applications in statistics, signal processing, data mining -- in machine learning, it is used in proving the identifiability of parameters for various latent variable models and mixture models such as Hidden Markov models, mixtures of Gaussians etc. Our robust version immediately implies identifiability using only polynomially many samples in many of these settings. Given the importance of Kruskal's theorem in the tensor literature, we expect that this robust version will have several applications beyond the settings we explore in this work.


Based on joint work with Aditya Bhaskara and Moses Charikar

September 18

Rotem Oshman

Princeton University

Tel Aviv University

Tight Bounds for Set Disjointness in the Message-Passing Model


In many distributed systems, the cost of computation is dominated by the cost of communication between the machines participating in the computation. Communication complexity is therefore a very useful tool in understanding distributed computation, and communication complexity lower bounds have been used extensively to obtain lower bounds on various distributed problems. However, almost all applications of communication complexity lower bounds in distributed computing use two-party lower bounds, despite the fact that distributed computation usually involves many players. Unfortunately, there are interesting distributed problems that it appears cannot be addressed using two-player lower bounds, because reductions from two-player problems seem to lose the "hardness" of the problem.


With this motivation in mind, in this work we study communication complexity in the multi-party message-passing model, which has been extensively used in distributed computing and in secure multi-party computation. In the message-passing model there are k players, each with a private n-bit input, and the players communicate with each other over private channels. We show a lower bound of Omega(n*k) on the communication complexity of set disjointness in the message-passing model. To obtain this bound we develop information complexity tools for the model, prove a direct-sum theorem, and show that the information complexity of computing a 1-bit AND with k players is Omega(k).


This is joint work with Mark Braverman, Faith Ellen, Toniann Pitassi and Vinod Vaikuntanathan.

September 25


Yevgeniy Dodis


Key Derivation Without Entropy Waste


We revisit the classical question of converting an imperfect source X of min-entropy k into a usable m-bit cryptographic key for some underlying application P. If P has security delta (against some class of attackers) with a uniformly random m-bit key, we seek to design a key derivation function (KDF) h that allows us to use R=h(X) as the key for P and results in comparable security delta' close to delta. Seeded randomness extractors provide a generic way to solve this problem provided that k > m + 2*log(1/delta), and this lower bound on k (called "RT-bound") is known to be tight in general. Unfortunately, in many situation the "waste" of 2*log(1/delta) bits of entropy is significant, motivating the question of designing KDFs with less waste for important special classes of sources X or applications P.I will discuss several positive and negative results in this regard.


The most surprising of them will be a positive result for all unpredictability applications P, yielding a provably secure KDF with entropy "waste" only loglog(1/delta) - an expenential improvement over the RT-bound.

October 2

Xi Chen

Columbia University

Multi-Stage Design for Quasipolynomial-Time Isomorphism Testing of Steiner 2-Systems


We analyze the 2-dimensional Weisfeiler-Leman (2-dim WL) refinement, an extension of the naive refinement heuristic for isomorphism testing, over Steiner 2-systems. A Steiner 2 -system consists of points and lines, where each line passes the same number of points and each pair of points uniquely determines a line. Each Steiner 2-system induces a Steiner graph, in which vertices represent lines and edges represent intersections of lines. Steiner graphs are an important subfamily of strongly regular graphs whose isomorphism testing has challenged researchers for years. Inspired by the previous analyses of the individualization and refinement method by Babai and by Spielman, we show that the individualization of O(log n) points and lines suffices for the 2-dim WL refinement to distinguish all pairs of points of a Steiner 2-system. As a result, the isomorphism of Steiner 2-systems with n lines can be tested in time n^{O(log n)}, improving the previous best upper bound of exp(\tilde{O}(n^{1/4})) by Spielman. Before our result, quasipolynomial-time isomorphism testing was only known for the case when the line size is polylogarithmic, as shown by Babai and Luks.


A result essentially identical to ours was obtained simultaneously by Babai and Wilmes. They performed a direct analysis of the individualization and refinement method based on the naive refinement, building on a different philosophy and combinatorial structure theory.


Joint work with Xiaorui Sun and Shang-Hua Teng.

October 9

Noga Alon

Tel Aviv University


Approximation algorithms via matrix covers


I will describe a general technique for obtaining approximate solutions of hard quadratic optimization problems using economical covers of high dimensional sets by small cubes. The analysis of the method leads to intriguing algorithmic, combinatorial, extremal, geometric and probabilistic questions.


Based on joint work with Lee, Shraibman and Vempala.

October 16

Brendan Juba

Harvard University

Efficient reasoning in PAC Semantics


Machine learning is often employed as one step in a larger application, serving to perform information extraction or data mining for example. The rules obtained by such learning are then used as inputs to a further analysis. As a consequence of the inputs to this analysis having been learned, however, its conclusions can only be theoretically guaranteed to satisfy the same standard as the inputs---that of "PAC Semantics" (Valiant, 2000). In this talk, we explore the benefits of taking the problems of learning and logical reasoning together, capturing a relatively general family of such applications. Briefly, the benefit is that we can simultaneously (1) handle incomplete information, (2) utilize rules that are a reasonable but imperfect fit for the data, and (3) reach conclusions more efficiently than is achieved by known algorithms for reasoning from rules alone. Precisely, we consider a problem of testing the validity of a "query" formula (hypothesis) against incomplete data. We present algorithms for soundly verifying such queries that succeed whenever there exist learnable rules that suffice to complete a simple proof of the query, matching what can be achieved by such a two-stage learning and reasoning process.

October 23

Sergey Yekhanin

Microsoft Research Silicon Valley

Local erasure coding for data storage.

Historically, most large distributed storage systems (e.g., Hotmail) have been using replication to provide reliability against machine failures. Today however as the amount of stored data reaches multiple Exabytes keeping few copies of data around is becoming prohibitively expensive. Therefore more and more systems are adopting erasure coding in place of replication.

Local Reconstruction Codes (LRCs) are a new class of erasure correcting codes designed specifically for applications in data storage. Built upon the rich mathematical theory of locally decodable codes developed in the theory community, LRCs provide high level of reliability and allow data fragments to be reconstructed quickly in typical failure scenarios. LRCs have been recently deployed by Windows Azure Storage and are going to ship in Windows 8.1 and Windows Server 2012.

In this talk we will discuss motivation behind local reconstruction codes and cover the main technical challenges and tradeoffs in the design of these codes.

(Based on joint papers with Brad Calder, Michael Forbes, Parikshit Gopalan, Cheng Huang, Bob Jenkins, Jin Li, Aaron Ogus, Huseyin Simitci, and Yikang Xu.)

October 30


(the day after FOCS)

November 6

Mark Lewko


Sets of large doubling


I will discuss the structure of
a finite set A of integers such that A+A is large. I will give a counterexample to an "anti-Freiman" conjecture in additive combinatorics. Connections with harmonic analysis and error correcting codes will also be discussed. No background will be assumed. This is joint work with Allison Lewko.

November 13

Rocco Servedio

Columbia University

Learning from satisfying assignments


We introduce and study a new type of learning problem for probability distributions over the Boolean hypercube. As in the standard PAC learning model, a learning problem in our framework is defined by a class C of Boolean functions over the hypercube, but unlike the standard PAC model, in our model the learning algorithm is given uniform random satisfying assignments of an unknown function in C and its goal is to output a high-accuracy approximation of the uniform distribution over the space of satisfying assignments for f. This distribution learning problem may be viewed as a demanding variant of standard Boolean function learning, where the learning algorithm only receives positive examples and --- more importantly --- must output a hypothesis function which has small *multiplicative* error (i.e. small error relative to the size of f^{-1}(1).


As our main results, we show that the two most widely studied classes of Boolean functions in computational learning theory --- linear threshold functions and DNF formulas --- have efficient distribution learning algorithms in our model. Our algorithm for linear threshold functions runs in time poly(n,1/epsilon) and our algorithm for polynomial-size DNF runs in quasipolynomial time. On the other hand, we also prove complementary hardness results which show that under cryptographic assumptions, learning monotone 2-CNFs, intersections of 2 halfspaces, and degree-2 PTFs are all hard. This shows that our algorithms are close to the limits of what is efficiently learnable in this model.


Joint work with Anindya De and Ilias Diakonikolas.

November 20

Gillat Kol


Interactive Channel Capacity


In a profoundly influential 1948 paper, Claude Shannon defined the entropy function H, and showed that the capacity of a symmetric binary channel with noise rate (bit flip rate) eps is 1-H(eps). This means that one can reliably communicate n bits by sending roughly n / (1-H(eps)) bits over this channel.


The extensive study of interactive communication protocols in the last decades gives rise to the related question of finding the capacity of a noisy channel when it is used interactively. We define interactive channel capacity as the minimal ratio between the communication required to compute a function (over a non-noisy channel), and the communication required to compute the same function over the eps-noisy channel. We show that the interactive channel capacity is roughly 1-Theta(sqrt(H(eps)) ). Our result gives the first separation between interactive and non-interactive channel capacity.


Joint work with Ran Raz.

November 27


(the day before Thanksgiving)

December 4

Kostas Bekris

Rutgers University

Algorithmic Challenges in Robot Motion Planning


Motion planning is a prototypical computationally hard problem, which requires the computation of collision-free, feasible paths for moving bodies in continuous spaces. Due to its importance in many applications, such as robotics and computer simulations, a variety of practical approaches have been developed for solving effectively many planning instances. A popular methodology samples valid configurations of a moving body to incrementally construct and connect the nodes of a graph on which path planning problems are then solved. These methods provide probabilistic instead of deterministic completeness. A recent development has been the identification of the conditions under which these methods also converge asymptotically to optimal paths in continuous configuration spaces.


This talk will review the state-of-the-art in algorithmic motion planning and recent contributions of our research group in balancing performance guarantees, such as completeness and path quality, and computational requirements, such as time and memory requirements. Furthermore, open problems will be identified that motivate further research in this area.