rnRutgers/DIMACS Theory of Computing Seminar
Spring 2015


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 link


·      The Rutgers discrete math seminar.

·      Other Math and CS seminars at Rutgers.

·      Theory of Computing seminars from previous semesters.



January 21

Igor Shinkar


Zero-Fixing Extractors for Sub-Logarithmic Entropy


An (n,k)-bit-fixing source is a distribution on n bit strings, that is fixed on n-k of the coordinates, and uniform on the remaining k bits. Explicit constructions of extractors for bit-fixing sources by Gabizon, Raz and Shaltiel (SICOMP 2006) and Rao (CCC 2009) extract (1-o(1))k bits for k = polylog(n), almost matching the probabilistic argument. Intriguingly, unlike other well-studied sources of randomness, a result of Kamp and Zuckerman (SICOMP 2006) shows that, for any k some small portion of the entropy in an (n,k)-bit-fixing source can be extracted. Although the extractor does not extract all the entropy, it does extract log(k)/2 bits.


In this work we prove that when the entropy k is small enough compared to n, this exponential entropy-loss is unavoidable, and it is impossible to extract more than log(k)/2 bits from (n,k)-bit-fixing sources. In some sense the remaining entropy is inaccessible, information theoretically.


In fact, our impossibility result holds for what we call zero-fixing sources. These are bit-fixing sources where the fixed bits are set to 0. We complement our negative result, by giving an explicit construction of an (n,k)-zero-fixing extractor, that outputs Omega(k) bits, even for k = polyloglog(n).


Furthermore, we give a construction of an (n,k)-bit-fixing extractor, for entropy k = (1+o(1))loglog(n), with running time n^polyloglog(n). We also give a new construction of an (n,k)-bit-fixing extractor, for entropy k = polylog(n) based on multi-source extractors.


Joint work with Gil Cohen

January 28

Grigory Yaroslavtsev

U Penn

Near Optimal LP Rounding for Correlation Clustering on Complete Graphs


Introduced about 10 years ago by Bansal, Blum and Chawla, correlation clustering has become one of the standard techniques in machine learning and data mining. This due to several advantages of correlation clustering as compared to other standard clustering methods (e.g. k-means):

-- Correlation clustering only requires qualitative information about similarities between objects. This makes it applicable in scenarios such as crowdsourced duplicate finding when information about similarities between objects is generated by humans.

-- Correlation clustering doesn’t require the number of clusters to be specified in advance, producing the number of clusters that best fits the data.


We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality gaps:

- For complete graphs our appoximation is 2.06−ε for a fixed constant ε, which almost matches the previously known integrality gap of 2.

- For complete k-partite graphs our approximation is 3. We also show a matching integrality gap.

- For complete graphs with edge weights satisfying triangle inequalities and probability constraints, our approximation is 1.5, and we show an integrality gap of 1.2.


Our results improve a long line of work on approximation algorithms for correlation clustering in complete graphs, previously culminating in a ratio of 2.5 for the complete case by Ailon, Charikar and Newman (JACM'08). In the weighted complete case satisfying triangle inequalities and probability constraints, the same authors give a 2-approximation; for the bipartite case, Ailon, Avigdor-Elgrabli, Liberty and van Zuylen give a 4-approximation (SICOMP'12).

February 4

Rafael Oliveira


Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas


Derandomization of the Polynomial Identity Testing problem is one of the most basic and challenging problems in Algebraic Complexity. Despite much effort, derandomizing PIT seems to be a hard task even for restricted models of computation, including small depth circuits computing multilinear polynomials. In this talk, we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we also obtain lower bounds for these models.


We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known.


Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas we go straight to read-once algebraic branching programs).


Joint work with Amir Shpilka and Ben Lee Volk, from Tel Aviv University.

February 11

Alex Nikolov

MSR/U Toronto

Randomized Rounding for the Largest j-Simplex Problem


The maximum volume j-simplex problem asks to compute the j-dimensional simplex of maximum volume inside the convex hull of a given set of n points in d-dimensional space. This is a natural problem with long history in computational geometry, and falls in the class of problems of approximating an arbitrary body with a simpler one. We give a deterministic approximation algorithm which achieves an approximation ratio of e^{j/2 + o(j)} and runs in time polynomial in d and n. The problem is known to be NP-hard to approximate within a factor of c^j for some constant c. Our algorithm also approximates the problem of finding the largest determinant principal j-by-j submatrix of a positive semidefinite matrix, with approximation ratio e^{j +   o(j)}. This latter problem has connections with discrepancy theory and low-rank matrix approximation. We achieve our approximation by rounding solutions to a generalization of the D-optimal design problem, or, equivalently, the dual of an appropriate smallest enclosing ellipsoid problem.

February 18

Sivakanth Gopi


2-Server PIR with sub-polynomial communication

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the $i$'th bit of an $n$-bit database replicated among two servers (which do not communicate) while not revealing any information about $i$ to either server. The privacy of the user is information theoretic and does not rely on any cryptographic assumptions. In this work we construct a new 2-server PIR scheme with total communication cost sub polynomial in $n$. This improves over the currently known 2-server protocols which require $n^{1/3}$ communication and matches the communication cost of known 3-server PIR schemes. Our improvement comes from reducing the number of servers in existing protocols, based on Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing these protocols in an algebraic way (using polynomial interpolation) and extending them using partial derivatives.

February 25


mass absences

March 4

Stefan Langerman

Free University of Brussels

The Power of Preprocessing: Detecting and constructing

intersections between geometric objects



When solving a computational problem (e.g., finding an element in a set), it is often the case that the bulk of the data used for input for the problem (e.g., the set) is known well in advance.  By preprocessing the data (e.g., sorting the set), it is often possible to significantly reduce the time needed to solve the problem once the specific query is provided.


In this lecture, I will focus on some of the most fundamental problems in Computational Geometry -- determining if geometric objects intersect, and if they do what is, or how large is, their intersection. These problems are fairly well understood in the traditional setting where two objects are provided and the intersection must be returned as output. However it may be the case that each object is known long in advance, and is translated and rotated just prior to the intersection query. For that setting, I will review some known and new results in an attempt to determine when preprocessing helps, and when it cannot.

March 11

Michael Forbes


Polynomial Identity Testing via Shifted Partial Derivatives


In this talk we consider the polynomial identity testing (PIT) problem: given an algebraic computation which computes a low-degree multivariate polynomial f, is f identically zero as a polynomial?  This problem is of fundamental importance in computer algebra and also captures problems such as computing matchings in graphs. While this problem has a simple randomized algorithm (test whether f is zero at a random evaluation point), it is an active line of pseudorandomness research to develop efficient deterministic PIT algorithms for interesting models of algebraic computation.


A related problem is to develop lower bounds: given a model of algebraic computation, find an explicit polynomial f which is expensive to compute in this model. As efficient deterministic PIT algorithms for a model of algebraic computation can be shown to imply lower bounds for that model, developing lower bounds is often a precursor to developing such PIT algorithms. Recently, a new lower bounds technique called "the method of shifted partial derivatives" has been introduced and has been used to obtain a number of new lower bounds for various models, however its potential for yielding PIT algorithms is largely unexplored.


In this work, we use give the first usage of the method of shifted partial derivatives to develop PIT algorithms.  In particular, we will highlight the relation to divisibility testing questions, that is, testing whether a given multivariate polynomial f divides another given multivariate polynomial g.

March 18


Spring Break

March 25

Tsvi Kopelowitz

University of Michigan

Higher lower bounds from the 3SUM conjecture



The 3SUM hardness conjecture has proven to be a valuable and popular tool for proving conditional lower bounds on the complexities of dynamic data structures and graph problems. This line of work was initiated by Patrascu [STOC 2010] and has received a lot of recent attention. Most of these lower bounds are based on reductions from 3SUM to a special set intersection problem introduced by Patrascu, which we call Patrascu's Problem. However, the framework introduced by Patrascu that reduces 3SUM to Patrascu's Problem suffers from some limitations, which in turn produce polynomial gaps between the achievable lower bounds via this framework and the known upper bounds.


We address these issues by providing a tighter and more versatile framework for proving 3SUM lower bounds via a new reduction to Patrascu's Problem. Furthermore, our framework does not become weaker if 3SUM can be solved in truly subquadratic time, and provides some immediate higher conditional lower bounds for several problems, including for set intersection data-structures. For some problems, the new higher lower bounds meet known upper bounds, giving evidence to the optimality of such algorithms.


During the talk, we will discuss this new framework, and show some new (optimal) lower bounds conditioned on the 3SUM hardness conjecture. In particular, we will demonstrate how some old and new triangle listing algorithms are optimal for any graph density, and prove a conditional lower bound for incremental Maximum Cardinality Matching which introduces new techniques for obtaining amortized lower bounds.

April 1


Sergey Yekhanin


Kolmogorov width of discrete linear spaces: an approach to matrix rigidity


A square matrix V is called rigid if every matrix obtained by altering a small number of entries of V has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major implications in computational complexity theory. One approach to establishing rigidity of a matrix V is to come up with a property that is satisfied by any collection of vectors arising from a low-dimensional space, but is not satisfied by the rows of V even after alterations. In this work we propose such a candidate property that has the potential of establishing rigidity of combinatorial design matrices over the binary field. Stated informally, we conjecture that under a suitable embedding of the Boolean cube into the Euclidian space, vectors arising from a low dimensional linear space modulo two always have somewhat small Kolmogorov width, i.e., admit a non-trivial simultaneous approximation by a low dimensional Euclidean space. This implies rigidity of combinatorial designs, as their rows do not admit such an approximation even after alterations. Our main technical contribution is a collection of results establishing weaker forms and special cases of the conjecture above.

(Joint work with Alex Samorodnitsky and Ilya Shkredov).

April 8

Roy Schwartz


Simplex Partitioning via Exponential Clocks and the Multiway Cut Problem


Multiway Cut is a graph partitioning problem in which the objective is to find a minimum weight set of edges disconnecting a special set of vertices called terminals. This problem is NP-hard and there is a well known geometric relaxation in which the graph is embedded into a high dimensional simplex. Rounding the geometric relaxation is equivalent to partitioning the simplex. I will present a simplex partitioning method that is based on competing exponential clocks and distortion. Applying this method to Multiway Cut yields an extremely simple (4/3)-approximation, thus improving the previous best known algorithm of Karger et al. Further improvements by a follow-up work will also be discussed along with related open questions.


Joint work with Niv Buchbinder and Joseph (Seffi) Naor.

April 15

Gillat Kol


Exponential Separation of Information and Communication


In profoundly influential works, Shannon and Huffman show that if Alice wants to send a message X to Bob, it's sufficient for her to send roughly H(X) bits (in expectation), where H denotes Shannon's entropy function. In other words, the message X can be compressed to roughly H(X) bits, the information content of the message. Can one prove similar results in the interactive setting, where Alice and Bob engage in an interactive communication protocol?


We show the first gap between communication complexity and information complexity, by giving an explicit example of a boolean function with information complexity O(k), and distributional communication complexity > 2^k. This shows that a communication protocol cannot always be compressed to its internal information, answering (the standard formulation of) the above question in the negative. By a result of Braverman, our example gives the largest possible gap.


By a result of Braverman and Rao, our example gives the first gap between communication complexity and amortized communication complexity, implying that strong direct sum does not hold for distributional communication complexity, answering a long standing open problem.


Joint work with Anat Ganor and Ran Raz.

April 22

Noam Solomon

Tel Aviv University

Incidences between points and lines and extremal configuration of lines in Euclidean spaces.


In 1983, Szemeredi and Trotter proved a tight bound for the number of incidences between points and lines in the plane. Ever since then, incidence geometry has been a very active research area, bridging between computer science and mathematics, with many connections to diverse topics, from range searching algorithms to the Kakeya problem.


Over 25 years later, Guth and Katz proved a tight incidence bound for points and lines in three dimensions. Their proof introduced methods from advanced algebra and especially from algebraic geometry which were not used in combinatorics before. This enabled Guth and Katz to (almost) settle the Erdos distinct distances problem - a problem which stubbornly stood open for over 60 years, despite very brave attempts to solve it. The work of Guth and Katz has given significant added momentum to incidence geometry, making many problems, deemed hopeless before the breakthrough, amenable to the new techniques.


In this talk I will present the area of incidence geometry, before and after, highlighting the basics of the new ``algebraic'' approach, and will also present very recent results, joint with Micha Sharir, among which we studied incidences between points and lines in four dimensions, incidences between points and lines that lie on special surfaces and other related questions. We will also give a variety of interesting open related questions.

April 29

Sanjeev Arora


Random Walks on Context Spaces: Towards an explanation of the mysteries of semantic word embeddings


Semantic word embeddings represent words as vectors in R^d for say d=300. They are useful  for many NLP tasks and often constructed using nonlinear/nonconvex techniques such as deep nets and energy-based models. Recently Mikolov et al (2013) showed that such embeddings exhibit linear structure that can be used to solve "word analogy tasks" such as man: woman :: king: ??.  Subsequently, Levy and Goldberg (2014) and Pennington et al (2014) tried to explain why such linear  structure should arise in embeddings derived from nonlinear methods.  We point out gaps in these explanations and provide a more complete explanation in the form of a loglinear generative model for text corpora that directly models latent semantic structure in words and involves random walk in the context space.  A rigorous mathematical analysis is performed to obtain explicit expressions for word co-occurrance probabilities, which leads to a surprising explanation for why word embeddings exist and why they exhibit linear structure that allows solving analogies.  Our model and its analysis lead to several counterintuitive predictions, which are also empirically verified.


We think our methodology may be useful in other settings.


Joint work with Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski (listed in alphabetical order).


manuscript at http://arxiv.org/abs/1502.03520