A celebrated result of Johansson in graph theory states that every triangle-free graph of maximum degree Δ can be properly colored with O(Δ/lnΔ) colors, improving upon the "greedy bound" of Δ+1 coloring in general graphs. This coloring can also be found in polynomial time. We present an algorithm for maintaining an O(Δ/lnΔ) coloring of a dynamically changing triangle-free graph that undergoes edge insertions and deletions. The algorithm is randomized and on n-vertex graphs has amortized update time of Δ^o(1) log(n) per update with high probability, even against an adaptive adversary. A key to the analysis of our algorithm is an application of the entropy compression method that to our knowledge is new in the context of dynamic algorithms. This technique appears general and is likely to find other applications in dynamic problems and thus can be of its own independent interest.

Vizing’s theorem states that any \(n\)-vertex \(m\)-edge graph of maximum degree \(\Delta\) can be edge colored using at most \(\Delta + 1\) different colors. Vizing’s original proof is easily translated into a deterministic \(O(mn)\) time algorithm. This deterministic time bound was subsequently improved to \(\tilde{O}(m\sqrt{n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].

In the semi-streaming model, an algorithm must process any \(n\)-vertex graph by making one or few passes over a stream of its edges, use \(\tilde{O}(n) := O(n \cdot \mathrm{polylog}(n))\) words of space, and at the end of the last pass, output a solution to the problem at hand. Approximating (single-source) shortest paths on undirected graphs is a longstanding open question in this model. In this work, we make progress on this question from both upper and lower bound fronts: 1) We present a simple randomized algorithm that for any \(\varepsilon \gt 0\), with high probability computes \((1+\varepsilon)\)-approximate shortest paths from a given source vertex in \(O\left( \frac{1}{\varepsilon} \cdot n \log^3 n \right)\) space and \(O\left( \frac{1}{\varepsilon} \cdot \left(\frac{\log n}{\log\log n}\right)^{2} \right)\) passes. The algorithm can also be derandomized and made to work on dynamic streams at a cost of some extra \(\mathrm{poly}(\log n,1/\varepsilon)\) factors only in the space. Previously, the best known algorithms for this problem required \(1/\varepsilon \cdot \log^{c}n\) passes, for an unspecified large constant \(c\). 2) We prove that any semi-streaming algorithm that with large constant probability outputs any constant approximation to shortest paths from a given source vertex (even to a single fixed target vertex and only the distance, not necessarily the path) requires \(\Omega\left( \frac{\log n}{\log\log n} \right)\) passes. We emphasize that our lower bound holds for any constant-factor approximation of shortest paths. Previously, only constant-pass lower bounds were known and only for small approximation ratios below two. Our results collectively reduce the gap in the pass complexity of approximating single-source shortest paths in the semi-streaming model from \(\mathrm{polylog}(n)\) vs. \(\omega(1)\) to only a quadratic gap.

We study graph coloring problems in the streaming model, wherein the goal is to process an \(n\)-vertex graph whose edges arrive in a stream, using a limited space that is much smaller than the trivial \(O(n^2)\) bound. While prior work has largely focused on coloring graphs with a large number of colors—typically as a function of the maximum degree—we explore the opposite end of the spectrum: deciding whether the input graph can be colored using only a few, say, a constant number of colors. We are interested in each of the adversarial, random order, or dynamic streams, and—as is the standard in this model—focus solely on the space complexity rather than running time. Our work lays the foundation for this new direction by establishing both upper and lower bounds on space complexity of key variants of the problem.

In the semi-streaming model, we have an $n$-vertex graph $G=(V,E)$ whose edges arrive in an arbitrary order in a stream. The goal is to make one or a few passes over the stream, use a limited memory of $\tilde O(n)$ bits, and output a solution to the problem at hand at the end. A central open question in this area is to determine the best approximation ratio possible for the maximum matching problem via single-pass semi-streaming algorithms. This problem admits a simple $0.5$-approximation algorithm, by maintaining a maximal matching greedily, which, despite extensive efforts, has remained the state of the art. Lower bounds for this problem have also been few and far between with best known bounds ruling out better than $1/(1+\ln{(2)}) \sim 0.590$ approximation, using a highly complicated construction motivated by the literature on RS graphs from extremal graph theory. We develop a new framework for proving lower bounds for the semi-streaming matching problem. Our framework abstracts out the extremal graph theory and information theoretic arguments in the lower bounds, and reduces the problem to constructing certain constant-size graphs, which we call blueprints. Not only existing lower bounds can be captured by these blueprints, leading to far simpler and more concise arguments, but also we can design new blueprints that can be used to rule out $(8-2\sqrt{10})/3 \sim 0.558$-approximation for the semi-streaming matching problem. We believe this approach can be of its own independent interest and lead to further improvements on this tantalizing open question.

In the streaming set cover problem, m sets from a universe of size n are arriving one by one in a stream, and the algorithm is allowed to process the stream using one or a few passes and a space of o(mn), which is sublinear in the input size. The goal is to determine the minimal (or approximately minimal) number of sets that cover the universe at the end of the last pass.

Vizing’s theorem states that any n -vertex m -edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to \(\tilde{O}(m\sqrt {n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. 1 Very recently, independently and concurrently, using randomization, this runtime bound was further improved to \(\tilde{O}(n^2)\) by [Assadi, 2024] and \(\tilde{O}(mn^{1/3})\) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to \(\tilde{O}(mn^{1/4})\) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this article, we present a randomized algorithm that computes a Δ + 1-edge coloring in near-linear time—in fact, only O(m log Δ) time—with high probability, giving a near-optimal algorithm for this fundamental problem .

In the distributed triangle detection problem, we have an n-vertex network G = (V, E) with one player for each vertex of the graph who sees the edges incident on the vertex. The players communicate in synchronous rounds using the edges of this network and have a limited bandwidth of O(log n) bits over each edge. The goal is to detect whether or not G contains a triangle as a subgraph in a minimal number of rounds.We prove that any protocol (deterministic or randomized) for distributed triangle detection requires Ω(log log n) rounds of communication. Prior to our work, only one-round lower bounds were known for this problem.The primary technique for proving these types of distributed lower bounds is via reductions from two-party communication complexity. However, it has been known for a while that this approach is provably incapable of establishing any meaningful lower bounds for distributed triangle detection. Our main technical contribution is a new information theoretic argument which combines recent advances on multi-pass graph streaming lower bounds with the point-to-point communication aspects of distributed models, and can be of independent interest.

Vizing’s celebrated theorem states that every simple graph with maximum degree Δ admits a (Δ +1) edge coloring which can be found in O (m · n) time on n-vertex m-edge graphs. This is just one color more than the trivial lower bound of Δ colors needed in any proper edge coloring. After a series of simplifications and variations, this running time was eventually improved by Arjomandi in 1982 and independently by Gabow, Nishizeki, Kariv, Leven, and Terada in 1985 to time. This has effectively remained the state- of-the-art modulo an -factor improvement by Sinnamon in 2019.

A semi-streaming algorithm in dynamic graph streams processes any n-vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph and using O (n · polylog(n )) space. Semi-streaming algorithms for dynamic streams were first obtained in the seminal work of Ahn, Guha, and McGregor in 2012, alongside the introduction of the graph sketching technique, which remains the de facto way of designing algorithms in this model and a highly popular technique for designing graph algorithms in general.

In the load-balancing problem, we have an n-vertex bipartite graph G = (L, R, E ) between a set of clients and servers. The goal is to find an assignment of all clients to the servers, while minimizing the maximum load on each server, where load of a server is the number of clients assigned to it. Motivated by understanding the streaming complexity of this problem, we study load-balancing in the one-way (two-party) communication model: the edges of the input graph are partitioned between Alice and Bob, and Alice needs to send a short message to Bob for him to output a solution of the entire graph.

In a very recent breakthrough, Behnezhad and Ghafari [FOCS’24] developed a novel fully dynamic randomized algorithm for maintaining a (1 — ε )-approximation of maximum matching with amortized update time potentially much better than the trivial O (n ) update time. The runtime of the BG algorithm is parameterized via the following graph theoretical concept:

Vizing’s theorem states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m√n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n2) by [Assadi, 2024] and Õ(mn1/3) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn1/4) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time—in fact, only O(mlogΔ) time—with high probability, giving a near-optimal algorithm for this fundamental problem.

Peer Reviewed

We study subgraph counting over fully dynamic graphs, which undergo edge insertions and deletions. Counting subgraphs is a fundamental problem in graph theory with numerous applications across various fields, including database theory, social network analysis, and computational biology. In database theory, we can use dynamic subgraph counting algorithms on layered graphs to maintain the sizes of joins of databases that undergo updates. Specifically, the problem of finding the number of elements in a cyclic join of size k is equivalent to counting the number of k-cycles in k-layered graphs. For example, let R, S, and T be relations that have schemas (A, B), (B, C), and (C, A) respectively. Then the size of the join of R with S with T is given by the number of triangles in the corresponding layered graph where there is a layer for each attribute, the vertices are the attribute values and the edges represent the tuples of attribute values in the relations. Maintaining the number of triangles in fully dynamic graphs is very well studied and has an upper bound of O(√m) for the update time [KNN+20]. There is also a conditional lower bound of Ω(m 1/2-γ ) for any constant γ>0, for the update time [HKNS15] under the Online Matrix-Vector (OMv) conjecture implying that O(√m) is the ''right answer' for the update time of counting triangles. More recently, [HHH22] studied the problem of maintaining the number of 4-cycles in fully dynamic graphs and designed an algorithm with O(m 2/3 ) update time which is a natural generalization of the approach for counting triangles. They also studied the problem of counting 4-cliques showing that the folklore upper bound of O(m) for the update time is tight under the static combinatorial 4-clique conjecture by giving a lower bound of Ω(m 1-γ ) for any γ>0. Thus, it seems natural that O(m 2/3 ) might be the correct answer for the complexity of the update time for counting 4-cycles. In this work, we present an improved algorithm for maintaining the number of 4-cycles in fully dynamic graphs. Our algorithm achieves a worst-case update time of O(m 2/3-ε ) for some constant ε>0. We also show that the problem of counting 4-cycles is equivalent in layered graphs and general graphs. Our approach crucially uses fast matrix multiplication and leverages recent developments therein to get an improved runtime. Using the current best value of the matrix multiplication exponent ω=2.371339 we get ε=0.009811 and if we assume the best possible exponent i.e. ω=2 then we get ε=1/24. There is also a lower bound of Ω(m 1/2-γ ) for any constant γ>0, for the update time [HKNS15,HHH22], so there is still a big gap between the best-known upper and lower bounds. The key message of our paper is demonstrating that O(m 2/3 ) is not the correct answer for the complexity of the update time.

Abstract. We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are [Formula: see text] players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex; this way, each edge is known by both its endpoints and is thus shared by two players. The players communicate in simultaneous rounds by posting their messages on a shared blackboard visible to all players, with the goal of computing an MIS of the graph. While the MIS problem is well studied in other distributed models and while shared blackboard is, perhaps, the simplest broadcast model, lower bounds for our problem were only known against one-round protocols. We present a lower bound on the round-communication tradeoff for computing an MIS in this model. Specifically, we show that, when [Formula: see text] rounds of interaction are allowed, at least one player needs to communicate [Formula: see text] bits. In particular, with logarithmic bandwidth, finding an MIS requires [Formula: see text] rounds. This lower bound can be compared with the algorithm of Ghaffari et al. [ Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018, pp. 129–138] that solves the MIS in [Formula: see text] rounds but with a logarithmic bandwidth for an average player. Additionally, our lower bound further extends to the closely related problem of maximal bipartite matching. The presence of edge-sharing gives the algorithms in our model a surprising power, and numerous algorithmic results exploiting this power are known. For a similar reason, proving lower bounds in this model is much more challenging because this sharing in the players’ inputs prohibits the use of standard number-in-hand communication complexity arguments. Thus, to prove our results, we devise a new round elimination framework, which we call partial-input embedding, that may also be useful in future work for proving round-sensitive lower bounds in the presence of shared inputs. Finally, we discuss several implications of our results to multiround (adaptive) distributed sketching algorithms, broadcast congested clique, and the welfare maximization problem in two-sided matching markets.

Abstract. A longstanding open problem in algorithmic mechanism design is to design truthful mechanisms that are computationally efficient and (approximately) maximize welfare in combinatorial auctions with submodular bidders. The first such mechanism was obtained by Dobzinski, Nisan, and Schapira [Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, ACM, New York, 2005, pp. 610–618] who gave an [Formula: see text]-approximation, where [Formula: see text] is the number of items. This problem has been studied extensively since, culminating in an [Formula: see text]-approximation mechanism by Dobzinski [Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, ACM, New York, 2016, pp. 940–948]. We present a computationally-efficient truthful mechanism with an approximation ratio that improves upon the state-of-the-art by an exponential factor. In particular, our mechanism achieves an [Formula: see text]-approximation in expectation, uses only [Formula: see text] demand queries, and has universal truthfulness guarantee. This settles an open question of Dobzinski on whether [Formula: see text] is the best approximation ratio in this setting in the negative.

The monotone minimal perfect hash function (MMPHF) problem is the following indexing problem. Given a set \(S=\{s_{1},\ldots,s_{n}\}\) of \(n\) distinct keys from a universe \(U\) of size \(u\) , create a data structure \(\mathbf{D}\) that answers the following query: \(\rm{{R\small{ANK}}}(q)=\begin{cases}\text{rank of }q\text{ in }S&q\in S \\ \text{arbitrary answer}&\text{otherwise.}\end{cases}\) Solutions to the MMPHF problem are in widespread use in both theory and practice. The best upper bound known for the problem encodes \(\mathbf{D}\) in \(O(n\log\log\log u)\) bits and performs queries in \(O(\log u)\) time. It has been an open problem to either improve the space upper bound or to show that this somewhat odd looking bound is tight. In this article, we show the latter: any data structure (deterministic or randomized) for monotone minimal perfect hashing of any collection of \(n\) elements from a universe of size \(u\) requires \(\Omega(n\cdot\log\log\log{u})\) expected bits to answer every query correctly. We achieve our lower bound by defining a graph \(\mathbf{G}\) where the nodes are the possible \({u\choose n}\) inputs and where two nodes are adjacent if they cannot share the same \(\mathbf{D}\) . The size of \(\mathbf{D}\) is then lower bounded by the log of the chromatic number of \(\mathbf{G}\) . Finally, we show that the fractional chromatic number (and hence the chromatic number) of \(\mathbf{G}\) is lower bounded by \(2^{\Omega(n\log\log\log u)}\) .

The following question arises naturally in the study of graph streaming algorithms: Is there any graph problem which is "not too hard", in that it can be solved efficiently with total communication (nearly) linear in the number n of vertices, and for which, nonetheless, any streaming algorithm with Õ(n) space (i.e., a semi-streaming algorithm) needs a polynomial n^Ω(1) number of passes? Assadi, Chen, and Khanna [STOC 2019] were the first to prove that this is indeed the case. However, the lower bounds that they obtained are for rather non-standard graph problems. Our first main contribution is to present the first polynomial-pass lower bounds for natural "not too hard" graph problems studied previously in the streaming model: k-cores and degeneracy. We devise a novel communication protocol for both problems with near-linear communication, thus showing that k-cores and degeneracy are natural examples of "not too hard" problems. Indeed, previous work have developed single-pass semi-streaming algorithms for approximating these problems. In contrast, we prove that any semi-streaming algorithm for exactly solving these problems requires (almost) Ω(n^{1/3}) passes. The lower bound follows by a reduction from a generalization of the hidden pointer chasing (HPC) problem of Assadi, Chen, and Khanna, which is also the basis of their earlier semi-streaming lower bounds. Our second main contribution is improved round-communication lower bounds for the underlying communication problems at the basis of these reductions: - We improve the previous lower bound of Assadi, Chen, and Khanna for HPC to achieve optimal bounds for this problem. - We further observe that all current reductions from HPC can also work with a generalized version of this problem that we call MultiHPC, and prove an even stronger and optimal lower bound for this generalization. These two results collectively allow us to improve the resulting pass lower bounds for semi-streaming algorithms by a polynomial factor, namely, from n^{1/5} to n^{1/3} passes.

We give a near-optimal sample-pass trade-off for pure exploration in multi-armed bandits (MABs) via multi-pass streaming algorithms: any streaming algorithm with sublinear memory that uses the optimal sample complexity of $O(n/\Delta^2)$ requires $\Omega(\log{(1/\Delta)}/\log\log{(1/\Delta)})$ passes. Here, $n$ is the number of arms and $\Delta$ is the reward gap between the best and the second-best arms. Our result matches the $O(\log(1/\Delta))$ pass algorithm of Jin et al. [ICML’21] (up to lower order terms) that only uses $O(1)$ memory and answers an open question posed by Assadi and Wang [STOC’20].

In the semi-streaming model for processing massive graphs, an algorithm makes multiple passes over the edges of a given n-vertex graph and is tasked with computing the solution to a problem using O(n · log(n)) space. Semi-streaming algorithms for Maximal Independent Set (MIS) that run in O(loglogn) passes have been known for almost a decade, however, the best lower bounds can only rule out single-pass algorithms. We close this large gap by proving that the current algorithms are optimal: Any semi-streaming algorithm for finding an MIS with constant probability of success requires Ω(loglogn) passes. This settles the complexity of this fundamental problem in the semi-streaming model, and constitutes one of the first optimal multi-pass lower bounds in this model. We establish our result by proving an optimal round vs communication tradeoff for the (multi-party) communication complexity of MIS. The key ingredient of this result is a new technique, called hierarchical embedding, for performing round elimination: we show how to pack many but small hard (r−1)-round instances of the problem into a single r-round instance, in a way that enforces any r-round protocol to effectively solve all these (r−1)-round instances also. These embeddings are obtained via a novel application of results from extremal graph theory—in particular dense graphs with many disjoint unique shortest paths—together with a newly designed graph product, and are analyzed via information-theoretic tools such as direct-sum and message compression arguments.

The seminal work of Ahn, Guha, and McGregor in 2012 introduced the graph sketching technique and used it to present the first streaming algorithms for various graph problems over dynamic streams with both insertions and deletions of edges. This includes algorithms for cut sparsification, spanners, matchings, and minimum spanning trees (MSTs). These results have since been improved or generalized in various directions, leading to a vastly rich host of efficient algorithms for processing dynamic graph streams.

Structural balance theory studies stability in networks. Given a $n$-vertex complete graph $G=(V,E)$ whose edges are labeled positive or negative, the graph is considered \emph{balanced} if every triangle either consists of three positive edges (three mutual ``friends''), or one positive edge and two negative edges (two ``friends'' with a common ``enemy''). From a computational perspective, structural balance turns out to be a special case of correlation clustering with the number of clusters at most two. The two main algorithmic problems of interest are: $(i)$ detecting whether a given graph is balanced, or $(ii)$ finding a partition that approximates the \emph{frustration index}, i.e., the minimum number of edge flips that turn the graph balanced. We study these problems in the streaming model where edges are given one by one and focus on \emph{memory efficiency}. We provide randomized single-pass algorithms for: $(i)$ determining whether an input graph is balanced with $O(\log{n})$ memory, and $(ii)$ finding a partition that induces a $(1 + \varepsilon)$-approximation to the frustration index with $O(n \cdot \text{polylog}(n))$ memory. We further provide several new lower bounds, complementing different aspects of our algorithms such as the need for randomization or approximation. To obtain our main results, we develop a method using pseudorandom generators (PRGs) to sample edges between independently-chosen \emph{vertices} in graph streaming. Furthermore, our algorithm that approximates the frustration index improves the running time of the state-of-the-art correlation clustering with two clusters (Giotis-Guruswami algorithm [SODA 2006]) from $n^{O(1/\varepsilon^2)}$ to $O(n^2\log^3{n}/\varepsilon^2 + n\log n \cdot (1/\varepsilon)^{O(1/\varepsilon^4)})$ time for $(1+\varepsilon)$-approximation. These results may be of independent interest.

Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applications in streaming, distributed computing, and massively parallel algorithms, among others. Graph sketching has proven to be quite successful for various problems such as connectivity, minimum spanning trees, edge or vertex connectivity, and cut or spectral sparsifiers. Yet, the problem of approximating shortest path metric of a graph, and specifically computing a spanner, is notably missing from the list of successes. This has turned the status of this fundamental problem into one of the most longstanding open questions in this area. We present a partial explanation of this lack of success by proving a strong lower bound for a large family of graph sketching algorithms that encompasses prior work on spanners and many (but importantly not also all) related cut-based problems mentioned above. Our lower bound matches the algorithmic bounds of the recent result of Filtser, Kapralov, and Nouri (SODA'21), up to lower order terms, for constructing spanners via the same graph sketching family. This establishes near-optimality of these bounds, at least restricted to this family of graph sketching techniques, and makes progress on a conjecture posed in this latter work.

We prove that any semi-streaming algorithm for $(1+\varepsilon)$ approximation of maximum bipartite matching requires \begin{equation*}\Omega\left(\frac{\log (1 / \varepsilon)}{\log (1 / \beta)}\right)\end{equation*} passes, where $\beta \in(0,1)$ is the largest parameter so that an n-vertex graph with $n^{\beta}$ edge-disjoint induced matchings of size $\Theta(n)$ exist (such graphs are referred to as Ruzsa-Szemerédi graphs). Currently, it is known that \begin{equation*}\Omega\left(\frac{1}{\log \log n}\right) \leqslant \beta \leqslant 1-\Theta\left(\frac{\log ^{*} n}{\log n}\right)\end{equation*} and closing this huge gap between upper and lower bounds has remained a notoriously difficult problem in combinatorics.Under the plausible hypothesis that $\beta=\Omega(1)$, our lower bound result provides the first pass-approximation lower bound for (small) constant approximation of matchings in the semi-streaming model, a longstanding open question in the graph streaming literature.Our techniques are based on analyzing communication protocols for compressing (hidden) permutations. Prior work in this context relied on reducing such problems to Boolean domain and analyzing them via tools like XOR Lemmas and Fourier analysis on Boolean hypercube. In contrast, our main technical contribution is a hardness amplification result for permutations through concatenation in place of prior XOR Lemmas. This result is proven by analyzing permutations directly via simple tools from group representation theory combined with detailed information-theoretic arguments, and can be of independent interest.

In the weighted load balancing problem, the input is an $n$-vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real weight. The output is an assignment that maps each client to one of its adjacent servers, and the load of a server is then the sum of the weights of the clients assigned to it. The goal is to find an assignment that is well-balanced, typically captured by (approximately) minimizing either the $\ell_\infty$- or $\ell_2$-norm of the server loads. Generalizing both of these objectives, the all-norm load balancing problem asks for an assignment that approximately minimizes all $\ell_p$-norm objectives for $p \ge 1$, including $p = \infty$, simultaneously. Our main result is a deterministic $O(\log{n})$-pass $O(1)$-approximation semi-streaming algorithm for the all-norm load balancing problem. Prior to our work, only an $O(\log{n})$-pass $O(\log{n})$-approximation algorithm for the $\ell_\infty$-norm objective was known in the semi-streaming setting. Our algorithm uses a novel application of the multiplicative weights update method to a mixed covering/packing convex program for the all-norm load balancing problem involving an infinite number of constraints.

Correlation clustering is a fundamental optimization problem at the intersection of machine learning and theoretical computer science. Motivated by applications to big data processing, recent years have witnessed a flurry of results on this problem in the streaming model. In this model, the algorithm needs to process the input $n$-vertex graph by making one or few passes over the stream of its edges and using a limited memory, much smaller than the input size. All previous work on streaming correlation clustering have focused on semi-streaming algorithms with $\Omega(n)$ memory, whereas in this work, we study streaming algorithms with much smaller memory requirement of only $\text{polylog}{(n)}$ bits. This stringent memory requirement is in the same spirit of classical streaming algorithms that instead of recovering a full solution to the problem---which can be prohibitively large with such small memory as is the case in our problem---, aimed to learn certain statistical properties of their inputs. In our case, this translates to determining the ``(correlation) clusterability'' of input graphs, or more precisely, estimating the cost of the optimal correlation clustering solution. As our main result, we present two novel algorithms that in only $\text{polylog}{(n)}$ space are able to estimate the optimal correlation clustering cost up to some constant multiplicative factor plus some extra additive error. One of the algorithms outputs a $3$-multiplicative approximation plus $o(n^2)$ additive approximation, and the other one improves the additive error further down at the cost of increasing the multiplicative factor to some large constant. We then present new lower bounds that justify this mix of both multiplicative and additive error approximation in our algorithms.

Graph coloring is a fundamental problem with wide reaching applications in various areas including ata mining and databases, e.g., in parallel query optimization. In recent years, there has been a growing interest in solving various graph coloring problems in the streaming model. The initial algorithms in this line of work are all crucially randomized, raising natural questions about how important a role randomization plays in streaming graph coloring. A couple of very recent works prove that deterministic or even adversarially robust coloring algorithms (that work on streams whose updates may depend on the algorithm's past outputs) are considerably weaker than standard randomized ones. However, there is still a significant gap between the upper and lower bounds for the number of colors needed (as a function of the maximum degree Δ) for robust coloring and multipass deterministic coloring. We contribute to this line of work by proving the following results.

Multi-item revenue-optimal mechanisms are known to be extremely complex, often offering buyers randomized lotteries of goods. In the standard buy-one model, it is known that optimal mechanisms can yield revenue infinitely higher than that of any "simple" mechanism---the ones with size polynomial in the number of items---even with just two items and a single buyer [Briest et al. 2015; Hart and Nisan 2017].

The monotone minimal perfect hash function (MMPHF) problem is the following indexing problem. Given a set S = {sı,…, sn} of n distinct keys from a universe U of size u, create a data structure D that answers the following query:

We present a new approach for finding matchings in dense graphs by building on Szemerédi’s celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n-vertex graphs:

We continue the study of the communication complexity of gap cycle counting problems. These problems have been introduced by Verbin and Yu [SODA 2011] and have found numerous applications in proving streaming lower bounds. In the noisy gap cycle counting problem (NGC), there is a small integer k ≥ 1 and an n-vertex graph consisted of vertex-disjoint union of either k-cycles or 2k-cycles, plus O(n/k) disjoint paths of length k−1 in both cases (“noise”). The edges of this graph are partitioned between Alice and Bob whose goal is to decide which case the graph belongs to with minimal communication from Alice to Bob.

The degree distribution is one of the most fundamental properties used in the analysis of massive graphs. There is a large literature on graph sampling, where the goal is to estimate properties (especially the degree distribution) of a large graph through a small, random sample. The degree distribution estimation poses a significant challenge, due to its heavy-tailed nature and the large variance in degrees. We design a new algorithm, SADDLES, for this problem, using recent mathematical techniques from the field of sublinear algorithms. The SADDLES algorithm gives provably accurate outputs for all values of the degree distribution. For the analysis, we define two fatness measures of the degree distribution, called the $h$-index and the $z$-index. We prove that SADDLES is sublinear in the graph size when these indices are large. A corollary of this result is a provably sublinear algorithm for any degree distribution bounded below by a power law. We deploy our new algorithm on a variety of real datasets and demonstrate its excellent empirical behavior. In all instances, we get extremely accurate approximations for all values in the degree distribution by observing at most $1\%$ of the vertices. This is a major improvement over the state-of-the-art sampling algorithms, which typically sample more than $10\%$ of the vertices to give comparable results. We also observe that the $h$ and $z$-indices of real graphs are large, validating our theoretical analysis.

The Hierarchical Clustering (HC) problem consists of building a hierarchy of clusters to represent a given dataset. Motivated by the modern large-scale applications, we study the problem in the streaming model, in which the memory is heavily limited and only a single or very few passes over the input are allowed. Specifically, we investigate whether a good hierarchical clustering can be obtained, or at least whether we can approximately estimate the value of the optimal hierarchy. To measure the quality of a hierarchy, we use the HC minimization objective introduced by Dasgupta [STOC’16]. Assuming that the input is an $n$-vertex weighted graph whose edges arrive in a stream, we derive the following results on space-vs-accuracy tradeoffs: – With O(n polylog n) space, we develop a single-pass algorithm, whose approximation ratio matches the currently best offline algorithm by Charikar and Chatziafratis [SODA’17]. – When the space is more limited, namely, $n^{1-o(1)}$, we prove that no algorithm can even estimate the value of the optimum hierarchical tree to within an $o(log(n)/loglog(n))$ factor, even when allowed polylog(n) passes over the input and exponential time. – In the most stringent setting of polylog{n} space, studied extensively in the literature, we rule out algorithms that can even distinguish between “highly”-vs-“poorly” clusterable graphs, namely, graphs that have an $n^{1/2-o(1)}$ factor gap between their HC objective value. – Finally, we prove that any single-pass streaming algorithm that computes an optimal HC clustering requires storing almost the entire input even if allowed exponential time. Our algorithmic results establish a general structural result that proves that cut sparsifiers of input graphs can preserve the cost of “balanced” hierarchical trees to within some constant factor, and thus can be used in place of the original (dense) graphs when solving HC. Our lower bound results involve establishing a new streaming lower bound for a novel problem “One-vs-Many-Expanders”, which can be of independent interest.

We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are n players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex – this way, each edge is known by both its endpoints and is thus shared by two players. The players communicate in simultaneous rounds by posting their messages on a shared blackboard visible to all players, with the goal of computing an MIS of the graph. While the MIS problem is well studied in other distributed models, and while shared blackboard is, perhaps, the simplest broadcast model, lower bounds for our problem were only known against one-round protocols. We present a lower bound on the round-communication tradeoff for computing an MIS in this model. Specifically, we show that when r rounds of interaction are allowed, at least one player needs to communicate $\Omega(n^{1/20^{r+1}})$ bits. In particular, with logarithmic bandwidth, finding an MIS requires $\Omega(\log\log n)$ rounds. This lower bound can be compared with the algorithm of Ghaffari, Gouleakis, Konrad, Mitrović, and Rubinfeld [PODC 2018] that solves MIS in $O(\log\log n)$ rounds but with a logarithmic bandwidth for an average player. Additionally, our lower bound further extends to the closely related problem of maximal bipartite matching. The presence of edge-sharing gives the algorithms in our model a surprising power and numerous algorithmic results exploiting this power are known. For a similar reason, proving lower bounds in this model is much more challenging, as this sharing in the players’ inputs prohibits the use of standard number-in-hand communication complexity arguments. Thus, to prove our results, we devise a new round elimination framework, which we call partial-input embedding, that may also be useful in future work for proving round-sensitive lower bounds in the presence of shared inputs. Finally, we discuss several implications of our results to multi-round (adaptive) distributed sketching algorithms, broadcast congested clique, and to the welfare maximization problem in two-sided matching markets.

Conditional lower bounds for dynamic graph problems has received a great deal of attention in recent years. While many results are now known for the fully-dynamic case and such bounds often imply worst-case bounds for the partially dynamic setting, it seems much more difficult to prove amortized bounds for incremental and decremental algorithms. In this paper we consider partially dynamic versions of three classic problems in graph theory. Based on popular conjectures we show that: -- No algorithm with amortized update time $O(n^{1-\varepsilon})$ exists for incremental or decremental maximum cardinality bipartite matching. This significantly improves on the $O(m^{1/2-\varepsilon})$ bound for sparse graphs of Henzinger et al. [STOC'15] and $O(n^{1/3-\varepsilon})$ bound of Kopelowitz, Pettie and Porat. Our linear bound also appears more natural. In addition, the result we present separates the node-addition model from the edge insertion model, as an algorithm with total update time $O(m\sqrt{n})$ exists for the former by Bosek et al. [FOCS'14]. -- No algorithm with amortized update time $O(m^{1-\varepsilon})$ exists for incremental or decremental maximum flow in directed and weighted sparse graphs. No such lower bound was known for partially dynamic maximum flow previously. Furthermore no algorithm with amortized update time $O(n^{1-\varepsilon})$ exists for directed and unweighted graphs or undirected and weighted graphs. -- No algorithm with amortized update time $O(n^{1/2 - \varepsilon})$ exists for incremental or decremental $(4/3-\varepsilon')$-approximating the diameter of an unweighted graph. We also show a slightly stronger bound if node additions are allowed. [...]

We present a new approach for solving (minimum disagreement) correlation clustering that results in sublinear algorithms with highly efficient time and space complexity for this problem. In particular, we obtain the following algorithms for $n$-vertex $(+/-)$-labeled graphs $G$: -- A sublinear-time algorithm that with high probability returns a constant approximation clustering of $G$ in $O(n\log^2{n})$ time assuming access to the adjacency list of the $(+)$-labeled edges of $G$ (this is almost quadratically faster than even reading the input once). Previously, no sublinear-time algorithm was known for this problem with any multiplicative approximation guarantee. -- A semi-streaming algorithm that with high probability returns a constant approximation clustering of $G$ in $O(n\log{n})$ space and a single pass over the edges of the graph $G$ (this memory is almost quadratically smaller than input size). Previously, no single-pass algorithm with $o(n^2)$ space was known for this problem with any approximation guarantee. The main ingredient of our approach is a novel connection to sparse-dense graph decompositions that are used extensively in the graph coloring literature. To our knowledge, this connection is the first application of these decompositions beyond graph coloring, and in particular for the correlation clustering problem, and can be of independent interest.

We present an algorithm for the maximum matching problem in dynamic (insertion-deletions) streams with asymptotically optimal space: for any n-vertex graph, our algorithm with high probability outputs an α-approximate matching in a single pass using O(n²/α³) bits of space. A long line of work on the dynamic streaming matching problem has reduced the gap between space upper and lower bounds first to n^{o(1)} factors [Assadi-Khanna-Li-Yaroslavtsev; SODA 2016] and subsequently to polylog factors [Dark-Konrad; CCC 2020]. Our upper bound now matches the Dark-Konrad lower bound up to O(1) factors, thus completing this research direction. Our approach consists of two main steps: we first (provably) identify a family of graphs, similar to the instances used in prior work to establish the lower bounds for this problem, as the only "hard" instances to focus on. These graphs include an induced subgraph which is both sparse and contains a large matching. We then design a dynamic streaming algorithm for this family of graphs which is more efficient than prior work. The key to this efficiency is a novel sketching method, which bypasses the typical loss of polylog(n)-factors in space compared to standard L₀-sampling primitives, and can be of independent interest in designing optimal algorithms for other streaming problems.

Motivated by applications to process massive datasets, we study streaming algorithms for pure exploration in Stochastic Multi-Armed Bandits (MABs). This problem was first formulated by Assadi and Wang [STOC 2020] as follows: A collection of $n$ arms with unknown rewards are arriving one by one in a stream, and the algorithm is only allowed to store a limited number of arms at any point. The goal is to find the arm with the largest reward while minimizing the number of arm pulls (sample complexity) and the maximum number of stored arms (space complexity). Assuming $\Delta_{[2]}$ is known, Assadi and Wang designed an algorithm that uses a memory of just one arm and still achieves the sample complexity of $O(n/\Delta_{[2]}^2)$ which is worst-case optimal even for non-streaming algorithms; here $\Delta_{[i]}$ is the gap between the rewards of the best and the $i$-th best arms.In this paper, we extended this line of work to stochastic MABs in the streaming model with the instance-sensitive sample complexity, i.e. the sample complexity of $O(\sum_{i=2}^{n} \frac{1}{\Delta_{[i]}^2}\log\log{(\frac{1}{\Delta_{[i]}})})$, similar in spirit to Karnin et.al. [ICML 2013] and Jamieson et.al. [COLT 2014] in the classical setting. We devise strong negative results under this setting: our results show that any streaming algorithm under a single pass has to use either asymptotically higher sample complexity than the instance-sensitive bound, or a memory of $\Omega(n)$ arms, even if the parameter $\Delta_{[2]}$ is known. In fact, the lower bound holds under much stronger assumptions, including the random order streams or the knowledge of all gap parameters $\{\Delta_{[i]}\}_{i=2}^n$. We complement our lower bounds by proposing a new algorithm that uses a memory of a single arm and achieves the instance-optimal sample complexity when all the strong assumptions hold simultaneously.Our results are developed based on a novel arm-trapping lemma. This generic complexity result shows that any algorithm to trap the index of the best arm among $o(n)$ indices (but not necessarily to find it) has to use $\Theta(n/\Delta_{[2]}^2)$ sample complexity. This result is not restricted to the streaming setting, and to the best of our knowledge, this is the first result that captures the sample-space trade-off for `trapping' arms in multi-armed bandits, and it can be of independent interest.

Program synthesis (a.k.a. programming-by-example, PBE) has been deployed in several widely-used commercial products, such as Microsoft Excel, Power BI, and Google Spreadsheet, due to its effectiveness and user-friendliness. It takes a few user-provided positive and negative examples as input and produces a program that is consistent with all the examples, which helps end-users wrangle messy texts without writing any code. In this paper, we focus on two text wrangling tasks, string filtering and transformation. Existing PBE systems for string filtering do not scale well with negative examples. This is because they first explicitly synthesize all the consistent programs and then greedily search a good one in them. However, when there are negative examples, it could take an exponential time and space to synthesize all the exponential number of consistent programs. In contrast, we propose to synthesize all the programs consistent with the positive examples first and then lazily determine whether a program is also consistent with all the negative examples on demand in the search step. For this purpose, we develop a dynamic programming algorithm to search the optimal consistent program. Many programs are never explored during dynamic programming as they are dominated by other better consistent programs. As for string transformation, existing PBE systems do not even support negative examples. Our approach naturally extends to string transformation. Experimental results show that our methods significantly outperformed the state-of-the-art string filtering and transformation approaches and achieved better scalability.

We prove a lower bound on the space complexity of two-pass semi-streaming algorithms that approximate the maximum matching problem. The lower bound is parameterized by the density of Ruzsa-Szemerédi graphs: Any two-pass semi-streaming algorithm for maximum matching has approximation ratio at most , where RS(n) denotes the maximum number of induced matchings of size Θ(n) in any n-vertex graph, i.e., the largest density of a Ruzsa-Szemerédi graph. Currently, it is known that and closing this (large) gap between upper and lower bounds has remained a notoriously difficult problem in combinatorics. Under the plausible hypothesis that RS(n) = nΩ(1), our lower bound is the first to rule out small-constant approximation two-pass semi-streaming algorithms for the maximum matching problem, making progress on a longstanding open question in the graph streaming literature.

We provide Õ(∊–1)-pass semi-streaming algorithms for computing (1–∊)-approximate maximum cardinality matchings in bipartite graphs. Our most efficient methods are deterministic and use optimal, O(n), space, improving upon the space complexity of the previous state-of-the-art Õ(∊–1)-pass algorithm of [AG18]. To obtain our results we provide semi-streaming adaptations of more general continuous optimization tools. Further, we leverage these techniques to obtain improvements for streaming variants of approximate linear programming, optimal transport, exact matching, transshipment, and shortest path problems.

Recent breakthroughs in graph streaming have led to design of semi-streaming algorithms for various graph coloring problems such as (Δ+1)-coloring, degeneracy-coloring, coloring triangle-free graphs, and others. These algorithms are all randomized in crucial ways and whether or not there is any deterministic analogue of them has remained an important open question in this line of work.

Every graph with maximum degree Δ can be colored with (Δ+1) colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model: there exists a randomized algorithm that with high probability finds a (Δ+1)-coloring of the input graph in only O(n·logn) space assuming a single pass over the edges of the graph in any arbitrary order. But, in reality, one almost never needs (Δ+1) colors to properly color a graph. Indeed, the celebrated Brooks’ theorem states that every (connected) graph beside cliques and odd cycles can be colored with Δ colors. Can we find a Δ-coloring in the semi-streaming model as well?

We provide the first separation in the approximation guarantee achievable by truthful and nontruthful algorithms for combinatorial auctions with polynomial communication. Specifically, we prove that any truthful mechanism guaranteeing a $(\nicefrac{3}{4}-\nicefrac{1}{240}+\varepsilon)$-approximation for two buyers with XOS valuations over $m$ items requires $\exp(\Omega(\varepsilon^2 \cdot m))$ communication, whereas a nontruthful algorithm by Dobzinski and Schapira [ Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2006, pp. 1064--1073] and Feige [ SIAM J. Comput., 39 (2009), pp. 122--142] is already known to achieve a $\nicefrac{3}{4}$-approximation in ${poly}(m)$ communication. We obtain our separation by proving that any simultaneous protocol (not necessarily truthful) which guarantees a $(\nicefrac{3}{4}-\nicefrac{1}{240}+\varepsilon)$-approximation requires communication $\exp(\Omega(\varepsilon^2 \cdot m))$. The taxation complexity framework of Dobzinski [ Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2016, pp. 209--218] extends this lower bound to all truthful mechanisms (including interactive truthful mechanisms).

No abstract available.

We study the robust - à la Chakrabarti, Cormode, and McGregor [STOC'08] - communication complexity of the maximum bipartite matching problem. The edges of an adversarially chosen n-vertex bipartite graph G are partitioned randomly between Alice and Bob. Alice has to send a single message to Bob, using which Bob has to output an approximate maximum matching of G. We are particularly interested in understanding the best approximation ratio possible by protocols that use a near-optimal message size of n ⋅ polylog(n). The communication complexity of bipartite matching in this setting under an adversarial partitioning is well-understood. In their beautiful paper, Goel, Kapralov, and Khanna [SODA'12] gave a rac{2} {3}-approximate protocol with O(n) communication and showed that this approximation is tight unless we allow more than a near-linear communication. The complexity of the robust version, i.e., with a random partitioning of the edges, however remains wide open. The best known protocol, implied by a very recent random-order streaming algorithm of the authors [ICALP'21], uses O(n log n) communication to obtain a (rac{2} {3} + ε₀)-approximation for a constant ε₀ ∼ 10^{-14}. The best known lower bound, on the other hand, leaves open the possibility of all the way up to even a (1-ε)-approximation using near-linear communication for constant ε > 0. In this work, we give a new protocol with a significantly better approximation. Particularly, our protocol achieves a 0.716 expected approximation using O(n) communication. This protocol is based on a new notion of distribution-dependent sparsifiers which give a natural way of sparsifying graphs sampled from a known distribution. We then show how to lift the assumption on knowing the graph’s distribution via minimax theorems. We believe this is a particularly powerful method of designing communication protocols and might find further applications.

Multi-pass streaming algorithm for Maximum Matching have been studied since more than 15 years and various algorithmic results are known today, including 2-pass streaming algorithms that break the 1/2-approximation barrier, and (1-ε)-approximation streaming algorithms that run in O(poly 1/ε) passes in bipartite graphs and in O((1/ε)^(1/ε)) or O(poly (1/ε) ⋅ log n) passes in general graphs, where n is the number of vertices of the input graph. However, proving impossibility results for such algorithms has so far been elusive, and, for example, even the existence of 2-pass small space streaming algorithms with approximation factor 0.999 has not yet been ruled out. The key building block of all multi-pass streaming algorithms for Maximum Matching is the Greedy matching algorithm. Our aim is to understand the limitations of this approach: How many passes are required if the algorithm solely relies on the invocation of the Greedy algorithm? In this paper, we initiate the study of lower bounds for restricted families of multi-pass streaming algorithms for Maximum Matching. We focus on the simple yet powerful class of algorithms that in each pass run Greedy on a vertex-induced subgraph of the input graph. In bipartite graphs, we show that 3 passes are necessary and sufficient to improve on the trivial approximation factor of 1/2: We give a lower bound of 0.6 on the approximation ratio of such algorithms, which is optimal. We further show that Ω(1/ε) passes are required for computing a (1-ε)-approximation, even in bipartite graphs. Last, the considered class of algorithms is not well-suited to general graphs: We show that Ω(n) passes are required in order to improve on the trivial approximation factor of 1/2.

We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary $n$-vertex graph $G=(V, E)$ arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use $n \cdot poly(\log n)$ space, and output a large matching of $G$. We prove that for an absolute constant $ε_0 > 0$, one can find a $(2/3 + ε_0)$-approximate maximum matching of $G$ using $O(n \log n)$ space with high probability. This breaks the natural boundary of $2/3$ for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a $(2/3 + Ω(1))$-approximation is achievable.

We present a computationally-efficient truthful mechanism for combinatorial auctions with subadditive bidders that achieves an $O((\log\!\log{m})^3)$-approximation to the maximum welfare in expectation using $O(n)$ demand queries; here $m$ and $n$ are the number of items and bidders, respectively. This breaks the longstanding logarithmic barrier for the problem dating back to the $O(\log{m}\cdot\log\!\log{m})$-approximation mechanism of Dobzinski from 2007. Along the way, we also improve and considerably simplify the state-of-the-art mechanisms for submodular bidders.

We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected or cycle-free versus being far from these properties. We develop a new lower bound technique that proves that for many problems of interest, including all the above, obtaining a (1+є)-approximation requires either nΩ(1) space or Ω(1/є) passes, even on highly restricted families of graphs such as bounded-degree planar graphs. For multiple of these problems, this bound matches those of existing algorithms and is thus (asymptotically) optimal. Our results considerably strengthen prior lower bounds even for arbitrary graphs: starting from the influential work of [Verbin, Yu; SODA 2011], there has been a plethora of lower bounds for single-pass algorithms for these problems; however, the only multi-pass lower bounds proven very recently in [Assadi, Kol, Saxena, Yu; FOCS 2020] rules out sublinear-space algorithms with exponentially smaller o(log(1/є)) passes for these problems. One key ingredient of our proofs is a simple streaming XOR Lemma, a generic hardness amplification result, that we prove: informally speaking, if a p-pass s-space streaming algorithm can only solve a decision problem with advantage δ > 0 over random guessing, then it cannot solve XOR of ℓ independent copies of the problem with advantage much better than δℓ. This result can be of independent interest and useful for other streaming lower bounds as well.

The goal of this paper is to understand the complexity of a key symmetry breaking problem, namely the (α,β)-ruling set problem in the graph streaming model. Given a graph G = (V,E), an (α, β)-ruling set is a subset I ⊆ V such that the distance between any two vertices in I is at least α and the distance between a vertex in V and the closest vertex in I is at most β. This is a fundamental problem in distributed computing where it finds applications as a useful subroutine for other problems such as maximal matching, distributed colouring, or shortest paths. Additionally, it is a generalization of MIS, which is a (2,1)-ruling set. Our main results are two algorithms for (2,2)-ruling sets: 1) In adversarial streams, where the order in which edges arrive is arbitrary, we give an algorithm with Õ(n^{4/3}) space, improving upon the best known algorithm due to Konrad et al. [DISC 2019], with space Õ(n^{3/2}). 2) In random-order streams, where the edges arrive in a random order, we give a semi-streaming algorithm, that is an algorithm that takes Õ(n) space. Finally, we present new algorithms and lower bounds for (α,β)-ruling sets for other values of α and β. Our algorithms improve and generalize the previous work of Konrad et al. [DISC 2019] for (2,β)-ruling sets, while our lower bound establishes the impossibility of obtaining any non-trivial streaming algorithm for (α,α-1)-ruling sets for all even α > 2.

We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an $\alpha$-approximate set cover (for any $\alpha=o(\sqrt{n}/\log n)$) using a single-pass streaming algorithm, we show that $\Theta(mn/\alpha)$ space is both sufficient and necessary (up to an $O(\log n)$ factor); here $m$ denotes the number of sets and $n$ denotes the size of the universe. This provides a strong negative answer to the open question posed by Har-Peled et al. [ Towards tight bounds for the streaming set cover problem, in Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS '16), pp. 371--383] regarding the possibility of having a single-pass algorithm with a small approximation factor that uses sublinear space. We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets) and establish that an additional factor of $\alpha$ savings in the space is achievable in this case and is the best possible. In other words, we show that $\Theta(mn/\alpha^2)$ space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of $\alpha$. Our algorithm, in fact, works for the more general problem of estimating the optimal value of a covering integer program. On the other hand, our lower bound holds even for set cover instances, where the sets are presented in a random order.

A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA'19] states that in every n-vertex graph G with maximum degree Δ, sampling O(log n) colors per each vertex independently from Δ+1 colors almost certainly allows for proper coloring of G from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for (Δ+1) coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we focus on palette sparsification beyond (Δ+1) coloring, in both regimes when the number of available colors is much larger than (Δ+1), and when it is much smaller. In particular, - We prove that for (1+ε) Δ coloring, sampling only O_ε(√{log n}) colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors - this shows a separation between (1+ε) Δ and (Δ+1) coloring in the context of palette sparsification. - A natural family of graphs with chromatic number much smaller than (Δ+1) are triangle-free graphs which are O(Δ/ln Δ) colorable. We prove a palette sparsification theorem tailored to these graphs: Sampling O(Δ^γ + √{log n}) colors per vertex is sufficient and necessary to obtain a proper O_γ(Δ/ln Δ) coloring of triangle-free graphs. - We also consider the "local version" of graph coloring where every vertex v can only be colored from a list of colors with size proportional to the degree deg(v) of v. We show that sampling O_ε(log n) colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of (1+ε) ⋅ deg(v) arbitrary colors, or even only deg(v)+1 colors when the lists are the sets {1,…,deg(v)+1}. Our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms.

Consider the following gap cycle counting problem in the streaming model: The edges of a 2-regular n-vertex graph G are arriving one-by-one in a stream and we are promised that G is a disjoint union of either k-cycles or 2k-cycles for some small k; the goal is to distinguish between these two cases using a limited memory. Verbin and Yu [SODA 2011] introduced this problem and showed that any single-pass streaming algorithm solving it requires n1-Ω(1/k)space. This result and the proof technique behind it-the Boolean Hidden Hypermatching communication problem-has since been used extensively for proving streaming lower bounds for various problems, including approximating MAX-CUT, matching size, property testing, matrix rank and Schatten norms, streaming unique games and CSPs, and many others. Despite its significance and broad range of applications, the lower bound technique of Verbin and Yu comes with a key weakness that is also inherited by all subsequent results: the Boolean Hidden Hypermatching problem is hard only if there is exactly one round of communication and, in fact, can be solved with logarithmic communication in two rounds. Therefore, all streaming lower bounds derived from this problem only hold for single-pass algorithms. Our goal in this paper is to remedy this state-of-affairs. We prove the first multi-pass lower bound for the gap cycle counting problem: Any p-pass streaming algorithm that can distinguish between disjoint union of k-cycles vs 2k-cycles-or even k-cycles vs one Hamiltonian cycle-requires n1-1/kΩ(1/p)space. This makes progress on multiple open questions in this line of research dating back to the work of Verbin and Yu. As a corollary of this result and by simple (or even no) modification of prior reductions, we can extend many of previous lower bounds to multi-pass algorithms. For instance, we can now prove that any streaming algorithm that ( 1+ε) -approximates the value of MAX-CUT, maximum matching size, or rank of an n-by- n matrix, requires either nΩ(1)space or Ω(log(1/ε)) passes. For all these problems, prior work left open the possibility of even an O(logn) space algorithm in only two passes.

We prove that any two-pass graph streaming algorithm for the s-t reachability problem in n-vertex directed graphs requires near-quadratic space of n2-o(1)bits. As a corollary, we also obtain near-quadratic space lower bounds for several other fundamental problems including maximum bipartite matching and (approximate) shortest path in undirected graphs. Our results collectively imply that a wide range of graph problems admit essentially no non-trivial streaming algorithm even when two passes over the input is allowed. Prior to our work, such impossibility results were only known for single-pass streaming algorithms, and the best two-pass lower bounds only ruled out o(n7/6) space algorithms, leaving open a large gap between (trivial) upper bounds and lower bounds.

Consider the following distributed graph sketching model: There is a referee and n vertices in an undirected graph G sharing public randomness. Each vertex v only knows its neighborhood in G and the referee receives no input initially. The vertices simultaneously each sends a message, called a sketch, to the referee who then based on the received sketches outputs a solution to some combinatorial problem on G, say, the minimum spanning tree problem.

We prove the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful auction guaranteeing a (34−1240+є)-approximation for two buyers with XOS valuations over m items requires exp(Ω(ε2 · m)) communication whereas a non-truthful auction by Feige [J. Comput. 2009] is already known to achieve a 34-approximation in (m) communication.

Consider the following abstract coin tossing problem: Given a set of n coins with unknown biases, find the most biased coin using a minimal number of coin tosses. This is a common abstraction of various exploration problems in theoretical computer science and machine learning and has been studied extensively over the years. In particular, algorithms with optimal sample complexity (number of coin tosses) have been known for this problem for quite some time.

In the load balancing problem, the input is an $n$-vertex bipartite graph $G = (C \cup S, E)$ and a positive weight for each client $c \in C$. The algorithm must assign each client $c \in C$ to an adjacent server $s \in S$. The load of a server is then the weighted sum of all the clients assigned to it, and the goal is to compute an assignment that minimizes some function of the server loads, typically either the maximum server load (i.e., the $\ell_{\infty}$-norm) or the $\ell_p$-norm of the server loads. We study load balancing in the distributed setting. There are two existing results in the CONGEST model. Czygrinow et al. [DISC 2012] showed a 2-approximation for unweighted clients with round-complexity $O(Δ^5)$, where $Δ$ is the maximum degree of the input graph. Halldórsson et al. [SPAA 2015] showed an $O(\log{n}/\log\log{n})$-approximation for unweighted clients and $O(\log^2\!{n}/\log\log{n})$-approximation for weighted clients with round-complexity polylog$(n)$. In this paper, we show the first distributed algorithms to compute an $O(1)$-approximation to the load balancing problem in polylog$(n)$ rounds. In the CONGEST model, we give an $O(1)$-approximation algorithm in polylog$(n)$ rounds for unweighted clients. For weighted clients, the approximation ratio is $O(\log{n})$. In the less constrained LOCAL model, we give an $O(1)$-approximation algorithm for weighted clients in polylog$(n)$ rounds. Our approach also has implications for the standard sequential setting in which we obtain the first $O(1)$-approximation for this problem that runs in near-linear time. A 2-approximation is already known, but it requires solving a linear program and is hence much slower. Finally, we note that all of our results simultaneously approximate all $\ell_p$-norms, including the $\ell_{\infty}$-norm.

A longstanding open problem in Algorithmic Mechanism Design is to design computationally-efficient truthful mechanisms for (approximately) maximizing welfare in combinatorial auctions with submodular bidders. The first such mechanism was obtained by Dobzinski, Nisan, and Schapira [STOC'06] who gave an O(log2m)-approximation where m is number of items. This problem has been studied extensively since, culminating in an O(√log m)-approximation mechanism by Dobzinski [STOC'16]. We present a computationally-efficient truthful mechanism with approximation ratio that improves upon the state-of-the-art by an exponential factor. In particular, our mechanism achieves an O((log log m)3)-approximation in expectation, uses only O(n) demand queries, and has universal truthfulness whether Θ(√log m) is the best approximation ratio in this guarantee. This settles an open question of Dobzinski on setting in negative.

Maximal independent set (MIS), maximal matching (MM), and (Delta+1)-(vertex) coloring in graphs of maximum degree Delta are among the most prominent algorithmic graph theory problems. They are all solvable by a simple linear-time greedy algorithm and up until very recently this constituted the state-of-the-art. In SODA 2019, Assadi, Chen, and Khanna gave a randomized algorithm for (Delta+1)-coloring that runs in O~(n sqrt{n}) time, which even for moderately dense graphs is sublinear in the input size. The work of Assadi et al. however contained a spoiler for MIS and MM: neither problems provably admits a sublinear-time algorithm in general graphs. In this work, we dig deeper into the possibility of achieving sublinear-time algorithms for MIS and MM. The neighborhood independence number of a graph G, denoted by beta(G), is the size of the largest independent set in the neighborhood of any vertex. We identify beta(G) as the "right" parameter to measure the runtime of MIS and MM algorithms: Although graphs of bounded neighborhood independence may be very dense (clique is one example), we prove that carefully chosen variants of greedy algorithms for MIS and MM run in O(n beta(G)) and O(n log{n} * beta(G)) time respectively on any n-vertex graph G. We complement this positive result by observing that a simple extension of the lower bound of Assadi et al. implies that Omega(n beta(G)) time is also necessary for any algorithm to either problem for all values of beta(G) from 1 to Theta(n). We note that our algorithm for MIS is deterministic while for MM we use randomization which we prove is unavoidable: any deterministic algorithm for MM requires Omega(n^2) time even for beta(G) = 2. Graphs with bounded neighborhood independence, already for constant beta = beta(G), constitute a rich family of possibly dense graphs, including line graphs, proper interval graphs, unit-disk graphs, claw-free graphs, and graphs of bounded growth. Our results suggest that even though MIS and MM do not admit sublinear-time algorithms in general graphs, one can still solve both problems in sublinear time for a wide range of beta(G) << n. Finally, by observing that the lower bound of Omega(n sqrt{n}) time for (Delta+1)-coloring due to Assadi et al. applies to graphs of (small) constant neighborhood independence, we unveil an intriguing separation between the time complexity of MIS and MM, and that of (Delta+1)-coloring: while the time complexity of MIS and MM is strictly higher than that of (Delta+1) coloring in general graphs, the exact opposite relation holds for graphs with small neighborhood independence.

Maximum weight matching is one of the most fundamental combinatorial optimization problems with a wide range of applications in data mining and bioinformatics. Developing distributed weighted matching algorithms has been challenging due to the sequential nature of efficient algorithms for this problem. In this paper, we develop a simple distributed algorithm for the problem on general graphs with approximation guarantee of 2 + eps that (nearly) matches that of the sequential greedy algorithm. A key advantage of this algorithm is that it can be easily implemented in only two rounds of computation in modern parallel computation frameworks such as MapReduce. We also demonstrate the efficiency of our algorithm in practice on various graphs (some with half a trillion edges) by achieving objective values always close to what is achievable in the centralized setting.

In the subgraph counting problem, we are given a input graph $G(V, E)$ and a target graph $H$; the goal is to estimate the number of occurrences of $H$ in $G$. Our focus here is on designing sublinear-time algorithms for approximately counting occurrences of $H$ in $G$ in the setting where the algorithm is given query access to $G$. This problem has been studied in several recent papers which primarily focused on specific families of graphs $H$ such as triangles, cliques, and stars. However, not much is known about approximate counting of arbitrary graphs $H$. This is in sharp contrast to the closely related subgraph enumeration problem that has received significant attention in the database community as the database join problem. The AGM bound shows that the maximum number of occurrences of any arbitrary subgraph $H$ in a graph $G$ with $m$ edges is $O(m^{ρ(H)})$, where $ρ(H)$ is the fractional edge-cover of $H$, and enumeration algorithms with matching runtime are known for any $H$. We bridge this gap between subgraph counting and subgraph enumeration by designing a sublinear-time algorithm that can estimate the number of any arbitrary subgraph $H$ in $G$, denoted by $\#H$, to within a $(1\pm ε)$-approximation w.h.p. in $O(\frac{m^{ρ(H)}}{\#H}) \cdot poly(\log{n},1/ε)$ time. Our algorithm is allowed the standard set of queries for general graphs, namely degree queries, pair queries and neighbor queries, plus an additional edge-sample query that returns an edge chosen uniformly at random. The performance of our algorithm matches those of Eden et.al. [FOCS 2015, STOC 2018] for counting triangles and cliques and extend them to all choices of subgraph $H$ under the additional assumption of edge-sample queries. We further show that our algorithm works for the more general database join size estimation problem and prove a matching lower bound for this problem.

We study a secretary problem which captures the task of ranking in online settings. We term this problem the secretary ranking problem: elements from an ordered set arrive in random order and instead of picking the maximum element, the algorithm is asked to assign a rank, or position, to each of the elements. The rank assigned is irrevocable and is given knowing only the pairwise comparisons with elements previously arrived. The goal is to minimize the distance of the rank produced to the true rank of the elements measured by the Kendall-Tau distance, which corresponds to the number of pairs that are inverted with respect to the true order. Our main result is a matching upper and lower bound for the secretary ranking problem. We present an algorithm that ranks n elements with only O(n^{3/2}) inversions in expectation, and show that any algorithm necessarily suffers \Omega(n^{3/2}) inversions when there are n available positions. In terms of techniques, the analysis of our algorithm draws connections to linear probing in the hashing literature, while our lower bound result relies on a general anti-concentration bound for a generic balls and bins sampling process. We also consider the case where the number of positions m can be larger than the number of secretaries n and provide an improved bound by showing a connection of this problem with random binary trees.

Massively parallel computation (MPC) algorithms for graph problems have witnessed a resurgence of interest in recent years. Despite major progress for numerous graph problems however, the complexity of the sparse graph connectivity problem in this model has remained elusive: While classical logarithmic-round PRAM algorithms for finding connected components in any n-vertex graph have been known for more than three decades (and imply the same bounds for MPC model), no o(log n)-round MPC algorithms are known for this task with truly sublinear in n memory per machine (which is the only interesting regime for sparse graphs with O(n) edges). It is conjectured that an o(log n)-round algorithm for connectivity on general sparse graphs with n1-Ω (1) per-machine memory may not exist, a conjecture that also forms the basis for multiple conditional hardness results on the round complexity of other problems in the MPC model.

We study linear programming and general LP-type problems in several big data (streaming and distributed) models. We mainly focus on low dimensional problems in which the number of constraints is much larger than the number of variables. Low dimensional LP-type problems appear frequently in various machine learning tasks such as robust regression, support vector machines, and core vector machines. As supporting large-scale machine learning queries in database systems has become an important direction for database research, obtaining efficient algorithms for low dimensional LP-type problems on massive datasets is of great value. In this paper we give both upper and lower bounds for LP-type problems in distributed and streaming models. Our bounds are almost tight when the dimensionality of the problem is a fixed constant.

In the submodular cover problem, we are given a non-negative monotone submodular function f over a ground set E of items, and the goal is to choose a smallest subset S ⊆ E such that f(S) = Q where Q = f(E). In the stochastic version of the problem, we are given m stochastic items which are different random variables that independently realize to some item in E, and the goal is to find a smallest set of stochastic items whose realization R satisfies f(R) = Q. The problem captures as a special case the stochastic set cover problem and more generally, stochastic covering integer programs. A fully adaptive algorithm for stochastic submodular cover chooses an item to realize and based on its realization, decides which item to realize next. A non-adaptive algorithm on the other hand needs to choose a permutation of items beforehand and realize them one by one in the order specified by this permutation until the function value reaches Q. The cost of the algorithm in both case is the number (or costs) of items realized by the algorithm. It is not difficult to show that even for the coverage function there exist instances where the expected cost of a fully adaptive algorithm and a non-adaptive algorithm are separated by Ω(Q). This strong separation, often referred to as the adaptivity gap, is in sharp contrast to the separations observed in the framework of stochastic packing problems where the performance gap for many natural problem is close to the poly-time approximability of the non-stochastic version of the problem. Motivated by this striking gap between the power of adaptive and non-adaptive algorithms, we consider the following question in this work: does one need full power of adaptivity to obtain a near-optimal solution to stochastic submodular cover? In particular, how does the performance guarantees change when an algorithm interpolates between these two extremes using a few rounds of adaptivity. Towards this end, we define an r-round adaptive algorithm to be an algorithm that chooses a permutation of all available items in each round k ∊ [r], and a threshold τk, and realizes items in the order specified by the permutation until the function value is at least τk. The permutation for each round k is chosen adaptively based on the realization in the previous rounds, but the ordering inside each round remains fixed regardless of the realizations seen inside the round. Our main result is that for any integer r, there exists a poly-time r-round adaptive algorithm for stochastic submodular cover whose expected cost is Õ(Q1/r) times the expected cost of a fully adaptive algorithm. Prior to our work, such a result was not known even for the case of r = 1 and when f is the coverage function. On the other hand, we show that for any r, there exist instances of the stochastic submodular cover problem where no r-round adaptive algorithm can achieve better than Ω(Q1/r) approximation to the expected cost of a fully adaptive algorithm. Our lower bound result holds even for coverage function and for algorithms with unbounded computational power. Thus our work shows that logarithmic rounds of adaptivity are necessary and sufficient to obtain near-optimal solutions to the stochastic submodular cover problem, and even few rounds of adaptivity are sufficient to sharply reduce the adaptivity gap.

There is a rapidly growing need for scalable algorithms that solve classical graph problems, such as maximum matching and minimum vertex cover, on massive graphs. For massive inputs, several different computational models have been introduced, including the streaming model, the distributed communication model, and the massively parallel computation (MPC) model that is a common abstraction of MapReduce-style computation. In each model, algorithms are analyzed in terms of resources such as space used or rounds of communication needed, in addition to the more traditional approximation ratio. In this paper, we give a single unified approach that yields better approximation algorithms for matching and vertex cover in all these models. The highlights include: The first one pass, significantly-better-than-2-approximation for matching in random arrival streams that uses subquadratic space, namely a (1.5 + ε)-approximation streaming algorithm that uses Õ(n15) space for constant ε > 0. The first 2-round, better-than-2-approximation for matching in the MPC model that uses subquadratic space per machine, namely a (1.5 + ε)-approximation algorithm with memory per machine for constant ε > 0. By building on our unified approach, we further develop parallel algorithms in the MPC model that give a (1+∊)-approximation to matching and an O(1)-approximation to vertex cover in only O(log log n) MPC rounds and O(n/polylog(n)) memory per machine. These results settle multiple open questions posed by Czumaj et al. [STOC 2018]. We obtain our results by a novel combination of two previously disjoint set of techniques, namely randomized composable coresets and edge degree constrained subgraphs (EDCS). We significantly extend the power of these techniques and prove several new structural results. For example, we show that an EDCS is a sparse certificate for large matchings and small vertex covers that is quite robust to sampling and composition.

Any graph with maximum degree Δ admits a proper vertex coloring with Δ+1 colors that can be found via a simple sequential greedy algorithm in linear time and space. But can one find such a coloring via a sublinear algorithm? We answer this fundamental question in the affirmative for several canonical classes of sublinear algorithms including graph streaming, sublinear time, and massively parallel computation (MPC) algorithms. In particular, we design: A single-pass semi-streaming algorithm in dynamic streams using Õ(n) space. The only known semi-streaming algorithm prior to our work was a folklore O(log n)-pass algorithm obtained by simulating classical distributed algorithms in the streaming model. A sublinear-time algorithm in the standard query model that allows neighbor queries and pair queries using time. We further show that any algorithm that outputs a valid coloring with sufficiently large constant probability requires time. No non-trivial sublinear time algorithms were known prior to our work. A parallel algorithm in the massively parallel computation (MPC) model using Õ(n) memory per machine and O(1) MPC rounds. Our number of rounds significantly improves upon the recent O(log log Δ · log* (n))-round algorithm of Parter [ICALP 2018]. At the core of our results is a remarkably simple meta-algorithm for the (Δ + 1) coloring problem: Sample O(log n) colors for each vertex independently and uniformly at random from the Δ + 1 colors; find a proper coloring of the graph using only the sampled colors of each vertex. As our main result, we prove that the sampled set of colors with high probability contains a proper coloring of the input graph. The sublinear algorithms are then obtained by designing efficient algorithms for finding a proper coloring of the graph from the sampled colors in each model. We note that all our upper bound results for (Δ + 1) coloring are either optimal or close to best possible in each model studied. We also establish new lower bounds that rule out the possibility of achieving similar results in these models for the closely related problems of maximal independent set and maximal matching. Collectively, our results highlight a sharp contrast between the complexity of (Δ+1) coloring vs maximal independent set and maximal matching in various models of sublinear computation even though all three problems are solvable by a simple greedy algorithm in the classical setting.

The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by the authors of this paper [Assadi et al., STOC’18]. The algorithm is deterministic and its update time is O(m3/4), where m is the (dynamically changing) number of edges. Subsequently, Gupta and Khan and independently Du and Zhang [arXiv, April 2018] presented deterministic algorithms for dynamic MIS with update times of O(m2/3) and O(m2/3 ), respectively. Du and Zhang also gave a randomized algorithm with update time . Moreover, they provided some partial (conditional) hardness results hinting that the update time of m1/2–ε, and in particular n1–ε for n-vertex dense graphs, is a natural barrier for this problem for any constant ε > 0, for deterministic and randomized algorithms that satisfy a certain natural property. In this paper, we break this natural barrier and present the first fully dynamic (randomized) algorithm for maintaining an MIS with update time that is always sublinear in the number of vertices, namely, an expected amortized update. We also show that a simpler variant of our algorithm can already achieve an Õ(m1/3) expected amortized update time, which results in an improved performance over our update time algorithm for sufficiently sparse graphs, and breaks the m1/2 barrier of Du and Zhang for all values of m.

We present new lower bounds that show that a polynomial number of passes are necessary for solving some fundamental graph problems in the streaming model of computation. For instance, we show that any streaming algorithm that finds a weighted minimum s-t cut in an n-vertex undirected graph requires n2−o(1) space unless it makes nΩ(1) passes over the stream.

We study the maximum k-set coverage problem in the following distributed setting. A collection of input sets S1, …, Sm over a universe [n] is partitioned across p machines and the goal is to find k sets whose union covers the most number of elements. The computation proceeds in rounds where in each round machines communicate information to each other. Specifically, in each round, all machines simultaneously send a message to a central coordinator who then communicates back to all machines a summary to guide the computation for the next round. At the end of the last round, the coordinator outputs the answer. The main measures of efficiency in this setting are the approximation ratio of the returned solution, the communication cost of each machine, and the number of rounds of computation. Our main result is an asymptotically tight bound on the tradeoff between these three measures for the distributed maximum coverage problem. We first show that any r-round protocol for this problem either incurs a communication cost of k · mΩ(1/r) or only achieves an approximation factor of kΩ(1/r). This in particular implies that any protocol that simultaneously achieves good approximation ratio (O(1) approximation) and good communication cost (Õ(n) communication per machine), essentially requires logarithmic (in k) number of rounds. We complement our lower bound result by showing that there exist an r-round protocol that achieves an -approximation (essentially best possible) with a communication cost of k · mO(1/r) as well as an r-round protocol that achieves a kO(1/r)-approximation with only Õ(n) communication per each machine (essentially best possible). We further use our results in this distributed setting to obtain new bounds for maximum coverage in two other main models of computation for massive datasets, namely, the dynamic streaming model and the MapReduce model.

A maximal independent set (MIS) can be maintained in an evolving m-edge graph by simply recomputing it from scratch in O(m) time after each update. But can it be maintained in time sublinear in m in fully dynamic graphs?

In many learning settings, active/adaptive querying is possible, but the number of rounds of adaptivity is limited. We study the relationship between query complexity and adaptivity in identifying the $k$ most biased coins among a set of $n$ coins with unknown biases. This problem is a common abstraction of many well-studied problems, including the problem of identifying the $k$ best arms in a stochastic multi-armed bandit, and the problem of top-$k$ ranking from pairwise comparisons. An $r$-round adaptive algorithm for the $k$ most biased coins problem specifies in each round the set of coin tosses to be performed based on the observed outcomes in earlier rounds, and outputs the set of $k$ most biased coins at the end of $r$ rounds. When $r=1$, the algorithm is known as \em non-adaptive; when $r$ is unbounded, the algorithm is known as \em fully adaptive. While the power of adaptivity in reducing query complexity is well known, full adaptivity requires repeated interaction with the coin tossing (feedback generation) mechanism, and is highly sequential, since the set of coins to be tossed in each round can only be determined after we have observed the outcomes of the coin tosses from the previous round. In contrast, algorithms with only few rounds of adaptivity require fewer rounds of interaction with the feedback generation mechanism, and offer the benefits of parallelism in algorithmic decision-making. Motivated by these considerations, we consider the question of how much adaptivity is needed to realize the optimal worst case query complexity for identifying the $k$ most biased coins. Given any positive integer $r$, we derive essentially matching upper and lower bounds on the query complexity of $r$-round algorithms. We then show that $Θ(\log^*n)$ rounds are both necessary and sufficient for achieving the optimal worst case query complexity for identifying the $k$ most biased coins. In particular, our algorithm achieves the optimal query complexity in at most $\log^*n$ rounds, which implies that on any realistic input, $5$ parallel rounds of exploration suffice to achieve the optimal worst-case sample complexity. The best known algorithm prior to our work required $Θ(\log n)$ rounds to achieve the optimal worst case query complexity even for the special case of $k=1$.

We study the classic set cover problem in the streaming model: the sets that comprise the instance are revealed one by one in a stream and the goal is to solve the problem by making one or few passes over the stream while maintaining a sublinear space o(mn) in the input size; here m denotes the number of the sets and n is the universe size. Notice that in this model, we are mainly concerned with the space requirement of the algorithms and hence do not restrict their computation time.

We study the necessity of interaction for obtaining efficient allocations in combinatorial auctions with subadditive bidders. This problem was originally introduced by Dobzinski, Nisan, and Oren (STOC'14) as the following simple market scenario: m items are to be allocated among n bidders in a distributed setting where bidders valuations are private and hence communication is needed to obtain an efficient allocation. The communication happens in rounds: in each round, each bidder, simultaneously with others, broadcasts a message to all parties involved. At the end, the central planner computes an allocation solely based on the communicated messages. Dobzinski et al. showed that (at least some) interaction is necessary for obtaining any efficient allocation: no non-interactive (1-round) protocol with polynomial communication (in the number of items and bidders) can achieve approximation ratio better than Ω(m1/4), while for any r ≥ 1, there exists r-round protocols that achieve Ō(r. m1/r+1) approximation with polynomial communication; in particular, O(log m) rounds of interaction suffice to obtain an (almost) efficient allocation, i.e., a polylog(m)-approximation.

In the stochastic matching problem, we are given a general (not necessarily bipartite) graph G(V,E), where each edge in E is realized with some constant probability p > 0 and the goal is to compute a bounded-degree (bounded by a function depending only on p) subgraph H of G such that the expected maximum matching size in H is close to the expected maximum matching size in G. The algorithms in this setting are considered non-adaptive as they have to choose the subgraph H without knowing any information about the set of realized edges in G. Originally motivated by an application to kidney exchange, the stochastic matching problem and its variants have received significant attention in recent years.

We study the problem of estimating the maximum matching size in graphs whose edges are revealed in a streaming manner. We consider both insertion-only streams, which only contain edge insertions, and dynamic streams that allow both insertions and deletions of the edges, and present new upper and lower bound results for both cases. On the upper bound front, we show that an α- approximate estimate of the matching size can be computed in dynamic streams using Õ(n2/a4) space, and in insertion-only streams using Õ(n/a2)-space. These bounds respectively shave off a factor of α from the space necessary to compute an α-approximate matching (as opposed to only size), thus proving a non-trivial separation between approximate estimation and approximate computation of matchings in data streams. On the lower bound front, we prove that any α- approximation algorithm for estimating matching size in dynamic graph streams requires bits of space, even if the underlying graph is both sparse and has arboricity bounded by O (α). We further improve our lower bound to Ω(n/α2) in the case of dense graphs. These results establish the first non-trivial streaming lower bounds for super- constant approximation of matching size. Furthermore, we present the first super-linear space lower bound for computing a (1 + ∊)-approximation of matching size even in insertion-only streams. In particular, we prove that a (1 + ∊)-approximation to matching size requires RS(n) · η1–0(∊) space; here, RS(n) denotes the maximum number of edge-disjoint induced matchings of size Θ(n) in an n-vertex graph. It is a major open problem with far-reaching implications to determine the value of RS(n), and current results leave open the possibility that RS(n) may be as large as n/logn. Moreover, using the best known lower bounds for RS(n), our result already rules out any O(n · poly(log n/e))-space algorithm for (1 + ∊)- approximation of matchings. We also show how to avoid the dependency on the parameter RS(n) in proving lower bound for dynamic streams and present a near-optimal lower bound of n2–0(£) for (1 + ∊)-approximation in this model. Using a well-known connection between matching size and matrix rank, all our lower bounds also hold for the problem of estimating matrix rank. In particular our results imply a near-optimal n2–0(£) bit lower bound for (1 + ∊)- approximation of matrix ranks for dense matrices in dynamic streams, answering an open question of Li and Woodruff (STOC 2016).

A common approach for designing scalable algorithms for massive data sets is to distribute the computation across, say k, machines and process the data using limited communication between them. A particularly appealing framework here is the simultaneous communication model whereby each machine constructs a small representative summary of its own data and one obtains an approximate/exact solution from the union of the representative summaries. If the representative summaries needed for a problem are small, then this results in a communication-efficient and \emph{round-optimal} (requiring essentially no interaction between the machines) protocol. Some well-known examples of techniques for creating summaries include sampling, linear sketching, and composable coresets. These techniques have been successfully used to design communication efficient solutions for many fundamental graph problems. However, two prominent problems are notably absent from the list of successes, namely, the maximum matching problem and the minimum vertex cover problem. Indeed, it was shown recently that for both these problems, even achieving a modest approximation factor of \polylog{(n)} requires using representative summaries of size \widetilde{\Omega}(n^2) i.e. essentially no better summary exists than each machine simply sending its entire input graph.

Provisioning is a technique for avoiding repeated expensive computations in what-if analysis. Given a query, an analyst formulates $k$ hypotheticals, each retaining some of the tuples of a database instance, possibly overlapping, and she wishes to answer the query under scenarios, where a scenario is defined by a subset of the hypotheticals that are "turned on". We say that a query admits compact provisioning if given any database instance and any $k$ hypotheticals, one can create a poly-size (in $k$) sketch that can then be used to answer the query under any of the $2^{k}$ possible scenarios without accessing the original instance. In this paper, we focus on provisioning complex queries that combine relational algebra (the logical component), grouping, and statistics/analytics (the numerical component). We first show that queries that compute quantiles or linear regression (as well as simpler queries that compute count and sum/average of positive values) can be compactly provisioned to provide (multiplicative) approximate answers to an arbitrary precision. In contrast, exact provisioning for each of these statistics requires the sketch size to be exponential in $k$. We then establish that for any complex query whose logical component is a positive relational algebra query, as long as the numerical component can be compactly provisioned, the complex query itself can be compactly provisioned. On the other hand, introducing negation or recursion in the logical component again requires the sketch size to be exponential in $k$. While our positive results use algorithms that do not access the original instance after a scenario is known, we prove our lower bounds even for the case when, knowing the scenario, limited access to the instance is allowed.

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.

We study the problem of finding an approximate maximum matching in two closely related computational models, namely, the dynamic graph streaming model and the simultaneous multi-party communication model. In the dynamic graph streaming model, the input graph is revealed as a stream of edge insertions and deletions, and the goal is to design a small space algorithm to approximate the maximum matching. In the simultaneous model, the input graph is partitioned across k players, and the goal is to design a protocol where the k players simultaneously send a small-size message to a coordinator, and the coordinator computes an approximate matching. Dynamic graph streams. We resolve the space complexity of single-pass turnstile streaming algorithms for approximating matchings by showing that for any ∊ > 0, ⊝(n2–3e) space is both sufficient and necessary (up to polylogarithmic factors) to compute an n∊-approximate matching; here n denotes the number of vertices in the input graph. The simultaneous communication model. Our results for dynamic graph streams also resolve the (per-player) simultaneous communication complexity for approximating matchings in the edge partition model. For the vertex partition model, we design new randomized and deterministic protocols for k players to achieve an α-approximation. Specifically, for , we provide a randomized protocol with total communication of O(nk/α2) and a deterministic protocol with total communication of O(nk/α). Both these bounds are tight. Our work generalizes the results established by Dobzinski et al. (STOC 2014) for the special case of k = n. Finally, for the case of , we establish a new lower bound on the simultaneous communication complexity which is super-linear in n.

We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an α-approximate set cover (for α= o(√n)) via a single-pass streaming algorithm, we show that Θ(mn/α) space is both sufficient and necessary (up to an O(logn) factor); here m denotes number of the sets and n denotes size of the universe. This provides a strong negative answer to the open question posed by Indyk (2015) regarding the possibility of having a single-pass algorithm with a small approximation factor that uses sub-linear space. We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets), and establish that an additional factor of α saving in the space is achievable in this case and that this is the best possible. In other words, we show that Θ(mn/α2) space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of α. Our algorithm in fact works for the more general problem of estimating the optimal value of a covering integer program. On the other hand, our lower bound holds even for set cover instances where the sets are presented in a random order.

Compile-time optimizations play an important role in the efficient design of real-time embedded systems. Usually, compile-time optimizations are designed to reduce average-case execution time (ACET). While ACET is a main concern in high-performance computing systems, in real-time embedded systems, concerns are different and worst-case execution time (WCET) is much more important than ACET. Therefore, WCET reduction is more desirable than ACET reduction in many real-time embedded systems. In this article, we propose a compile-time optimization method aimed at reducing WCET in real-time embedded systems. In the proposed method, based on the predicated execution capability of embedded processors, program code blocks that are in the worst-case paths of the program are merged to increase instruction-level parallelism and opportunity for WCET reduction. The use of predicated execution enables merging code blocks from different worst-case paths that can be very effective in WCET reduction. The experimental results show that the proposed method can reduce WCET by up to 45% as compared to previous compile-time block formation methods. It is noteworthy that compared to previous works, while the proposed method usually achieves more WCET reduction, it has considerably less negative impact on ACET and code size.

In this paper, we introduce a new model for sublinear algorithms called dynamic sketching. In this model, the underlying data is partitioned into a large static part and a small dynamic part and the goal is to compute a summary of the static part (i.e, a sketch) such that given any update for the dynamic part, one can combine it with the sketch to compute a given function. We say that a sketch is compact if its size is bounded by a polynomial function of the length of the dynamic data, (essentially) independent of the size of the static part. A graph optimization problem P in this model is defined as follows. The input is a graph G(V,E) and a set T \subseteq V of k terminals; the edges between the terminals are the dynamic part and the other edges in G are the static part. The goal is to summarize the graph G into a compact sketch (of size poly(k)) such that given any set Q of edges between the terminals, one can answer the problem P for the graph obtained by inserting all edges in Q to G, using only the sketch. We study the fundamental problem of computing a maximum matching and prove tight bounds on the sketch size. In particular, we show that there exists a (compact) dynamic sketch of size O(k^2) for the matching problem and any such sketch has to be of size \Omega(k^2). Our sketch for matchings can be further used to derive compact dynamic sketches for other fundamental graph problems involving cuts and connectivities. Interestingly, our sketch for matchings can also be used to give an elementary construction of a cut-preserving vertex sparsifier with space O(kC^2) for k-terminal graphs, which matches the best known upper bound; here C is the total capacity of the edges incident on the terminals. Additionally, we give an improved lower bound (in terms of C) of Omega(C/log{C}) on size of cut-preserving vertex sparsifiers, and establish that progress on dynamic sketching of the s-t max-flow problem (either upper bound or lower bound) immediately leads to better bounds for size of cut-preserving vertex sparsifiers.

We investigate the problem of heterogeneous task assignment in crowdsourcing markets from the point of view of the requester, who has a collection of tasks. Workers arrive online one by one, and each declare a set of feasible tasks they can solve, and desired payment for each feasible task. The requester must decide on the fly which task (if any) to assign to the worker, while assigning workers only to feasible tasks. The goal is to maximize the number of assigned tasks with a fixed overall budget. We provide an online algorithm for this problem and prove an upper bound on the competitive ratio of this algorithm against an arbitrary (possibly worst-case) sequence of workers who want small payments relative to the requester’s total budget. We further show an almost matching lower bound on the competitive ratio of any algorithm in this setting. Finally, we propose a different algorithm that achieves an improved competitive ratio in the random permutation model, where the order of arrival of the workers is chosen uniformly at random. Apart from these strong theoretical guarantees, we carry out experiments on simulated data which demonstrates the practical applicability of our algorithms.

A classical trading experiment consists of a set of unit demand buyers and unit supply sellers with identical items. Each agent’s value or opportunity cost for the item is their private information and preferences are quasi-linear. Trade between agents employs a double oral auction (DOA) in which both buyers and sellers call out bids or offers which an auctioneer recognizes. Transactions resulting from accepted bids and offers are recorded. This continues until there are no more acceptable bids or offers. Remarkably, the experiment consistently terminates in a Walrasian price. The main result of this paper is a mechanism in the spirit of the DOA that converges to a Walrasian equilibrium in a polynomial number of steps, thus providing a theoretical basis for the above-described empirical phenomenon. It is well-known that computation of a Walrasian equilibrium for this market corresponds to solving a maximum weight bipartite matching problem. The uncoordinated but rational responses of agents thus solve in a distributed fashion a maximum weight bipartite matching problem that is encoded by their private valuations. We show, furthermore, that every Walrasian equilibrium is reachable by some sequence of responses. This is in contrast to the well known auction algorithms for this problem which only allow one side to make offers and thus essentially choose an equilibrium that maximizes the surplus for the side making offers. Our results extend to the setting where not every agent pair is allowed to trade with each other. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.