Abstract:
Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data --- data is distributed to processors, each of which has a sublinear (in the input data) amount of memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. This model is stronger than the classical PRAM model, and it is an intriguing question to design algorithms whose running time is smaller than in the PRAM model.
One fundamental graph problem is connectivity. On an undirected graph with $n$ nodes and $m$ edges, $O(\log n)$ round connectivity algorithms have been known for over 35 years. However, no algorithms with better complexity bounds were known. In this work, we give fully scalable, faster algorithms for the connectivity problem, by parameterizing the time complexity as a function of the diameter of the graph. Our main result is a $O(\log D \log\log_{m/n} n)$ time connectivity algorithm for diameter-$D$ graphs, using $\Theta(m)$ total memory. If our algorithm can use more memory, it can terminate in fewer rounds, and there is no lower bound on the memory per processor.
We extend our results to related graph problems such as spanning forest, finding a DFS sequence, exact/approximate minimum spanning forest, and bottleneck spanning forest. We also show that achieving similar bounds for reachability in directed graphs would imply faster boolean matrix multiplication algorithms.
We introduce several new algorithmic ideas. We describe a general technique called double exponential speed problem size reduction which roughly means that if we can use total memory $N$ to reduce a problem from size $n$ to $n/k$, for $k=(N/n)^{\Theta(1)}$ in one phase, then we can solve the problem in $O(\log\log_{N/n} n)$ phases. In order to achieve this fast reduction for graph connectivity, we use a multistep algorithm. One key step is a carefully constructed truncated broadcasting scheme where each node broadcasts neighbor sets to its neighbors in a way that limits the size of the resulting neighbor sets. Another key step is random leader contraction, where we choose a smaller set of leaders than many previous works do.
Abstract:
There is currently a substantial gap between theory and practice in the area of high-dimensional sampling and integration. There are numerous Markov chains that appear to work well in practice for high-dimensional sampling. For each Markov chain, there are seemingly suboptimal (or a lack of) mixing time bounds. Understanding the theoretical frontier of efficiency can help guide algorithms in practice, along with suggesting new approaches and connections to other fields. Notably, there is a well-studied connection between the mixing time of the ball walk and a decades-old fundamental question in convex geometry, known as the Kannan, Lovász, and Simonovits (KLS) conjecture.
In this talk, I will give an overview of the algorithmic approaches used for sampling, integration, and volume computation, while illustrating the geometric and probabilistic tools used to prove the algorithmic efficiency. Additionally, I will discuss progress on this line of work and show an O*(n^3) volume algorithm for well-rounded convex bodies, which was previously suspected to rely on a positive resolution of the KLS conjecture. The theoretical ideas for the algorithms also appear to transfer over to practice, and I will demonstrate a MATLAB implementation that can experimentally sample from or compute the volume of a polytope in a few thousand dimensions.
In addition, I will briefly discuss preliminary work (with Ton Dieker) on estimating high-dimensional Gaussian tails.
Abstract:
Combinatorial auctions have been central to understanding the relative power of efficient algorithms (where input is directly given) versus efficient mechanisms (where input must be solicited from strategic bidders) since AGT's inception as a field. In this talk, we'll specifically study the communication complexity of two-player combinatorial auctions: there is a set M of m items available. Alice has a valuation function A:2^M --> R, and Bob has a valuation function B:2^M --> R. They wish to find a partition of M maximizing A(S) + B(M\S) using poly(m) communication. In this talk, I'll present two results:
1) In joint work with Mark Braverman and Jieming Mao, we study search (find a good allocation) problems versus decision (determine whether a good allocation exists) problems. If one can achieve an X-approximation to the search problem with communication C and R rounds of interaction, a trivial reduction allows one to also achieve an X-approximation to the decision problem with communication C+\log(m) and R+1 rounds of interaction. When valuation functions are fractionally subadditive (XOS), we show essentially that this additional round of interaction is necessary: a (tight) 3/4-approximation for the search problem with poly(m) communication and 1 round of interaction exists, but no 3/4-1/108 approximation for the decision problem with subexp(m) communication and 1 round of interaction exists for the decision problem.
2) In joint work with Tomer Ezra, Michal Feldman, Eric Neyman, and Inbal Talgam-Cohen, we further consider the best achievable guarantee for subadditive valuations. Here, there are numerous trivial 1/2-approximations (which don't even require the subadditivity assumption), including the zero-communication protocol which simply allocates M uniformly at random to Alice or Bob. Surprisingly, we show that any better approximation requires exp(m) communication, resolving an open question of (Dobzinski, Nisan, and Schapira 2005) and also (Feige 2006).
Abstract:
Reconstructing signals based on a small number of potentially noisy samples is a fundamental problem in signal processing. In practice, we are often interested in signals with ``simple'' Fourier transforms -- e.g. those involving frequencies within a bounded range, a small number of frequencies, or a few blocks of frequencies (bandlimited, sparse, and multiband signals, respectively). We generally find that ``simpler'' classes of signals require fewer samples to learn.
It is possible to formalize this tradeoff between sample complexity and simplicity: a continuous signal from a given class can be reconstructed using a number of samples equal to a natural ``statistical dimension'' parameter of the class' Fourier support. In this talk, I will show that, up to logarithmic factors, a universal non-uniform sampling strategy can achieve this optimal complexity for any class of signals. This surprising result yields a simple, practical, and general algorithm for signal reconstruction. For well-studied classes, including bandlimited and sparse signals, our algorithm matches or improves on the state-of-the-art. At the same time, it solves a much broader range of signal fitting problems.
Our work draws on tools from randomized linear algebra and low-rank approximation. I will discuss its connections to classical sampling theory, and to computational results like Slepian, Pollak, and Landau's seminal papers on using prolate spheroidal wave functions to learn bandlimited signals. This project is joint work Haim Avron, Michael Kapralov, Cameron Musco, Ameya Velingker, and Amir Zandieh.
Abstract:
We consider a setting where an auctioneer sells a single item to $n$ potential agents with interdependent values. This captures settings such as valuations for artwork, oil drilling rights, broadcast rights, and many more. In the interdependent value setting, all previous work has assumed a so-called single-crossing condition. Single-crossing means that the impact of agent $i$'s private signal, $s_i$, on her own valuation is greater than the impact of $s_i$ on the valuation of any other agent. It is known that without the single-crossing condition an efficient outcome cannot be obtained. This finding motivates the study of welfare maximization for interdependent valuations through the lens of approximation.
We show that, in general, without the single-crossing condition, one cannot hope to approximate the optimal social welfare any better than the approximation given by assigning the item to a random bidder. Consequently, we introduce two valuation properties that enable positive results. The first is a relaxed, parameterized version of single-crossing; the second is a (parameterized) submodularity condition over the signals. We obtain a host of approximation guarantees under these two notions.
Abstract:
Computing the permanent of non-negative matrices has received a lot of attention over the past two decades. The beautiful result of Jerrum-Sinclair-Vigoda gives a fully polynomial-time approximation scheme for the problem and the proof of Van der Waerden conjecture gives exponential deterministic approximations for it.
On the other hand, we know very little about the computation of the permanent of positive semidefinite matrices. I will talk about various open problems in this area and present our result, which is the first simply exponential approximation for the problem.
Joint work with N. Anari, L. Gurvits, and S. Oveis Gharan.
Abstract: In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes a shortest augmenting path from the newly inserted vertex (denoted SAP) uses at most amortized O(log^2 n) replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any strategy, almost matching the O(log n) lower bound. The previous best strategy achieved amortized O(\sqrt{n}) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014]. For SAP in particular, nothing better than the trivial O(n) bound was known except in special cases.
Thursday, November 8:
Abstract:
To date, the tightest upper and lower-bounds for the active learning of general concept classes have been in terms of a parameter of the learning problem called the splitting index. In this talk, I will discuss this parameter and present the first efficient algorithm that is able to realize this upper bound.
Joint work with Sanjoy Dasgupta.
Abstract: We present PanORAMa, the first Oblivious RAM construction that achieves communication overhead O(logN·loglogN) for database of N blocks and for any block size B=O(logN) while requiring client memory of only a constant number of memory blocks. Our scheme is only an O(loglogN) factor away from the O(logN) lower bound shown by Larsen and Nielsen [CRYPTO '18]. Our construction follows the hierarchical approach to ORAM design and relies on two main building blocks of independent interest: a new oblivious hash table construction with improved amortized O(logN+poly(loglogλ)) communication overhead for security parameter λ and N=poly(λ), assuming its input is randomly shuffled; and a complementary new oblivious random multi-array shuffle construction, which shuffles N blocks of data with communication O(Nloglogλ+NlogNlogλ) when the input has a certain level of entropy. We combine these two primitives to improve the shuffle time in our hierarchical ORAM construction by avoiding heavy oblivious shuffles and leveraging entropy remaining in the merged levels from previous shuffles. As a result, the amortized shuffle cost is asymptotically the same as the lookup complexity in our construction. This is a joint work with Sarvar Patel, Giuseppe Persiano and Mariana Raykova.
Thursday, November 29:
Abstract:
The Burrows-Wheeler Transform (BWT) is a reversible preprocessing step in large scale text compression, and is the basis
of practical storage algorithms (such as the bzip compression program). Alas, the decoding process of BWT is inherently
sequential and requires \Omega(n) time even to retrieve a single character.
We study the succinct data structure problem of locally decoding short substrings of a given text under its compressed BWT, i.e.,
with small additive redundancy r over its Move-To-Front ("bzip") compression. The celebrated (BWT-based) FM-index yield a tradeoff
of r =~ O(n/\sqrt{t}) bits, to decode a single character in O(t) time. We give a near-quadratic improvement r = O~(n\log(t)/t). As a by-product,
we obtain an exponential (in t) improvement on the redundancy of the FM-index for counting pattern-matches on compressed text.
In the interesting regime where the text compresses to n^{1-o(1)} bits, these results provide an exp(t) overall space reduction. For
the local decoding problem of BWT, we also prove an \Omega(n/t^2) cell-probe lower bound for "symmetric" data structures.
We achieve our main result by designing a compressed partial-sums (Rank) data structure over BWT. The key component is a
locally-decodable Move-to-Front (MTF) code: with only O(1) extra bits per block, the decoding time of a single character can be
decreased from \Omega(n) to O(\log n). This result is of independent interest in algorithmic information theory.
This is a recent joint work with Omri Weinstein.