Regular expressions constitute a fundamental notion in formal language theory and are frequently used in computer science to define search patterns. In particular, regular expression matching  and membership testing are widely used computational primitives, employed in many programming languages and text processing utilities. A classic algorithm for these problems constructs and simulates a non-deterministic finite automaton corresponding to the expression, resulting in an O(m n) running time (where m is the length of the pattern and n is the length of the text). This running time can be improved slightly (by a polylogarithmic factor), but no significantly faster solutions are known. At the same time, much faster algorithms exist for various special cases of regular expressions, including dictionary matching, wildcard matching, subset matching, word break problem etc.

In this paper, we show that the complexity of regular expression matching can be characterized based on its depth (when interpreted as a formula). Our results hold for expressions involving concatenation, OR, Kleene star and Kleene plus. For regular expressions of depth two (involving any combination of the above operators), we show the following dichotomy: matching and membership testing can be solved in near-linear time, except for “concatenations of stars”, which  cannot be solved in sub-quadratic time unless the Strong Exponential Time Hypothesis (SETH) is false. For regular expressions of depth three the picture is more complex. Nevertheless, we show that all problems can either be solved in strongly sub-quadratic time, or cannot be solved in sub-quadratic time unless SETH fails.

An intriguing special case of membership testing involves regular expressions of the form  “a star of an OR of concatenations”, e.g., [a|ab|bc]^*. This corresponds to the so-called word break problem, for which a dynamic programming algorithm with a runtime of (roughly) O(n√m) is known. We show that the latter bound is not tight and improve the runtime to O(n m^0.44…).

Smooth (or universal) projective hash functions (SPHFs) were first introduced by Cramer and Shoup, at Eurocrypt'02, as a tool to construct efficient encryption schemes satisfying a strong security property: indistinguishability under chosen-ciphertext attacks. Since then, they have found many other applications in cryptography, including password-authenticated key exchange, oblivious transfer, and blind signatures. They also enable an informer to send a message to a secret agent, so that only a real secret agent can read the message, but the informer has no way to be sure whether he was talking to a secret agent or an impostor.

SPHFs can be seen as implicit proofs of membership for certain languages. An important question is to characterize which languages they can handle. In this talk, we make a step forward towards this goal, by introducing diverse modules. A diverse module is a representation of a language, as a submodule of a larger module, where a module is essentially a vector space over a ring. Any diverse module directly yields an SPHF for the corresponding language, and almost all the known smooth projective hash functions are constructed this way. Furthermore, diverse modules can easily be combined to provide new applications of SPHFs, such as zero-knowledge arguments.

A “distance preserver” of a graph G is a sparse subgraph whose distances agree with G for a given set of node pairs P. A famous example is BFS trees, which preserve all distances from a single source s to all other nodes V using O(n) edges. The central goal of distance preserver research is simply to determine how many edges are needed when the node pairs have some other structure besides P = {s} x V.

We will survey basic results and techniques in this area, as well as some very recent developments in the state of the art. We will also briefly discuss a successful line of research using distance preservers to understand spanners (subgraphs that approximately preserve all pairwise distances), and show how certain fundamental facts about distance preservers directly imply some surprising behaviors in the landscape of spanners.

We consider the problem of answering queries about a sensitive dataset subject to differential privacy. The queries may be chosen adversarially from a larger set of allowable queries via one of three interactive models. These models capture whether the queries are given to the mechanism all in a single batch (“offline”), whether they are chosen in advance but presented to the mechanism one at a time (“online”), or whether they may be chosen by an analyst adaptively (“adaptive”).

Many differentially private mechanisms are just as efficient in the adaptive model as they are in the offline model. Meanwhile, most lower bounds for differential privacy hold in the offline setting. This suggests that the three models might be equivalent.

We prove that these models are all, in fact, distinct. Specifically, we show that there is a family of statistical queries such that exponentially more queries from this family can be answered in the offline model than in the online model. We also exhibit a family of search queries such that many more queries from this family can be answered in the online model than in the adaptive model. We also investigate whether such separations might hold for simple queries, such as threshold queries over the real line.

Joint work with Thomas Steinke and Jonathan Ullman.

Many programmable matter systems have been proposed and realized recently, each often tailored to a specific task or physical setting. In our work on self-organizing particle systems, we abstract away from specific settings and instead describe programmable matter as a collection of simple computational elements (called particles) with limited computational power that each perform fully distributed, local, asynchronous algorithms to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, where we seek fully distributed and asynchronous algorithms that lead the system to gather together as tightly as possible, that is, to converge to a configuration with small perimeter, where we measure the perimeter of a configuration by the length of the walk along the configuration boundary. We present a Markov chain based algorithm that solves the compression problem under the geometric amoebot model, using the triangular lattice as the underlying graph, for particle systems that begin in a connected configuration with no holes. The Markov chain M takes as input a bias parameter λ, where λ > 1 corresponds to particles favoring inducing more lattice triangles within the particle system. We prove that during the execution of M, the particles stay connected and no holes form. We furthermore prove M is a reversible and ergodic Markov chain, which leads to our main result: for all λ > 2 + √2, there is a constant α > 1 such that at stationarity the particles are α-compressed, meaning the perimeter of the particle configuration is at most α times the minimum perimeter for those particles. We additionally show λ > 1 is not enough to guarantee compression: for all 0 < λ < 2.17, there is a constant β < 1 such that the perimeter is at least a β fraction of the maximum perimeter.

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.

Monotonicity testing has been a touchstone problem in property testing for more than fifteen years, with many exciting recent developments in just the past few years. When specialized to Boolean-valued functions over {0,1}ⁿ, we are interested in the number of queries required to distinguish whether an unknown function is monotone or far from every monotone function. In this talk we discuss recent results on Boolean monotonicity testing and some related problems, focusing on the lower bound side.

Based on joint works with Anindya De, Rocco Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie.

Given an explicit description of a Markov chain, we present a new algorithm to (approximately) compute its stationary distribution.  The traditional approaches to this problem involve either solving general systems of linear equations (taking n^ω time) or in some way simulating the Markov chain itself (giving a linear dependence on the mixing time of the Markov chain).  In contrast, our new approach has a subquadratic dependence on the size of the Markov chain and a polylogarithmic dependence on mixing time.  Our methods can also be used for other random walk problems, such as Personalized Page Rank and commute times.

Joint work with Jonathan Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu.

We give the first polynomial-time approximation schemes (PTASs) for the following classical problems:

1. uniform facility location in edge-weighted planar graphs;
2. k-median and k-means in edge-weighted planar graphs;
3. k-means in Euclidean space of bounded dimension.

Our first and second results extend to minor-closed families of graphs. The algorithm is local search where the local neighborhood of a solution S consists of all solutions obtained from S by removing and adding 1/ε^O(1) centers.

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-Turing reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP ≠ EXP, which is a major open problem in computational complexity.

In this talk, we provide strong evidence that current techniques cannot establish NP-hardness of MCSP, even under polynomial-time Turing reductions or randomized reductions: Specifically, we introduce the notion of oracle-independent reduction to MCSP, which captures all the currently known reductions.  We say that a reduction to MCSP is oracle-independent if the reduction can be generalized to a reduction to MCSP^A for any oracle A, where MCSP^A denotes an oracle version of MCSP.  We prove that no language outside P is reducible to MCSP via an oracle-independent polynomial-time Turing reduction.  We also show that the class of languages reducible to MCSP via an oracle-independent randomized reduction that makes at most one query is contained in AM and coAM.  Thus, NP-hardness of MCSP cannot be established via such oracle-independent reductions unless the polynomial hierarchy collapses.

We present a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner Forest Problem in doubling metrics. Before our work, a PTAS is given only for the Euclidean plane in [FOCS 2008: Borradaile, Klein and Mathieu]. Our PTAS also shares similarities with the dynamic programming for sparse instances used in [STOC 2012: Bartal, Gottlieb and Krauthgamer] and [SODA 2016: Chan and Jiang]. However, extending previous approaches requires overcoming several non-trivial hurdles.

We introduce the following novel technical ideas.

1. We prove a technical lemma showing that Steiner points have to be “near” the terminals in an optimal Steiner tree. This enables us to define an estimator to estimate the local behavior of the optimal solution, even though the Steiner points are unknown in advance. This lemma also generalizes previous results in the Euclidean plane, and may be of independent interest for related problems involving Steiner points.
2. We develop a novel algorithmic technique known as “adaptive cells” to overcome the difficulty of keeping track of multiple components in a solution. Our idea is based on but significantly different from the previously proposed “uniform cells” in the FOCS 2008 paper, whose techniques cannot be readily applied to doubling metrics.

We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an ε-fraction of the samples. Such questions have a rich history spanning statistics, machine learning and theoretical computer science. Even in the most basic settings, the only known approaches are either computationally inefficient or lose dimension-dependent factors in their error guarantees. This raises the following question: is high-dimensional agnostic distribution learning even possible, algorithmically?

In this talk, we present the first computationally efficient algorithms with dimension-independent error guarantees for agnostically learning several fundamental classes of high-dimensional distributions: (1) a single Gaussian, (2) a product distribution on the hypercube, (3) mixtures of two product distributions (under a natural balancedness condition), and (4) mixtures of spherical Gaussians. Our algorithms achieve error that is independent of the dimension, and in many cases scales nearly optimally with the fraction of adversarially corrupted samples. Moreover, we develop a general recipe for detecting and correcting corruptions in high-dimensions, that may be applicable to many other problems.

Based on joint work with Ilias Diakonikolas, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.

In this talk we give a broad introduction to Birthday Repetition, a technique introduced in [AIM '14] to prove quasi-polynomial hardness of “Free” game assuming the Exponential Time Hypothesis. The main observation of the technique is Birthday Paradox, in particular that aggregating the variables in 2CSPs to a tuple of size Õ(√n) then choosing two tuples at random will have a challenge from original 2CSP with high probability.

Using the technique, we show the following specific applications:

1. ε-approximate Nash Equilibrium with good social welfare [BKW '15, KY '16];
2. Densest-k-subgraph with perfect completeness (or additive approximation guarantees) [BKRW '15];
3. Signaling for Bayesian Games [Rub '16, KY '16];
4. Approximation guarantee for dense-CSPs [MR '16].

Suppose one wishes to accurately recover the set of eigenvalues of the covariance matrix of a distribution, given access to samples from the distribution. To what extent can this set be accurately approximated given an amount of data that is sublinear in the dimension of the space? The naive empirical estimate has poor performance when the number of samples is linear or sub-linear in the dimension of the data. In the “large sample, large dimension” setting, we proposed an efficient and information theoretically near-optimal algorithm to learn the moments of the covariance spectral distribution. Further we show that given the first k moments of a distribution, we can pin down the distribution in Earthmover distance up to an error of O(1/k). These two results combined allow us to efficiently and accurately learn the spectrum of the underlying covariance matrix, yielding a consistent spectrum estimator even with sub-linear number of samples.

I will show how to perform sparse approximate Gaussian elimination on Laplacian matrices.

I present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix with a sparse Cholesky factorization, which is essentially Gaussian elimination on symmetric matrices.

This gives the first nearly linear time solver for Laplacian systems that is based purely on random sampling, and does not use any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders.

Joint work with Sushant Sachdeva.

Motivated by an application in kidney exchange, we study the following stochastic matching problem: we are given a graph G(V,E) (not necessarily bipartite), where each edge in E is realized with some constant probability p > 0 and the goal is to find a maximum matching in the realized graph. An algorithm in this setting is allowed to make queries to edges in E in order to determine whether or not they are realized, and we aim to design algorithms that make as few queries per vertex as possible.

We design algorithms for the stochastic matching problem that achieve the same approximation factor as the previous best algorithms of Blum et al. (EC 2015) while making exponentially smaller number of queries per vertex. Moreover, the approximation guarantee of our algorithms is instance-wise as opposed to only being competitive in expectation as is the case for Blum et al. This is of particular relevance to the key application of stochastic matching in kidney exchange.

This is based on joint work with Sepehr Assadi and Sanjeev Khanna.

Leon Walras introduced an economic market model in 1874. In this model, every agent participating in the market has an initial endowment of some goods and a utility function over sets of goods. Goods are assumed to be divisible.

The market clears at a set of prices if each agent can spend its entire budget (= the total value of its goods at the set of prices) on a bundle of goods with maximum utility, and all goods are completely sold. Market clearing prices are also called equilibrium prices. In the linear version of the problem, all utility functions are linear. For the case of linear utility functions, Walras' model is also known as the linear exchange economy.

Walras argued the existence of equilibrium prices by describing an iterative improvement algorithm. However, his argument was incomplete. A convincing proof of existence was only given in the 1950 by Arrow and Debreu. The proof is non-constructive. Starting in the '70s, the quest for algorithms arose. The first algorithms were exponential. Later, polynomial time algorithms were derived based on the formulation of the problem as a convex program and the use of the Ellipsoid or the interior point method.

In the technical part of the talk, we describe a combinatorial polynomial-time algorithm for computing equilibrium prices. We formulate the problem as a network flow problem in which the prices are modeled as capacities. We show that the problem can be solved by an iterative algorithm. In each iteration, we first adjust the prices and then compute a maximum flow. The adjustment of the prices is based on a careful examination of the current maximum flow.

We also report on an implementation of the algorithm.

(joint work with Ran Duan, Jugal Garg, and Omar Darwish).

We present a candidate reduction from 3-Lin to the 2-to-2 Games problem. Though we are unable to show that the reduction is sound, we present a combinatorial hypothesis about Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in a certain non-standard sense. The optimized parameter is the number of vertices that can be assigned a small list of colors, so that for every constraint, either one of its endpoints is unassigned, or there is a consistent pair of colors in the endpoints' lists.

This sense of soundness is sufficient to obtain new hardness gaps for IS: Assuming a combinatorial hypothesis on the Grassmann Graph, it is NP-hard to distinguish whether an n-vertex graph has an independent set of size (1 - 1/√2)n - εn or whether every independent set has size εn. In particular, it is NP-hard to approximate the Vertex Cover problem to within factor √2 - ε.

The talk is based on a joint work with Subhash Khot (NYU) and Muli Safra (Tel-Aviv University).

Every undirected, unweighted graph G=(V,E) defines a “graph metric” (V,d) where d is the distance function w.r.t. G. Graph spanners, emulators, and distance oracles can all be viewed as “lossy” compression schemes that take a (dense) undirected graph G and produce a representation of some approximation (V,d') of the true metric (V,d).

What does an information-theoretically optimal compression of (V,d') look like? In particular, given a budget of n^1+ε bits for the compressed representation, how much must d' diverge from d, as a function of ε?

In this talk I will survey the history of graph compression. The talk will cover constructions of additive spanners, sublinear additive emulators, and a recent lower bound due to Abboud, Bodwin, and Pettie (2016) that mostly closes the problem.

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n*n matrix M and will receive n column-vectors of size n, denoted by v₁, …, v_n, one by one. After seeing each vector v_i, we have to output the product M*v_i before we can see the next vector. A naive algorithm can solve this problem using O(n³) time in total, and its running time can be slightly improved to O(n³/log² n) [Williams SODA'07].

We show that a conjecture that there is no truly subcubic (O(n^3-ε)) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term “combinatorial algorithms” is interpreted as “non-Strassen-like algorithms”.

The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures — such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase — thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully dynamic densest subgraph and diameter problems.

Random instances of 3SAT are known to be unsatisfiable with high probability when there at least 5N clauses. However, given a random 3SAT instance on N variables, the task of refuting the instance, or of proving that the instance has no satisfying assignments, is hypothesized to be computationally hard if there are O(N) clauses—in fact, the best known efficient algorithms for refutation require instances with at least Ω(N^3/2) clauses, a factor of N^1/2 beyond the unsatisfiability threshold at ϴ(N).

In this talk, I will describe a new spectral algorithm that refutes 3SAT instances with fewer clauses, given more time. Our algorithm extends the best polynomial time algorithms at ϴ(N^3/2) clauses, interpolating between them and the exponential brute-force search at the unsatisfiability threshold at ϴ(N) clauses.

Further, our algorithm strongly refutes the instances, certifying that no assignment satisfies more than a (7/8)-fraction of constraints.

This result also implies tight upper bounds on the value of sum-of-squares relaxations for random CSPs, as well as the value of sum-of-squares relaxations for random polynomial maximization over the unit sphere (injective tensor norm).

Based on joint work with Prasad Raghavendra and Satish Rao.

A classical question in the geometry of numbers asks how many lattice points lie in some ball around the origin. Minkowski's celebrated theorem gives us a tight lower bound for this number that depends only on the determinant of the lattice. (One can think of the determinant as the limit of the density of lattice points inside large balls. So, Minkowski's theorem gives a tight lower bound on a lattice's “local density” based on its “global density.”) We resolve a conjecture due to Dadush that gives a nearly tight converse to Minkowski's theorem—an upper bound on the number of lattice points in a ball that depends only on the determinants of sublattices. This theorem has numerous applications, from complexity theory, to the geometry of numbers, to the behavior of Brownian motion on flat tori.

Based on joint work with Oded Regev.

Reed–Muller codes encode an m-variate polynomial of degree r by evaluating it on all points in {0,1}^m. Its distance is 2^m-r and so it cannot correct more than half number of errors in the worst case. For random errors, however, one may hope for better results.

In this talk we will see an efficient algorithm for correcting random errors in Reed–Muller codes in various regimes that can handle many more errors than the minimal distance suggests, and discuss its connections with the recent progress regarding decoding erasures in Reed–Muller codes.

(Based on a joint work with Ramprasad Saptharishi and Amir Shpilka)

The ellipsoid method, as analyzed by Khachiyan in 1979, is the first polynomial time algorithm for solving linear and convex programming in the presence a separation oracle for the underlying linear constraints. The seminal paper of Grotschel, Lovasz & Schrijver laid the foundation of its wide applicability in combinatorial optimization by formulating various discrete optimization problems as linear programs.

In this talk I will demonstrate that surprisingly, very often appropriately formulating the problem as a convex program instead would yield significantly faster algorithms. Applications of this simple idea include new algorithms for matroid intersection and computing market equilibrium with the aggregate demand oracle in buyers' market.

Existing n-process randomized wait-free (and obstruction-free) consensus protocols from registers all use at least n registers. In 1992, it was proved that such protocols must use Ω(√n) registers. In 2015, this was improved to Ω(n) registers in the anonymous setting, where processes do not have identifiers. Closing the gap in the general case, however, remained an open problem. Recently, I resolved this problem by proving that every randomized wait-free (or obstruction-free) consensus protocol for n processes must use at least n-1 registers. This talk will go over the lower bound and the necessary prerequisites from distributed computing.