Random cluster dynamics at q = 2 is rapidly mixing
Heng Guo, Queen Mary, University of London
Monday, May 9, 2016 - 1:00pm to 2:30pm
Pierce 213
We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 is bounded by a polynomial in the size of the underlying graph. As a consequence the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound.
Joint work with Mark Jerrum.
An average-case depth hierarchy theorem for Boolean circuits
Li-Yang Tan, Toyota Technological Institute at Chicago (TTIC)
Monday, April 25, 2016 - 1:00pm to 2:30pm
Pierce 213
We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every $d \geq 2$, there is an explicit $n$-variable Boolean function $f$, computed by a linear-size depth-$d$ formula, which is such that any depth-$(d-1)$ circuit that agrees with $f$ on $(1/2 + o_n(1))$ fraction of all inputs must have size $\exp(n^{\Omega(1/d)}).$ This answers an open question posed by Håstad in his Ph.D. thesis.
Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of Håstad, Cai, and Babai. We also use our result to show that there is no "approximate converse" to the results of Linial, Mansour, Nisan and Boppana on the total influence of constant-depth circuits, thus answering a question posed by O'Donnell, Kalai, and Hatami.
A key ingredient in our proof is a notion of random projections which generalize random restrictions.
Joint work with Ben Rossman and Rocco Servedio. Paper available at http://arxiv.org/abs/1504.03398
Explicit Two-Source Extractors and Resilient Functions
David Zuckerman, University of Texas at Austin
Monday, April 11, 2016 - 1:00pm to 2:30pm
Pierce 213
We explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\Omega(1)}. The best previous extractor, by Bourgain, required each source to have min-entropy .499n.
A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta>0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylog(n)-wise independently, and the remaining q=n^{1-\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q=n^{1/2 - \delta}.
Our explicit two-source extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.
Joint work with Eshan Chattopadhyay.
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
Ryan Williams, Stanford University
Monday, March 28, 2016 - 1:00pm to 2:30pm
Pierce 213
Low-depth threshold circuits provide a clean way to model low-depth neural networks. For an explicit function in P, we prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, as well as depth-three threshold circuits with small weights. The key is a new random restriction lemma for linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.
Joint work with Daniel Kane (UCSD). Paper available at http://arxiv.org/abs/1511.07860
The Power of Tabulation Hashing
Mikkel Thorup, University of Copenhagen
Monday, March 21, 2016 - 1:00pm to 2:30pm
Pierce 213
Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical.
Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees. The scheme itself dates back to game playing programs of Zobrist from 1970. Keys are viewed as consisting of c characters. We initialize c tables T1,…,Tc mapping characters to random hash codes. A key x=(x1,…,xc) is hashed to T1[x1] xor … xor Tc[xc]. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, e.g., we get reliable performance in hash tables based on linear probing and cuckoo hashing, and in min-wise hashing for estimating set intersection.
Next we consider "twisted tabulation" where one character is "twisted" with some simple operations. The resulting hash function has powerful distributional properties, e.g., Chernoff type tail bounds and a very small bias for min-wise hashing.
Finally, we consider "double tabulation" where we compose two simple tabulation functions, applying one to the output of the other, and show that this yields very high independence in the classic framework of Carter and Wegman [1977]. In fact, w.h.p., for a given set of size proportional to that of the space consumed, double tabulation gives fully-random hashing.
Amplification and Derandomization Without Slowdown
Dana Moshkovitz, MIT
Monday, March 7, 2016 - 1:00pm to 2:30pm
Pierce 213
We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms.
Unlike most existing techniques that involve repetition of the randomized algorithm and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms. The amplification technique is related to a certain stochastic multi-armed bandit problem. The derandomization technique - which is the main contribution of this work - points to an intriguing connection between derandomization and sketching/sparsification.
We demonstrate the techniques by showing applications to Max-Cut on dense graphs, approximate clique on graphs that contain a large clique, constraint satisfaction problems on dense bipartite graphs and the list decoding to unique decoding problem for the Reed-Muller code.
This is joint work with Ofer Grossman (MIT).
Basis Collapse in Holographic Algorithms Over All Domain Sizes
Sitan Chen, Harvard
Monday, February 22, 2016 - 1:00pm to 2:30pm
Pierce 213
The theory of holographic algorithms introduced by Valiant represents a novel approach to achieving polynomial-time algorithms for seemingly intractable counting problems via a reduction to counting planar perfect matchings and a linear change of basis. Two fundamental parameters in holographic algorithms are the \emph{domain size} and the \emph{basis size}. Roughly, the domain size is the range of colors involved in the counting problem at hand (e.g. counting graph $k$-colorings is a problem over domain size $k$), while the basis size $\ell$ captures the dimensionality of the representation of those colors. A major open problem has been: for a given $k$, what is the smallest $\ell$ for which any holographic algorithm for a problem over domain size $k$ ``collapses to'' (can be simulated by) a holographic algorithm with basis size $\ell$? Cai and Lu showed in 2008 that over domain size 2, basis size 1 suffices, opening the door to an extensive line of work on the structural theory of holographic algorithms over the Boolean domain. Cai and Fu later showed for signatures of full rank that over domain sizes 3 and 4, basis sizes 1 and 2, respectively, suffice, and they conjectured that over domain size $k$ there is a collapse to basis size $\lfloor\log_2 k\rfloor$. In this work, we resolve this conjecture in the affirmative for signatures of full rank for all $k$.
k-Median Clustering on Data Streams
Harry Lang, Johns Hopkins University
Monday, February 8, 2016 - 1:00pm to 2:30pm
Pierce 213
We explore clustering problems in the streaming sliding window model in both general metric spaces and Euclidean space. We present the first polylogarithmic space O(1)-approximation to the metric k-median and metric k-means problems in the sliding window model, answering the main open problem posed by Babcock, Datar, Motwani and O'Callaghan (PODS 2003), which has remained unanswered for over a decade. Our algorithm uses $O(k^3 \log^6 n)$-space and $poly(k, \log n)$ update time. This is an exponential improvement on the space required by the technique due to Babcock et al. We introduce a data structure that extends smooth histograms as introduced by Braverman and Ostrovsky to operate on a broader class of functions. In particular, we show that using only polylogarithmic space we can maintain a summary of the current window from which we can construct an O(1)-approximate clustering solution. In Euclidean space, we give the first algorithm that, given an insertion-only streaming $\epsilon$-coreset construction of space s, maintains a $\epsilon$-coreset in the sliding windows model using $O(s^2 \epsilon^{-2} \log n)$ space.
For insertion-only streams, we provide an overview of our recent polynomial-time $O(k \log n)$-space 24-approximation. Prior algorithms achieving the same space bound had approximation factors of over 5500. We also present some of our current work that further improves this result.
Cutting Plane Method: A faster algorithm for many (combinatorial) optimization problems
Yin-Tat Lee, MIT
Monday, December 7, 2015 - 1:00pm to 2:30pm
Pierce 213
Many polynomial-time solvable (combinatorial) optimization problems can be reduced to the feasibility problem and the intersection problem. In this talk, I will present the first nearly cubic time algorithm for both problems using a new cutting plane method. This is the first improvement over the long-standing O(n^3.38) running time bound due to Vaidya in 1989.
As a consequence, our algorithm yields improved runtimes for solving classic problems in continuous and combinatorial optimization such as
- submodular minimization
- matroid intersection
- submodular flow and
- semidefinite programming.
The talk will assume no exposure to cutting plane methods. It will be based on a joint work with Aaron Sidford and Sam Wong (FOCS’15).
See http://arxiv.org/abs/1508.04874.
Smarter tools for (Citi)bike-sharing
David Shmoys, Cornell
Monday, November 30, 2015 - 1:00pm to 2:30pm
Pierce 213
New York launched the largest bike-sharing system in North America in May 2013. We have worked with Citibike, using analytics and optimization to change how they manage the system. Huge rush-hour usage imbalances the system; we answer both of the questions: where should bikes be at the start of a rush hour and how can we mitigate the imbalances that develop? Although we focus in this talk on the latter question, we will briefly touch on the analytics we have employed for the former as well, where we developed an approach based continuous-time Markov chains combined with integer programming models to compute daily stocking levels for the bikes, as well as methods employed for optimizing the capacity of the stations. For the latter problem, we present a 3-approximation algorithm used to target limited available rebalancing resources during rush-hour periods. The goal is to ensure that users are never too far from a station that will be rebalanced when looking for a bike or a spot to return one. We formulate this as a variant of the k-center problem and provide a linear programming-based algorithm with a performance guarantee of 3.
This is joint work with Shane Henderson, Eoin O'Mahoney, and Ola Svensson.
Sum of Squares lower bounds for planted clique
Boaz Barak, Harvard and Microsoft of New England
Monday, November 23, 2015 - 1:00pm to 2:30pm
Pierce 213
The planted clique problem is a central problem in average case complexity that has attracted considerable attention and was shown to be related to questions in machine learning, sparse recovery, computing equilibrium, and more.
The sum of squares algorithm is a convex program that encapsulates many of the approaches attempted for this problem.
In this talk I will discuss some recent results by Hopkins, Kothari, Potechin, Raghavendra and Schramm (SODA 2016) showing limitations of the sum of squares algorithm for this problem, as well as talk about some follow-up works that I have been involved in, together with Hopkins, Kelner, Kothari, Moitra, and Potechin.
On the $AC^0$ Complexity of Subgraph Isomorphism
Alexander (Sasha) Razborov, University of Chicago
Monday, November 9, 2015 - 1:00pm to 2:30pm
Pierce 213
For a given fixed pattern graph P, the subgraph isomorphism problem is to decide whether a large graph G contains a subgraph isomorphic to P. We are interested in its $AC^0$-complexity; more precisely, in determining (in purely combinatorial terms) the smallest possible exponent C(P) for which this problem can be decided by bounded-depth circuits of size $n^{C(P)+o(1)}$. We completely answer this question for two natural modifications suggested by the previous research in this area: a "colorful" version in which every vertex of P must end up in a part of its own, and the average-case version. For the general case we provide some partial results, some of them strongly indicating that perhaps the colorful version of the subgraph isomorphism problem is the "right" one.
Is optimization computationally equivalent to online learning?
Elad Hazan, Princeton
Monday, October 26, 2015 - 1:00pm to 2:30pm
Maxwell Dworkin 221
The fundamental theorem of statistical learning establishes a computational equivalence between optimization (empirical risk minimization) and learning in the statistical setting. Is the same true for learning in games? We give a precise answer to this question.
Joint work with Tomer Koren.
Approximation Schemes for Planar Graphs: A How-To Guide
Philip Klein, Brown University
Monday, October 5, 2015 - 1:00pm to 2:30pm
Pierce 213
In addressing an NP-hard problem in combinatorial optimization, one way to cope is to use an {\em approximation scheme}, an algorithm that, for any given $\epsilon>0$, produces a solution whose value is within a $1+\epsilon$ factor of optimal. For many problems on graphs, obtaining such accurate approximations is NP-hard if the input is allowed to be any graph but is tractable if the input graph is required to be planar.
Research on polynomial-time approximation schemes for optimization problems in planar graphs goes back to the pioneering work of Lipton and Tarjan (1977) and Baker (1983). Beginning in 2005, however, a flurry of results were obtained, greatly broadening the range of problems for which fast approximation schemes for planar graphs are known. The approach continues to yield new results. In this talk, we outline the approach and illustrate its use.
How to refute a random CSP
Ryan O'Donnell, CMU
Monday, September 21, 2015 - 1:00pm to 2:30pm
Pierce 213
Let P be a k-ary predicate and let H be a uniformly random constraint satisfaction problem with n variables and m = m(n) constraints, each of type P applied to k literals. (For example, if P is the 3-ary OR predicate, then H is a classic random instance of 3SAT.) For each P there is a critical constant alpha such that H will be satisfiable (with high probability) if m < alpha n and will be unsatisfiable (whp) if m > alpha n. In the former case, the natural algorithmic task is to find a satisfying assignment to the variables. In the latter case, the natural algorithmic task is to find a *refutation*; i.e., a proof of unsatisfiability. This task becomes algorithmically easier the larger m is. As an example, in the case of 3SAT, it is known that efficient refutation algorithms exist provided m >> n^{3/2}.
In this work, we investigate the refutation problem for a general predicate P. Our main theorem is that if P fails to support a t-wise uniform probability distribution then there is an efficient algorithm for refuting random H provided m >> n^{t/2}. Our work generalizes, and in many cases improves, all previously known refutation algorithms (except for logarithmic factors on m). We also provide some limited evidence that the m-dependence may be optimal. Finally, as an application, we show that the "SRCSP assumptions" used in recent work [DLSS14] on hardness-of-learning are false.
Joint work with Sarah Allen (CMU) and David Witmer (CMU)
Communication Amid Uncertainty
Madhu Sudan, MSR New England and Harvard
Monday, August 31, 2015 - 1:00pm to 2:30pm
Pierce 213
I will talk about a sequence of works where we investigate basic questions in communication where unreliability can be attributed, not to the channel of communication, but to the lack of perfect synchronization between the communicating players. Topics that will be covered include (some subset of): 1) (One-shot) Compression where sender and receiver of information do not agree on the distribution from which the message is sampled. Can we compress information down to the entropy? 2) Communication complexity when Alice and Bob don't have perfectly shared randomness: Is having shared correlation as good as having perfectly shared randomness? 3) Communication complexity when Alice and Bob don't agree on the function being computed. Can one salvage low-communication protocols with such uncertainty? In most case we have only partial results, and I will describe what we know and the many open questions.
Based on joint works with Clement Canonne, Badih Ghazi, Oded Goldreich, Venkatesan Guruswami, Elad Haramaty, Brendan Juba, Adam Kalai, Pritish Kamath, Sanjeev Khanna, Ilan Komargodski, Pravesh Kothari, Jacob Leshno, and Raghu Meka.