We consider the problem of testing graph cluster structure: given access to a graph $G=(V, E)$, can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generalization of the well-studied problem of testing graph expansion, where one wants to distinguish between the graph having good expansion (i.e. being a good single cluster) and the graph having a sparse cut (i.e. being a union of at least two clusters). A recent work of Czumaj, Peng, and Sohler (STOC'15) gave an ingenious sublinear time algorithm for testing $k$-clusterability in time $\tilde{O}(n^{1/2} \poly(k))$: their algorithm implicitly embeds a random sample of vertices of the graph into Euclidean space, and then clusters the samples based on estimates of Euclidean distances between the points. This yields a very efficient testing algorithm, but only works if the cluster structure is very strong: it is necessary to assume that the gap between conductances of accepted and rejected graphs is at least logarithmic in the size of the graph $G$. In this paper we show how one can leverage more refined geometric information, namely angles as opposed to distances, to obtain a sublinear time tester that works even when the gap is a sufficiently large constant. Our tester is based on the singular value decomposition of a natural matrix derived from random walk transition probabilities from a small sample of seed nodes. We complement our algorithm with a matching lower bound on the query complexity of testing clusterability. Our lower bound is based on a novel property testing problem, which we analyze using Fourier analytic tools. As a byproduct of our techniques, we also achieve new lower bounds for the problem of approximating MAX-CUT value in sublinear time.

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g.,\ estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been studied extensively in the literature, but many natural settings are still not well understood. In this paper we revisit the subgraph (and hypergraph) counting problem in the sketching model, where the algorithm's state as it processes a stream of updates to the graph is a linear function of the stream. This model has recently received a lot of attention in the literature, and has become a standard model for solving dynamic graph streaming problems. In this paper we give a tight bound on the sketching complexity of counting the number of occurrences of a small subgraph $H$ in a bounded degree graph $G$ presented as a stream of edge updates. Specifically, we show that the space complexity of the problem is governed by the fractional vertex cover number of the graph $H$. Our subgraph counting algorithm implements a natural vertex sampling approach, with sampling probabilities governed by the vertex cover of $H$. Our main technical contribution lies in a new set of Fourier analytic tools that we develop to analyze multiplayer communication protocols in the simultaneous communication model, allowing us to prove a tight lower bound. We believe that our techniques are likely to find applications in other settings. Besides giving tight bounds for all graphs $H$, both our algorithm and lower bounds extend to the hypergraph setting, albeit with some loss in space complexity.

The problem of computing the Fourier Transform of a signal whose spectrum is dominated by a small number $k$ of frequencies quickly and using a small number of samples of the signal in time domain (the Sparse FFT problem) has received significant attention recently. It is known how to approximately compute the $k$-sparse Fourier transform in $\approx k\log^2 n$ time [Hassanieh et al'STOC'12], or using the optimal number $O(k\log n)$ of samples [Indyk et al'FOCS'14] in time domain, or come within $(\log\log n)^{O(1)}$ factors of both these bounds simultaneously, but no algorithm achieving the optimal $O(k\log n)$ bound in sublinear time is known. At a high level, sublinear time Sparse FFT algorithms operate by `hashing' the spectrum of the input signal into $\approx k$ `buckets', identifying frequencies that are `isolated' in their buckets, subtracting them from the signal and repeating until the entire signal is recovered. The notion of `isolation' in a `bucket', inspired by applications of hashing in sparse recovery with arbitrary linear measurements, has been the main tool in the analysis of Fourier hashing schemes in the literature. However, Fourier hashing schemes, which are implemented via filtering, tend to be `noisy' in the sense that a frequency that hashes into a bucket contributes a non-negligible amount to neighboring buckets. This leakage to neighboring buckets makes identification and estimation challenging, and the standard analysis based on isolation becomes difficult to use without losing $\omega(1)$ factors in sample complexity. In this paper we propose a new technique for analysing noisy hashing schemes that arise in Sparse FFT, which we refer to as isolation on average. We apply this technique to two problems in Sparse FFT: estimating the values of a list of frequencies using few samples and computing Sparse FFT itself, achieving sample-optimal results in $k\log^{O(1)} n$ time for both. We feel that our approach will likely be of interest in designing Fourier sampling schemes for more general settings (e.g. model based Sparse FFT).

In the communication problem $\mathbf{UR}$ (universal relation), Alice and Bob respectively receive $x, y \in\{0,1\}^n$ with the promise that $x\neq y$. The last player to receive a message must output an index $i$ such that $x_i\neq y_i$. We prove that the randomized one-way communication complexity of this problem in the public coin model is exactly $\Theta(\min\{n,\log(1/\delta)\log^2(\frac n{\log(1/\delta)})\})$ for failure probability $\delta$. Our lower bound holds even if promised $\mathop{support}(y)\subset \mathop{support}(x)$. As a corollary, we obtain optimal lower bounds for $\ell_p$-sampling in strict turnstile streams for $0\le p < 2$, as well as for the problem of finding duplicates in a stream. Our lower bounds do not need to use large weights, and hold even if promised $x\in\{0,1\}^n$ at all points in the stream. We give two different proofs of our main result. The first proof demonstrates that any algorithm $\mathcal A$ solving sampling problems in turnstile streams in low memory can be used to encode subsets of $[n]$ of certain sizes into a number of bits below the information theoretic minimum. Our encoder makes adaptive queries to $\mathcal A$ throughout its execution, but done carefully so as to not violate correctness. This is accomplished by injecting random noise into the encoder's interactions with $\mathcal A$, which is loosely motivated by techniques in differential privacy. Our correctness analysis involves understanding the ability of $\mathcal A$ to correctly answer adaptive queries which have positive but bounded mutual information with $\mathcal A$'s internal randomness, and may be of independent interest in the newly emerging area of adaptive data analysis with a theoretical computer science lens. Our second proof is via a novel randomized reduction from Augmented Indexing \cite{MiltersenNSW98} which needs to interact with $\mathcal A$ adaptively. To handle the adaptivity we identify certain likely interaction patterns and union bound over them to guarantee correct interaction on all of them. To guarantee correctness, it is important that the interaction hides some of its randomness from $\mathcal A$ in the reduction.

Random Fourier features is one of the most popular techniques for scaling up kernel methods, such as kernel ridge regression. However, despite impressive empirical results, the statistical properties of random Fourier features are still not well understood. In this paper we take steps toward filling this gap. Specifically, we approach random Fourier features from a spectral matrix approximation point of view, give tight bounds on the number of Fourier features required to achieve a spectral approximation, and show how spectral matrix approximation bounds imply statistical guarantees for kernel ridge regression. Qualitatively, our results are twofold: on one hand, we show that random Fourier feature approximation can provably speed up kernel ridge regression under reasonable assumptions. At the same time, we show that the method is suboptimal, and sampling from a modified distribution in Fourier space, given by the leverage function of the kernel, yields provably better performance. We study this optimal sampling distribution for the Gaussian kernel, achieving a nearly complete characterization for the case of one-dimensional bounded datasets. Based on this characterization, we propose an efficient sampling scheme with guarantees superior to random Fourier features in this regime.

The problem of approximately computing the $k$ dominant Fourier coefficients of a vector $X$ quickly, and using few samples in time domain, is known as the Sparse Fourier Transform (sparse FFT) problem. A long line of work on the sparse FFT has resulted in algorithms with $O(k\log n\log (n/k))$ runtime [Hassanieh et al., STOC'12] and $O(k\log n)$ sample complexity [Indyk et al., FOCS'14]. These results are proved using non-adaptive algorithms, and the latter $O(k\log n)$ sample complexity result is essentially the best possible under the sparsity assumption alone: It is known that even adaptive algorithms must use $\Omega((k\log(n/k))/\log\log n)$ samples [Hassanieh et al., STOC'12]. By adaptive, we mean being able to exploit previous samples in guiding the selection of further samples. This paper revisits the sparse FFT problem with the added twist that the sparse coefficients approximately obey a $(k_0,k_1)$-block sparse model. In this model, signal frequencies are clustered in $k_0$ intervals with width $k_1$ in Fourier space, where $k= k_0k_1$ is the total sparsity. Signals arising in applications are often well approximated by this model with $k_0\ll k$. Our main result is the first sparse FFT algorithm for $(k_0, k_1)$-block sparse signals with the sample complexity of $O^*(k_0k_1 + k_0\log(1+ k_0)\log n)$ at constant signal-to-noise ratios, and sublinear runtime. A similar sample complexity was previously achieved in the works on {\em model-based compressive sensing} using random Gaussian measurements, but used $\Omega(n)$ runtime. To the best of our knowledge, our result is the first sublinear-time algorithm for model based compressed sensing, and the first sparse FFT result that goes below the $O(k\log n)$ sample complexity bound. Interestingly, the aforementioned model-based compressive sensing result that relies on Gaussian measurements is non-adaptive, whereas our algorithm crucially uses {\em adaptivity} to achieve the improved sample complexity bound. We prove that adaptivity is in fact necessary in the Fourier setting: Any non-adaptive algorithm must use $\Omega(k_0k_1\log \frac{n}{k_0k_1})$ samples for the $(k_0,k_1$)-block sparse model, ruling out improvements over the vanilla sparsity assumption. Our main technical innovation for adaptivity is a new randomized energy-based importance sampling technique that may be of independent interest.

We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. We show that there exists a constant $\epsilon_* > 0$ such that any randomized streaming algorithm that computes a $(1+\epsilon_*)$-approximation to MAX-CUT requires $\Omega(n)$ space on an $n$ vertex graph. By contrast, there are algorithms that produce a $(1+\epsilon)$-approximation in space $O(n/\epsilon^2)$ for every $\epsilon > 0$. Our result is the first linear space lower bound for the task of approximating the max cut value and partially answers an open question from the literature. The prior state of the art ruled out $(2-\epsilon)$-approximation in $\tilde{O}(\sqrt{n})$ space or $(1+\epsilon)$-approximation in $n^{1-O(\epsilon)}$ space, for any $\epsilon > 0$. Previous lower bounds for the MAX-CUT problem relied, in essence, on a lower bound on the communication complexity of the following task: Several players are each given some edges of a graph and they wish to determine if the union of these edges is $\epsilon$-close to forming a bipartite graph, using one-way communication. The previous works proved a lower bound of $\Omega(\sqrt{n})$ for this task when $\epsilon=1/2$, and $n^{1-O(\epsilon)}$ for every $\epsilon>0$, even when one of the players is given a candidate bipartition of the graph and the graph is promised to be bipartite with respect to this partition or $\epsilon$-far from bipartite. This added information was essential in enabling the previous analyses but also yields a weak bound since, with this extra information, there is an $n^{1-O(\epsilon)}$ communication protocol for this problem. In this work, we give an $\Omega(n)$ lower bound on the communication complexity of the original problem (without the extra information) for $\epsilon=\Omega(1)$ in the three-player setting. Obtaining this $\Omega(n)$ lower bound on the communication complexity is the main technical result in this paper. We achieve it by a delicate choice of distributions on instances as well as a novel use of the convolution theorem from Fourier analysis combined with graph-theoretic considerations to analyze the communication complexity.

Have you ever wanted to multiply an $n \times d$ matrix $X$, with $n \gg d$, on the left by an $m \times n$ matrix $\tilde G$ of i.i.d. Gaussian random variables, but could not afford to do it because it was too slow? In this work we propose a new randomized $m \times n$ matrix $T$, for which one can compute $T \cdot X$ in only $O(\text{nnz}(X)) + \tilde O(m^2 \cdot d^{3})$ time, for which the total variation distance between the distributions $T \cdot X$ and $\tilde G \cdot X$ is as small as desired, i.e., less than any positive constant. Here $\text{nnz}(X)$ denotes the number of non-zero entries of $X$. Assuming $\text{nnz}(X) \gg m^2 \cdot d^{3}$, this is a significant savings over the naive $O(\text{nnz}(X) m)$ time to compute $\tilde G \cdot X$. Moreover, since the total variation distance is small, we can provably use $T \cdot X$ in place of $\tilde G \cdot X$ in any application and have the same guarantees as if we were using $\tilde G \cdot X$, up to a small positive constant in error probability. We apply this transform to nonnegative matrix factorization (NMF) and support vector machines (SVM).

We consider the problem of computing a $k$-sparse approximation to the Fourier transform of a length $N$ signal. Our main result is a randomized algorithm for computing such an approximation (i.e. achieving the $\ell_2/\ell_2$ sparse recovery guarantees using Fourier measurements) using $O_d(k\log N\log\log N)$ samples of the signal in time domain that runs in time $O_d(k\log^{d+3} N)$, where $d\geq 1$ is the dimensionality of the Fourier transform. The sample complexity matches the lower bound of $\Omega(k\log (N/k))$ for non-adaptive algorithms due to~\cite{DIPW} for any $k\leq N^{1-\delta}$ for a constant $\delta>0$ up to an $O(\log\log N)$ factor. Prior to our work a result with comparable sample complexity $k\log N \log^{O(1)}\log N$ and sublinear runtime was known for the Fourier transform on the line~\cite{IKP}, but for any dimension $d\geq 2$ previously known techniques either suffered from a $\text{poly}(\log N)$ factor loss in sample complexity or required $\Omega(N)$ runtime.

The problem of counting occurrences of query graphs in a large data graph, known as subgraph counting, is fundamental to several domains such as genomics and social network analysis. Many important special cases (e.g. triangle counting) have received significant attention. Color coding is a very general and powerful algorithmic technique for subgraph counting. Color coding has been shown to be effective in several applications, but scalable implementations are only known for the special case of tree queries (i.e. queries of treewidth one). In this paper we present the first efficient distributed implementation for color coding that goes beyond tree queries: our algorithm applies to any query graph of treewidth 2. Since tree queries can be solved in time linear in the size of the data graph, our contribution is the first step into the realm of colour coding for queries that require superlinear running time in the worst case. This superlinear complexity leads to significant load balancing problems on graphs with heavy tailed degree distributions. Our algorithm structures the computation to work around high degree nodes in the data graph, and achieves very good runtime and scalability on a diverse collection of data and query graph pairs as a result. We also provide theoretical analysis of our algorithmic techniques, showing asymptotic improvements in runtime on random graphs with power law degree distributions, a popular model for real world graphs.

Locality Sensitive Hashing (LSH) has emerged as the method of choice for high dimensional similarity search, a classical problem of interest in numerous applications. LSH-based solutions require that each data point be inserted into a number $A$ of hash tables, after which a query can be answered by performing $B$ lookups. The original LSH solution of [IM98] showed for the first time that both $A$ and $B$ can be made sublinear in the number of data points. Unfortunately, the classical LSH solution does not provide any tradeoff between insert and query complexity, whereas for data (respectively, query) intensive applications one would like to minimize insert time by choosing a smaller $A$ (respectively, minimize query time by choosing a smaller $B$). A partial remedy for this is provided by Entropy LSH [Pan06], which allows to make either inserts or queries essentially constant time at the expense of a loss in the other parameter, but no algorithm that achieves a smooth tradeoff is known. In this paper, we present an algorithm for performing similarity search under the Euclidean metric that resolves the problem above. Our solution is inspired by Entropy LSH, but uses a very different analysis to achieve a smooth tradeoff between insert and query complexity. Our results improve upon or match, up to lower order terms in the exponent, best known data-oblivious algorithms for the Euclidean metric.

We consider the problem of estimating the value of max cut in a graph in the streaming model of computation. At one extreme, there is a trivial $2$-approximation for this problem that uses only $O(\log n)$ space, namely, count the number of edges and output half of this value as the estimate for max cut value. On the other extreme, if one allows $\tilde{O}(n)$ space, then a near-optimal solution to the max cut value can be obtained by storing an $\tilde{O}(n)$-size sparsifier that essentially preserves the max cut. An intriguing question is if poly-logarithmic space suffices to obtain a non-trivial approximation to the max-cut value (that is, beating the factor $2$). It was recently shown that the problem of estimating the size of a maximum matching in a graph admits a non-trivial approximation in poly-logarithmic space.
Our main result is that any streaming algorithm that breaks the $2$-approximation barrier requires $\tilde{\Omega}(\sqrt{n})$ space even if the edges of the input graph are presented in random order. Our result is obtained by exhibiting a distribution over graphs which are either bipartite or $\frac{1}{2}$-far from being bipartite, and establishing that $\tilde{\Omega}(\sqrt{n})$ space is necessary to differentiate between these two cases. Thus as a direct corollary we obtain that $\tilde{\Omega}(\sqrt{n})$ space is also necessary to test if a graph is bipartite or $\frac{1}{2}$-far from being bipartite. We also show that for any $\epsilon > 0$, any streaming algorithm that obtains a $(1 + \epsilon)$-approximation to the max cut value when edges arrive in adversarial order requires $n^{1 - O(\epsilon)}$ space, implying that $\Omega(n)$ space is necessary to obtain an arbitrarily good approximation to the max cut value.

We present the first single pass algorithm for computing spectral sparsifiers of graphs in the dynamic semi-streaming model. Given a single pass over a stream containing insertions and deletions of edges to a graph $G$, our algorithm maintains a randomized linear sketch of the incidence matrix of $G$ into dimension $O(\frac{1}{\epsilon^2}n\text{poly}(\log n))$. Using this sketch, at any point, the algorithm can output a $(1 \pm \epsilon)$ spectral sparsifier for $G$ with high probability.
While $O(\frac{1}{\epsilon^2} n \text{poly}(\log n))$ space algorithms are known for computing cut sparsifiers in dynamic streams [AGM12b, GKP12] and spectral sparsifiers in insertion-only streams [KL11], prior to our work, the best known single pass algorithm for maintaining spectral sparsifiers in dynamic streams required sketches of dimension $\Omega(\frac{1}{\epsilon^2}n^{5/3})$ [AGM14].
To achieve our result, we show that, using a coarse sparsifier of $G$ and a linear sketch of $G$'s incidence matrix, it is possible to sample edges by effective resistance, obtaining a spectral sparsifier of arbitrary precision. Sampling from the sketch requires a novel application of $\ell_2/\ell_2$ sparse recovery, a natural extension of the $\ell_0$ methods used for cut sparsifiers in [AGM12b]. Recent work of [MP12] on row sampling for matrix approximation gives a recursive approach for obtaining the required coarse sparsifiers.
Under certain restrictions, our approach also extends to the problem of maintaining a spectral approximation for a general matrix $A^\top A$ given a stream of updates to rows in $A$.

We give an algorithm for $\ell_2/\ell_2$ sparse recovery from Fourier measurements using $O(k\log N)$ samples, matching the lower bound of [DIPW] for non-adaptive algorithms up to constant factors for any $k\leq N^{1-\delta}$. The algorithm runs in $\tilde O(N)$ time. Our algorithm extends to higher dimensions, leading to sample complexity of $O_d(k\log N)$, which is optimal up to constant factors for any $d=O(1)$. These are the first sample optimal algorithms for these problems.
A preliminary experimental evaluation indicates that our algorithm has empirical sampling complexity comparable to that of other recovery methods known in the literature, while providing strong provable guarantees on the recovery quality.

Linear sketching is a popular technique for computing in dynamic streams, where one needs to handle both insertions and deletions of elements. The underlying idea of taking randomized linear measurements of input data has been extremely successful in providing space-efficient algorithms for classical problems such as frequency moment estimation and computing heavy hitters, and was very recently shown to be a powerful technique for solving graph problems in dynamic streams [AGM'12]. Ideally, one would like to obtain algorithms that use one or a small constant number of passes over the data and a small amount of space (i.e. sketching dimension) to preserve some useful properties of the input graph presented as a sequence of edge insertions and edge deletions.
In this paper, we concentrate on the problem of constructing linear sketches of graphs that (approximately) preserve the spectral information of the graph in a few passes over the stream. We do so by giving the first sketch-based algorithm for constructing multiplicative graph spanners in only two passes over the stream. Our spanners use $\tilde{O}(n^{1+1/k})$ bits of space and have stretch $2^k$. While this stretch is larger than the conjectured optimal $2k-1$ for this amount of space, we show for an appropriate $k$ that it implies the first $2$-pass spectral sparsifier with $n^{1+o(1)}$ bits of space. Previous constructions of spectral sparsifiers in this model with a constant number of passes would require $n^{1+c}$ bits of space for a constant $c > 0$. We also give an algorithm for constructing spanners that provides an additive approximation to the shortest path metric using a single pass over the data stream, also achieving an essentially best possible space/approximation tradeoff.

We present a streaming algorithm that makes one pass over the edges of an unweighted graph presented in random order, and produces a polylogarithmic approximation to the size of the maximum matching in the graph, while using only polylogarithmic space. Prior to this work the only approximations known were a folklore $\tilde{O}(\sqrt{n})$ approximation with polylogarithmic space in an $n$ vertex graph and a constant approximation with $\Omega(n)$ space. Our work thus gives the first algorithm where both the space and approximation factors are smaller than any polynomial in $n$.
Our algorithm is obtained by effecting a streaming implementation of a simple ``local'' algorithm that we design for this problem. The local algorithm produces a $O(k\cdot n^{1/k})$ approximation to the size of a maximum matching by exploring the radius $k$ neighborhoods of vertices, for any parameter $k$. We show, somewhat surprisingly, that our local algorithm can be implemented in the streaming setting even for $k = \Omega(\log n/\log\log n)$. Our analysis exposes some of the problems that arise in such conversions of local algorithms into streaming ones, and gives techniques to overcome such problems.

We consider the problem of computing a $k$-sparse approximation to the discrete Fourier transform of an $n$-dimensional signal. Our main result is a randomized algorithm that computes such an approximation using $O(k \log n (\log\log n)^{O(1)})$ signal samples in time $O(k \log^2 n (\log\log n)^{O(1)})$, assuming that the entries of the signal are polynomially bounded. The sampling complexity improves over the recent bound of $O(k \log n \log (n/k))$ given in [HIKP12], and matches the lower bound of $\Omega(k \log (n/k)/\log \log n)$ from the same paper up to $\mbox{poly}(\log \log n)$ factors when $k=O(n^{1-\delta})$ for a constant $\delta>0$.

In this paper we present improved bounds for approximating maximum matchings in bipartite graphs in the streaming model. First, we consider the question of how well maximum matching can be approximated in a single pass over the input when $\tilde O(n)$ space is allowed, where $n$ is the number of vertices in the input graph. Two natural variants of this problem have been considered in the literature: (1) the edge arrival setting, where edges arrive in the stream and (2) the vertex arrival setting, where vertices on one side of the graph arrive in the stream together with all their incident edges. The latter setting has also been studied extensively in the context of online algorithms, where each arriving vertex has to either be matched irrevocably or discarded upon arrival.
In the online setting, the celebrated algorithm of Karp-Vazirani-Vazirani achieves a $1-1/e$ approximation by crucially using randomization (and using $\tilde O(n)$ space). Despite the fact that the streaming model is less restrictive in that the algorithm is not constrained to match vertices irrevocably upon arrival, the best known approximation in the streaming model with vertex arrivals and $\tilde O(n)$ space is the same factor of $1-1/e$.
Our main result in this paper shows that no (possibly randomized) single pass streaming algorithm constrained to use $\tilde O(n)$ space can achieve a better than $1-1/e$ approximation to maximum matching, even in the vertex arrival setting. This leads to the striking conclusion that no single pass streaming algorithm can get any advantage over online algorithms unless it uses significantly more than $\tilde O(n)$ space. Additionally, our bound yields the best known impossibility result for approximating matchings in the edge arrival model (improving upon the bound of $2/3$ proved by Goel at al[SODA'12]).
We also consider the problem of approximating matchings in multiple passes in the vertex arrival setting. We show that a simple fractional load balancing approach achieves approximation ratio $1-e^{-k}k^{k-1}/(k-1)!=1-\frac1{\sqrt{2\pi k}}+o(1/k)$ in $k$ passes using linear space. Thus, our algorithm achieves the best possible $1-1/e$ approximation in a single pass and improves upon the $1-O(\sqrt{\log\log k/k})$ approximation in $k$ passes due to Ahn and Guha[ICALP'11]. Additionally, our approach yields an efficient solution to the Gap-Existence problem considered by Charles et al[EC'10].

Low rank approximation is a fundamental computational primitive widely used in data analysis. In many applications the dataset that the algorithm operates on may contain sensitive information about contributing individuals (e.g. user/movie ratings in the Netflix challenge), motivating the need to design low rank approximation algorithms that preserve privacy of individual entries of the input matrix.
In this paper, we give a polynomial time algorithm that, given a privacy parameter $\epsilon>0$, for a symmetric matrix $A$, outputs an $\epsilon$-differentially approximation to the principal eigenvector of $A$, and then show how this algorithm can be used to obtain a differentially private rank-$k$ approximation. We also provide lower bounds showing that our utility/privacy tradeoff is close to best possible.
While there has been significant progress on this problem recently for a weaker notion of privacy, namely $(\epsilon, \delta)$-differential privacy [HR12, BBDS12], our result is the first to achieve $(\epsilon, 0)$-differential privacy guarantees with a near-optimal utility/privacy tradeoff in polynomial time.

We prove that no online algorithm (even randomized, against an oblivious adversary) is better than 1/2-competitive for welfare maximization with coverage valuations, unless NP = RP. Since the Greedy algorithm is known to be 1/2-competitive for monotone submodular valuations, of which coverage is a special case, this proves that Greedy provides the optimal competitive ratio. On the other hand, we prove that Greedy in a stochastic setting with i.i.d. items and valuations satisfying diminishing returns is (1-1/e)-competitive, which is optimal even for coverage valuations, unless NP=RP. For online budget-additive allocation, we prove that no algorithm can be 0.612-competitive with respect to a natural LP which has been used previously for this problem.

Modern cloud infrastructure providers allow customers to rent compute capability in the form of a network of virtual machines (VMs) with bandwidth guarantees between pairs of VMs. Typical requests are in the form of a chain of VMs with an uplink bandwidth to the gateway node of the network (rooted path requests), and most data center architectures route network packets along a spanning tree of the physical network. VMs are instantiated inside servers which reside at the leaves of this network, leading to the following optimization problem: given a rooted tree network $T$ and a set of rooted path requests, find an embedding of the requests that minimize link congestion.
Our main result is an algorithm that given a rooted tree network $T$ with $n$ leaves and set of weighted rooted path requests, embeds a $1-\epsilon$ fraction of the requests with congestion at most $poly(\log{n}, \log \theta ,\epsilon^{-1})\cdot\text{OPT}$ (approximation is necessary since the problem is NP-hard). Here $\text{OPT}$ is the congestion of the optimal embedding and $\theta$ is the ratio of the maximum to minimum weights of the path requests. We also obtain a $O(H\log n/\epsilon^2)$ approximation if node capacities can be augmented by a $1+\epsilon$ factor (here $H$ is the height of the tree). Our algorithm applies a randomized rounding scheme based on Group Steiner Tree rounding to a novel LP relaxation of the set of subtrees of $T$ with a given number of leaves that may be of independent interest.

We give new lower bounds for randomized NNS data structures in the cell probe model based on robust metric expansion for two metric spaces: $l_\infty$ and Earth Mover Distance (EMD) in high dimensions. In particular, our results imply stronger non-embedability for these metric spaces into $l_1$. The main components of our approach are a strengthening of the isoperimetric inequality for the distribution on $l_\infty$ introduced by Andoni et al [FOCS'08] and a robust isoperimetric inequality for EMD on quotients of the boolean hypercube.

In this paper we introduce a new notion of distance between nodes in a graph that we refer to as robust connectivity . Robust connectivity between a pair of nodes $u$ and $v$ is parameterized by a threshold $\kappa$ and intuitively captures the number of paths between $u$ and $v$ of length at most $\kappa$. Using this new notion of distances, we show that any black box algorithm for constructing a spanner can be used to construct a spectral sparsifier. We show that given an undirected weighted graph $G$, simply taking the union of spanners of a few (polylogarithmically many) random subgraphs of $G$ obtained by sampling edges at different probabilities, after appropriate weighting, yields a spectral sparsifier of $G$. We show how this be done in $\tilde O(m)$ time, producing a sparsifier with $\tilde O(n/\epsilon^2)$ edges. While the cut sparsifiers of Benczur and Karger are based on weighting edges according to (inverse) strong connectivity, and the spectral sparsifiers are based on resistance, our method weights edges using the robust connectivity measure. The main property that we use is that this new measure is always greater than the resistance when scaled by a factor of $O(\kappa)$ ($\kappa$ is chosen to be $O(\log n)$), but, just like resistance and connectivity, has a bounded sum, i.e. $\tilde O(n)$, over all the edges of the graph.

  Consider the following communication problem. Alice holds a graph $G_A=(P, Q, E_A)$ and Bob holds a graph $G_B=(P, Q, E_B)$, where $|P|=|Q|=n$. Alice is allowed to send Bob a message $m$ that depends only on the graph $G_A$. Bob must then output a matching $M\subseteq E_A\cup E_B$. What is the minimum message size of the message $m$ that Alice sends to Bob that allows Bob to recover a matching of size at least $(1-\epsilon)$ times the maximum matching in $G_A\cup G_B$? The minimum message length is the one-round communication complexity of approximating bipartite matching. It is easy to see that the one-round communication complexity also gives a lower bound on the space needed by a one-pass streaming algorithm to compute a $1-\epsilon$-approximate bipartite matching. The focus of this work is to understand one-round communication complexity and one-pass streaming complexity of maximum bipartite matching. In particular, how well can one approximate these problems with linear communication and space? Prior to our work, only a $\frac{1}{2}$-approximation was known for both these problems.
  In order to study these questions, we introduce the concept of an $\epsilon$-matching cover of a bipartite graph $G$, which is a sparse subgraph of the original graph that preserves the size of maximum matching between every subset of vertices to within an additive $\epsilon n$ error. We give a polynomial time construction of a $\frac{1}{2}$-matching cover of size $O(n)$ with some crucial additional properties, thereby showing that Alice and Bob can achieve a $\frac{2}{3}$-approximation with a message of size $O(n)$. While we do not provide bounds on the size of $\epsilon$-matching covers for $\epsilon<1/2$, we prove that in general, the size of the smallest $\epsilon$-matching cover of a graph $G$ on $n$ vertices is essentially equal to the size of the largest so-called $\epsilon$-Ruzsa Szemeredi graph on $n$ vertices. We use this connection to show that for any $\delta>0$, a $(\frac{2}{3}+\delta)$-approximation requires a communication complexity of $n^{1+\Omega(1/\log\log n)}$.
  We also consider the natural restrictingon of the problem in which $G_A$ and $G_B$ are only allowed to share vertices on one side of the bipartition, which is motivated by applications to one-pass streaming with vertex arrivals. We show that a $\frac{3}{4}$-approximation can be achieved with a linear size message in this case, and this result is best possible in that super-linear space is needed to achieve any better approximation.
  Finally, we build on our techniques for the restricted version above to design one-pass streaming algorithm for the case when vertices on one side are known in advance, and the vertices on the other side arrive in a streaming manner together with all their incident edges. This is precisely the setting of the celebrated $(1- \frac{1}{e})$-competitive randomized algorithm of Karp-Vazirani-Vazirani (KVV) for the online bipartite matching problem. We present here the first deterministic one-pass streaming $(1-\frac{1}{e})$-approximation algorithm using $O(n)$ space for this setting.

Consider a sequence of bits where we are trying to predict the next bit from the previous bits. Assume we are allowed to say `predict 0' or `predict 1', and our payoff is $+1$ if the prediction is correct and $-1$ otherwise. We will say that at each point in time the loss of an algorithm is the number of wrong predictions minus the number of right predictions so far. In this paper we are interested in algorithms that have essentially zero (expected) loss over any string at any point in time and yet have small regret with respect to always predicting $0$ or always predicting $1$. For a sequence of length $T$ our algorithm has regret $5\epsilon T $ and loss $2\sqrt{T}e^{-\epsilon^2 T} $ in expectation for all strings. We show that the tradeoff between loss and regret is optimal up to constant factors.
  The algorithm extends to the general setting of $N$ experts, yielding essentially zero loss with respect to the special expert and optimal loss/regret tradeoff, improving upon the results of Even-Dar et al (COLT'07) and settling the main question left open in their paper.
  The strong loss bounds of the algorithm have some surprising consequences. First, we obtain a parameter free algorithm for the experts problem that has optimal regret bounds with respect to $k$-shifting optima, i.e. bounds with respect to the optimum that is allowed to change arms multiple times. Moreover, for any window of size $n$ the regret of our algorithm to any expert never exceeds $O(\sqrt{n(\log N+\log T)})$, where $N$ is the number of experts and $T$ is the time horizon, while maintaining the essentially zero loss property.

  We study the space and time complexity of approximating distributions of $l$-step random walks in simple (possibly directed) graphs $G$. While very efficient algorithms for obtaining additive $\epsilon$-approximations have been developed in the literature, no non-trivial results with multiplicative guarantees are known, and obtaining such approximations is the main focus of this paper. Specifically, we ask the following question: given a bound $S$ on the space used, what is the minimum threshold $t>0$ such that $l$-step transition probabilities for all pairs $u, v\in V$ such that $P_{uv}^l\geq t$ can be approximated within a $1\pm \epsilon$ factor? How fast can an approximation be obtained?
  We show that the following surprising behavior occurs. When the bound on the space is $S=o(n^2/d)$, where $d$ is the minimum out-degree of $G$, no approximation can be achieved for non-trivial values of the threshold $t$. However, if an extra factor of $s$ space is allowed, i.e. $S=\tilde \Omega(sn^2/d)$ space, then the threshold $t$ is exponentially small in the length of the walk $l$ and even very small transition probabilities can be approximated up to a $1\pm \epsilon$ factor. One instantiation of these guarantees is as follows: any almost regular directed graph can be represented in $\tilde O(l n^{3/2+\epsilon})$ space such that all probabilities larger than $n^{-10}$ can be approximated within a $(1\pm \epsilon)$ factor as long as $l\geq 40/\epsilon^2$. Moreover, we show how to estimate of such probabilities faster than matrix multiplication time.
  For undirected graphs, we also give small space oracles for estimating $P^l_{uv}$ using a notion of bicriteria approximation based on approximate distance oracles of Thorup and Zwick [STOC'01].

  We study the online stochastic matching problem in a form motivated by Internet display advertisement. Recently, Feldman et al. gave an algorithm that achieves $0.6702$ competitive ratio, thus breaking through the $1-1/e$ barrier. One of the questions left open in their work is to obtain a better competitive ratio by generalizing their two suggested matchings (TSM) algorithm to $d$-suggested matchings ($d$-SM).
  We show that the best competitive ratio that can be obtained with the static analysis used in the $d$-SM algorithm is upper bounded by $0.76$, even for the special case of $d$-regular graphs, thus suggesting that a dynamic analysis may be needed to improve the competitive ratio significantly. We make the first step in this direction by showing that the RANDOM algorithm, which assigns an impression to a randomly chosen eligible advertiser, achieves $1-e^{-d}d^d/d!=1-O(1/\sqrt{d})$ competitive ratio for $d$-regular graphs, which converges to $1$ as $d$ increases. On the hardness side, we improve the upper bound of $0.989$ on the competitive ratio of any online algorithm obtained by Feldman et al. to $1-1/(e+e^2)\approx 0.902$. Finally, we show how to modify the TSM algorithm to obtain an improved $0.699$ approximation for general bipartite graphs.

  In this paper we consider the well-studied problem of finding a perfect matching in a $d$-regular bipartite graph on $2n$ nodes with $m=nd$ edges. The best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time $O(m\sqrt{n})$. In regular bipartite graphs, however, a matching is known to be computable in $O(m)$ time (due to Cole, Ost, and Schirra). In a recent line of work by Goel, Kapralov, and Khanna the $O(m)$ time algorithm was improved first to $\tilde O\left(\min\{m, n^{2.5}/d\}\right)$ and then to $\tilde O\left(\min\{m, n^2/d\}\right)$. It was also shown that the latter algorithm is optimal up to polylogarithmic factors among all algorithms that use non-adaptive uniform sampling to reduce the size of the graph as a first step.
  In this paper, we give a randomized algorithm that finds a perfect matching in a $d$-regular graph and runs in $O(n\log n)$ time (both in expectation and with high probability). The algorithm performs an appropriately truncated random walk on a modified graph to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of (non-adaptive) uniform sampling established in earlier work. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time $O(n\log^2 n)$, with $O(m)$ pre-processing time; this gives a simple $O(m+mn\log^2 n)$ time algorithm for finding the Birkhoff-von Neumann decomposition of a doubly stochastic matrix.
  We show that randomization is crucial for obtaining $o(nd)$ time algorithms by establishing an $\Omega(nd)$ lower bound for any deterministic algorithm. We also show that there does not exist a randomized algorithm that finds a matching in a regular bipartite multigraph and takes $o(n\log n)$ time with high probability.

  We consider the well-studied problem of finding a perfect matching in $d$-regular bipartite graphs with $2n$ vertices and $m = nd$ edges. While the best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes $O(m \sqrt{n})$ time, in regular bipartite graphs, a perfect matching is known to be computable in $O(m)$ time. Very recently, the $O(m)$ bound was improved to $O(\min\{m, \frac{n^{2.5}\ln n}{d}\})$ expected time, an expression that is bounded by $\tilde{O}(n^{1.75})$. In this paper, we further improve this result by giving an $O(\min\{m, \frac{n^2\ln^3 n}{d}\})$ expected time algorithm for finding a perfect matching in regular bipartite graphs; as a function of $n$ alone, the algorithm takes expected time $O((n\ln n)^{1.5})$.
  To obtain this result, we design and analyze a two-stage sampling scheme that reduces the problem of finding a perfect matching in a regular bipartite graph to the same problem on a subsampled bipartite graph with $O(n\ln n)$ edges. The first-stage is a sub-linear time uniform sampling that reduces the size of the input graph while maintaining certain structural properties of the original graph. The second-stage is a non-uniform sampling that takes linear-time (on the reduced graph) and outputs a graph with $O(n\ln n)$ edges, while preserving a matching with high probability. This matching is then recovered using the Hopcroft-Karp algorithm. While the standard analysis of Hopcroft-Karp also gives us an $\tilde{O}(n^{1.5})$ running time, we present a tighter analysis for our special case that results in the stronger $\tilde{O}(\min\{m, \frac{n^2}{d} \})$ time mentioned earlier.
  Our proof of correctness of this sampling scheme uses a new correspondence theorem between cuts and Hall's theorem ``witnesses'' for a perfect matching in a bipartite graph that we prove. We believe this theorem may be of independent interest; as another example application, we show that a perfect matching in the support of an $n \times n$ doubly stochastic matrix with $m$ non-zero entries can be found in expected time $\tilde{O}(m + n^{1.5})$.

We adapt a probabilistic latent variable model, namely GaP (Gamma-Poisson), to ad targeting in the contexts of sponsored search (SS) and behaviorally targeted (BT) display advertising. We also approach the important problem of ad posi- tional bias by formulating a one-latent-dimension GaP factorization. Learning from click-through data is intrinsically large scale, even more so for ads. We scale up the algorithm to terabytes of real-world SS and BT data that contains hundreds of millions of users and hundreds of thousands of features, by leveraging the scalability characteristics of the algorithm and the inherent structure of the problem including data sparsity and locality. Specifically, we demonstrate two somewhat orthogonal philosophies of scaling algorithms to large-scale problems, through the SS and BT implementations, respectively. Finally, we report the experimental results using Yahoo's vast datasets, and show that our approach substantially outperform the state-of-the-art methods in prediction accuracy. For BT in particular, the ROC area achieved by GaP is exceeding 0.95, while one prior approach using Poisson regression yielded 0.83. For computational performance, we compare a single-node sparse implementation with a parallel implementation using Hadoop MapReduce, the results are counterintuitive yet quite interesting. We therefore provide insights into the underlying principles of large-scale learning.

In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time $O(mn)$, dates back to König's work in 1916 (here $m=nd$ is the number of edges in the graph, $2n$ is the number of vertices, and $d$ is the degree of each node). The currently most efficient algorithm takes time $O(m)$, and is due to Cole, Ost, and Schirra. We improve this running time to $O(\min\{m, \frac{n^{2.5}\ln n}{d}\})$; this minimum can never be larger than $O(n^{1.75}\sqrt{\ln n})$. We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a $d$-regular bipartite graph independently with a probability $p = O(\frac{n\ln n}{d^2})$ then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to non-existence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Karger's sampling theorem for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the $O(m\sqrt{n})$ algorithm (due to Hopcroft and Karp) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to poly-logarithmic factors (in fact, up to $\ln^2 n$).