Assadi, Liu, and Tarjan [SOSA'21] gave an auction algorithm that outputs a $(1-ε)$-approximation to Maximum Matching in bipartite graphs. Their algorithm computes a sequence of $O(\frac{1}{ε^2})$ maximal matchings in subgraphs of the input graph and can be implemented in the multi-pass streaming setting with $O(\frac{1}{ε^2})$ passes in a straightforward manner, which constitutes the state-of-the-art pass/approximation trade-off result in the multi-pass streaming setting. Their analysis uses tools from combinatorial auctions and, at its heart, relies on a clever potential function argument. Their proof, however, provides only limited insight into the inner workings of the algorithm. In this paper, we revisit the ALT-algorithm and present the following contributions. Simplification: The ALT-algorithm is built upon a freezing mechanism where vertices on one side of the bipartition that have already been rematched $Θ(\frac{1}ε)$ times over the course of the algorithm remain matched to their current partner forever. We show that this mechanism is in fact unnecessary, i.e., no special treatment of such vertices is needed. Alternative Analysis: We give an alternative analysis of the algorithm that is based on augmenting paths. Our analysis allows for a reinterpretation as one that follows the traditional approach of searching for and eliminating augmenting paths. Our analysis also copes with the removal of the freezing mechanism in a natural way, whereas the analysis of Assadi et al. strictly depends on its use. Hard Instance: We provide the first hard instance on which the algorithm requires $Ω(\frac{1}{ε^2})$ iterations/maximal matching computations. The instance is a simple path graph, where we exhibit a cyclic behaviour that prevents fast progress.

We consider the Unit Interval Selection problem in the one-pass random order streaming model. In this setting, an algorithm is presented with a sequence of n unit-length intervals on the line that arrive in uniform random order, one at a time, and the objective is to output (an approximation of) a largest set of disjoint intervals using space linear in the size of an optimal solution. Previous work only considered adversarially ordered streams and established that, within these space constraints, a (2/3)-approximation can be achieved in such streams, and this is best possible, in that going beyond such an approximation factor requires space Ω(n) [Emek et al., TALG'16]. In this work, we show that an improved expected approximation factor can be achieved if the input stream is in uniform random order, where the expectation is taken over the stream order. More specifically, we give a one-pass streaming algorithm with expected approximation factor 0.7401 that uses space O(|OPT|), where OPT denotes an optimal solution. We also show that random order algorithms with expected approximation factor above 8/9 require space Ω(n), and algorithms that compute a better than 2/3-approximation with probability above 2/3 also require Ω(n) space. On a technical level, we design an algorithm for the restricted domain [0, Δ), for some constant Δ, and use standard techniques to obtain an algorithm for unrestricted domains. For the restricted domain [0, Δ), we run O(Δ) recursive instances of our algorithm, with each instance targeting the situation where a specific interval of an optimal solution arrives first. We establish the interesting property of our algorithm that it performs worst when the input stream consists solely of a set of independent intervals. It then remains to analyse the algorithm on these simple instances. Our lower bound is proved via communication complexity arguments, similar in spirit to the robust communication lower bounds established by [Chakrabarti et al., Theory Comput. 2016].

In the Graph Reconstruction (GR) problem, a player initially only knows the vertex set V of an input graph G = (V, E) and is required to learn its set of edges E. To this end, the player submits queries to an oracle and must deduce E from the oracle’s answers. Angluin and Chen [Journal of Computer and System Sciences, 2008] resolved the number of Independent Set (IS) queries necessary and sufficient for GR on m-edge graphs. In this setting, each query consists of a subset of vertices U ⊆ V, and the oracle responds with a boolean, indicating whether U is an independent set in G. They gave algorithms that use O(m ⋅ log n) IS queries, which is best possible. In this paper, we initiate the study of GR via Maximal Independent Set (MIS) queries, a more powerful variant of IS queries. Given a query U ⊆ V, the oracle responds with any, potentially adversarially chosen, maximal independent set I ⊆ U in the induced subgraph G[U]. We show that, for GR, MIS queries are strictly more powerful than IS queries when parametrized by the maximum degree Δ of the input graph. We give tight (up to poly-logarithmic factors) upper and lower bounds for this problem: 1) We observe that the simple strategy of taking uniform independent random samples of V and submitting those to the oracle yields a non-adaptive randomized algorithm that executes O(Δ² ⋅ log n) queries and succeeds with high probability. This should be contrasted with the fact that Ω(Δ ⋅ n ⋅ log(n/Δ)) IS queries are required for such graphs, which shows that MIS queries are strictly more powerful than IS queries. Interestingly, combining the strategy of taking uniform random samples of V with the probabilistic method, we show the existence of a deterministic non-adaptive algorithm that executes O(Δ³ ⋅ log(n/Δ)) queries. 2) Regarding lower bounds, we prove that the additional Δ factor when going from randomized non-adaptive algorithms to deterministic non-adaptive algorithms is necessary. We show that every non-adaptive deterministic algorithm requires Ω(Δ³ / log² Δ) queries. For arbitrary randomized adaptive algorithms, we show that Ω(Δ²) queries are necessary in graphs of maximum degree Δ, and that Ω(log n) queries are necessary, even when the input graph is an n-vertex cycle.

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.

We initiate the study of the Interval Selection problem in the (streaming) sliding window model of computation. In this problem, an algorithm receives a potentially infinite stream of intervals on the line, and the objective is to maintain at every moment an approximation to a largest possible subset of disjoint intervals among the L most recent intervals, for some integer L. We give the following results: 1) In the unit-length intervals case, we give a 2-approximation sliding window algorithm with space Õ(|OPT|), and we show that any sliding window algorithm that computes a (2-ε)-approximation requires space Ω(L), for any ε > 0. 2) In the arbitrary-length case, we give a (11/3+ε)-approximation sliding window algorithm with space Õ(|OPT|), for any constant ε > 0, which constitutes our main result. We also show that space Ω(L) is needed for algorithms that compute a (2.5-ε)-approximation, for any ε > 0. Our main technical contribution is an improvement over the smooth histogram technique, which consists of running independent copies of a traditional streaming algorithm with different start times. By employing the one-pass 2-approximation streaming algorithm by Cabello and Pérez-Lantero [Theor. Comput. Sci. '17] for Interval Selection on arbitrary-length intervals as the underlying algorithm, the smooth histogram technique immediately yields a (4+ε)-approximation in this setting. Our improvement is obtained by forwarding the structure of the intervals identified in a run to the subsequent run, which constrains the shape of an optimal solution and allows us to target optimal intervals differently.

We consider the problem of estimating the size of a maximum matching in low-arboricity graphs in the dynamic graph stream model. In this setting, an algorithm with limited memory makes multiple passes over a stream of edge insertions and deletions, resulting in a low-arboricity graph. Let n be the number of vertices of the input graph, and α be its arboricity. We give the following results. 1) As our main result, we give a three-pass streaming algorithm that produces an (α + 2)(1 + ε)-approximation and uses space O(ε^{-2}⋅α²⋅n^{1/2}⋅log n). This result should be contrasted with the Ω(α^{-5/2}⋅n^{1/2}) space lower bound established by [Assadi et al., SODA'17] for one-pass algorithms, showing that, for graphs of constant arboricity, the one-pass space lower bound can be achieved in three passes (up to poly-logarithmic factors). Furthermore, we obtain a two-pass algorithm that uses space O(ε^{-2}⋅α²⋅n^{3/5}⋅log n). 2) We also give a (1+ε)-approximation multi-pass algorithm, where the space used is parameterized by an upper bound on the size of a largest matching. For example, using O(log log n) passes, the space required is O(ε^{-1}⋅α²⋅k⋅log n), where k denotes an upper bound on the size of a largest matching. Finally, we define a notion of arboricity in the context of matrices. This is a natural measure of the sparsity of a matrix that is more nuanced than simply bounding the total number of nonzero entries, but less restrictive than bounding the number of nonzero entries in each row and column. For such matrices, we exploit our results on estimating matching size to present upper bounds for the problem of rank estimation in the dynamic data stream model.

In this paper, we give the first unconditional space lower bound for two-pass streaming algorithms for Maximum Bipartite Matching approximation. We show that every randomized two-pass streaming algorithm that computes a -approximation to Maximum Bipartite Matching, for any constant ɛ > 0, requires space , where n is the number of vertices of the input graph.

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.

We study the Set Cover problem in the one-pass edge-arrival streaming model. In this model, the input stream consists of a sequence of tuples (S, u), indicating that element u is contained in set S. This setting captures the streaming Dominating Set problem and is more general and harder to solve than the Set Cover set-arrival setting, where entire sets with all their elements arrive in the stream one-by-one. We prove the following results (n is the size of the universe, m is the number of sets):

We give deterministic distributed (1+ϵ)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O(1ϵlog⁡n) rounds, and our independent set algorithm has a runtime of O(1ϵlog⁡(1ϵ)log⁎⁡n) rounds. For coloring, existing lower bounds imply that the dependencies on 1ϵ and log⁡n are best possible. For independent set, we prove that Ω(1ϵ) rounds are necessary. Both our algorithms make use of a tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O(log⁡n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O(log⁡1ϵ) layers are required as they already contain a large enough independent set. We develop a (1+ϵ)-approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. While tree decompositions have only played a minor role in distributed computing, our work demonstrates their potential for designing efficient distributed algorithms.

State-of-the-art practical algorithms for solving large Set Cover instances can all be regarded as variants of the Greedy Set Cover algorithm. These algorithms maintain the input sets in memory, which yields a substantial memory footprint. In particular, in the context of massive inputs, these sets may need to be maintained on the hard disk or on external memory, and, consequently, access to these sets is slow. In this paper, we demonstrate that simple one-pass algorithms with small memory footprints are able to compete with the more involved Greedy-like algorithms for Set Cover in practice. Our experiments show that a recent Set Cover streaming algorithm by Emek and Rosén [ACM Trans. on Alg. 2016] produces covers whose sizes are on average within 8% of those produced by state-of-the-art algorithms, while using between 10 and 73 times less memory. We also provide a theoretical analysis of an extension of the Emek-Rosén algorithm to multiple passes and demonstrate that multiple passes allow us to further reduce cover sizes in practice.

We study two-pass streaming algorithms for Maximum Bipartite Matching (MBM). All known two-pass streaming algorithms for MBM operate in a similar fashion: They compute a maximal matching in the first pass and find 3-augmenting paths in the second in order to augment the matching found in the first pass. Our aim is to explore the limitations of this approach and to determine whether current techniques can be used to further improve the state-of-the-art algorithms. We give the following results: We show that every two-pass streaming algorithm that solely computes a maximal matching in the first pass and outputs a (2/3+ε)-approximation requires n^{1+Ω(1/(log log n))} space, for every ε > 0, where n is the number of vertices of the input graph. This result is obtained by extending the Ruzsa-Szemerédi graph construction of [Goel et al., SODA'12] so as to ensure that the resulting graph has a close to perfect matching, the key property needed in our construction. This result may be of independent interest. Furthermore, we combine the two main techniques, i.e., subsampling followed by the Greedy matching algorithm [Konrad, MFCS'18] which gives a 2-√2 ≈ 0.5857-approximation, and the computation of degree-bounded semi-matchings [Esfandiari et al., ICDMW'16][Kale and Tirodkar, APPROX'17] which gives a 1/2 + 1/12 ≈ 0.5833-approximation, and obtain a meta-algorithm that yields Konrad’s and Esfandiari et al.’s algorithms as special cases. This unifies two strands of research. By optimizing parameters, we discover that Konrad’s algorithm is optimal for the implied class of algorithms and, perhaps surprisingly, that there is a second optimal algorithm. We show that the analysis of our meta-algorithm is best possible. Our results imply that further improvements, if possible, require new techniques.

Detecting frequent elements is among the oldest and most-studied problems in the area of data streams. Given a stream of m data items in \1, 2, \dots, n\, the objective is to output items that appear at least d times, for some threshold parameter d, and provably optimal algorithms are known today. However, in many applications, knowing only the frequent elements themselves is not enough: For example, an Internet router may not only need to know the most frequent destination IP addresses of forwarded packages, but also the timestamps of when these packages appeared or any other meta-data that "arrived'' with the packages, e.g., their source IP addresses. In this paper, we introduce the witness version of the frequent elements problem: Given a desired approximation guarantee α \ge 1$ and a desired frequency $d łe Δ$, where Δ is the frequency of the most frequent item, the objective is to report an item together with at least $d / α$ timestamps of when the item appeared in the stream (or any other meta-data that arrived with the items). We give provably optimal algorithms for both the insertion-only and insertion-deletion stream settings: In insertion-only streams, we show that space $\tildeO (n + d \cdot n^\frac1 α )$ is necessary and sufficient for every integral $1 łe α łe łog n$. In insertion-deletion streams, we show that space $\tildeO (\fracn \cdot d α^2 )$ is necessary and sufficient, for every α łe \sqrtn $.

In this paper, we give simple optimal lower bounds on the one-way two-party communication complexity of approximate Maximum Matching and Minimum Vertex Cover with deletions. In our model, Alice holds a set of edges and sends a single message to Bob. Bob holds a set of edge deletions, which form a subset of Alice’s edges, and needs to report a large matching or a small vertex cover in the graph spanned by the edges that are not deleted. Our results imply optimal space lower bounds for insertion-deletion streaming algorithms for Maximum Matching and Minimum Vertex Cover. Previously, Assadi et al. [SODA 2016] gave an optimal space lower bound for insertion-deletion streaming algorithms for Maximum Matching via the simultaneous model of communication. Our lower bound is simpler and stronger in several aspects: The lower bound of Assadi et al. only holds for algorithms that (1) are able to process streams that contain a triple exponential number of deletions in n, the number of vertices of the input graph; (2) are able to process multi-graphs; and (3) never output edges that do not exist in the input graph when the randomized algorithm errs. In contrast, our lower bound even holds for algorithms that (1) rely on short (O(n²)-length) input streams; (2) are only able to process simple graphs; and (3) may output non-existing edges when the algorithm errs.

Abstract The problem of detecting network structures plays a central role in distributed computing. One of the fundamental problems studied in this area is to determine whether for a given graph H, the input network contains a subgraph isomorphic to H or not. We investigate this problem for H being a clique $$K_{\ell }$$ K ℓ in the classical distributed model, where the communication topology is the same as the topology of the underlying network, and with limited communication bandwidth on the links. Our first and main result is a lower bound, showing that detecting $$K_{\ell }$$ K ℓ requires $$\varOmega (\sqrt{n} / {\mathfrak {b}})$$ Ω ( n / b ) communication rounds, for every $$4 \le \ell \le \sqrt{n}$$ 4 ≤ ℓ ≤ n , and $$\varOmega (n / (\ell {\mathfrak {b}}))$$ Ω ( n / ( ℓ b ) ) rounds for every $$\ell \ge \sqrt{n}$$ ℓ ≥ n , where $${\mathfrak {b}}$$ b is the bandwidth of the communication links. This result is obtained by using a reduction to the set disjointness problem in the framework of two-party communication complexity. We complement our lower bound with a two-party communication protocol for listing all cliques in the input graph, which up to constant factors communicates the same number of bits as our lower bound for $$K_4$$ K 4 detection. This demonstrates that our lower bound cannot be improved using the two-party communication framework.

We consider the maximal and maximum independent set problems in three models of graph streams: - In the edge model we see a stream of edges which collectively define a graph; this model is well-studied for a variety of problems. We show that the space complexity for a one-pass streaming algorithm to find a maximal independent set is quadratic (i.e. we must store all edges). We further show that it is not much easier if we only require approximate maximality. This contrasts strongly with the other two vertex-based models, where one can greedily find an exact solution in only the space needed to store the independent set. - In the "explicit" vertex model, the input stream is a sequence of vertices making up the graph. Every vertex arrives along with its incident edges that connect to previously arrived vertices. Various graph problems require substantially less space to solve in this setting than in edge-arrival streams. We show that every one-pass c-approximation streaming algorithm for maximum independent set (MIS) on explicit vertex streams requires Omega({n^2}/{c^6}) bits of space, where n is the number of vertices of the input graph. It is already known that Theta~({n^2}/{c^2}) bits of space are necessary and sufficient in the edge arrival model (Halldórsson et al. 2012), thus the MIS problem is not significantly easier to solve under the explicit vertex arrival order assumption. Our result is proved via a reduction from a new multi-party communication problem closely related to pointer jumping. - In the "implicit" vertex model, the input stream consists of a sequence of objects, one per vertex. The algorithm is equipped with a function that maps pairs of objects to the presence or absence of edges, thus defining the graph. This model captures, for example, geometric intersection graphs such as unit disc graphs. Our final set of results consists of several improved upper and lower bounds for interval and square intersection graphs, in both explicit and implicit streams. In particular, we show a gap between the hardness of the explicit and implicit vertex models for interval graphs.

We give deterministic distributed (1+epsilon)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O( (1 / epsilon) log n) rounds, and our independent set algorithm has a runtime of O( (1/epsilon) log(1/epsilon)log^* n) rounds. For coloring, existing lower bounds imply that the dependencies on 1/epsilon and log n are best possible. For independent set, we prove that Omega(1/epsilon) rounds are necessary. Both our algorithms make use of the tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O(log n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O(log (1/epsilon)) layers are required as they already contain a large enough independent set. We develop a (1+epsilon)-approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. This work raises the question as to how useful tree decompositions are for distributed computing.

The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related $β$-ruling set problem, in two computational models suited for large-scale graph processing, namely the $k$-machine model and the graph streaming model. We present a number of results. For MIS in the $k$-machine model, we improve the $\tilde{O}(m/k^2 + Δ/k)$-round upper bound of Klauck et al. (SODA 2015) by presenting an $\tilde{O}(m/k^2)$-round algorithm. We also present an $\tildeΩ(n/k^2)$ round lower bound for MIS, the first lower bound for a symmetry breaking problem in the $k$-machine model. For $β$-ruling sets, we use hierarchical sampling to obtain more efficient algorithms in the $k$-machine model and also in the graph streaming model. More specifically, we obtain a $k$-machine algorithm that runs in $\tilde{O}(βnΔ^{1/β}/k^2)$ rounds and, by using a similar hierarchical sampling technique, we obtain one-pass algorithms for both insertion-only and insertion-deletion streams that use $O(β\cdot n^{1+1/2^{β-1}})$ space. The latter result establishes a clear separation between MIS, which is known to require $Ω(n^2)$ space (Cormode et al., ICALP 2019), and $β$-ruling sets, even for $β= 2$. Finally, we present an even faster 2-ruling set algorithm in the $k$-machine model, one that runs in $\tilde{O}(n/k^{2-ε} + k^{1-ε})$ rounds for any $ε$, $0 \le ε\le 1$.

Given a graph G, it is well known that any maximal matching M in G is at least half the size of a maximum matching M^*. In this paper, we show that if G is bipartite, then running the Greedy matching algorithm on a sampled subgraph of G produces enough additional edges that can be used to augment M such that the resulting matching is of size at least (2 - sqrt{2})|M^*| ~~ 0.5857 |M^*| (ignoring lower order terms) with high probability. The main applications of our method lie in the area of data streaming algorithms, where an algorithm performs few passes over the edges of an n-vertex graph while maintaining a memory of size O(n polylog n). Our method immediately yields a very simple two-pass algorithm for Maximum Bipartite Matching (MBM) with approximation factor 0.5857, which only runs the Greedy matching algorithm in each pass. This slightly improves on the much more involved 0.583-approximation algorithm of Esfandiari et al. [ICDMW 2016]. To obtain our main result, we combine our method with a residual sparsity property of the random order Greedy algorithm and give a one-pass random order streaming algorithm for MBM with approximation factor 0.5395. This substantially improves upon the one-pass random order 0.505-approximation algorithm of Konrad et al. [APPROX 2012].

We present O(loglog n) -round algorithms in the Massively Parallel Computation (MPC) model, with Õ (n) memory per machine, that compute a maximal independent set, a 1+ε approximation of maximum matching, and a 2+εapproximation of minimum vertex cover, for any n-vertex graph and any constant \eps>0. These improve the state of the art as follows:

We give deterministic distributed (1+ε)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O( 1/ε logn) rounds, and our independent set algorithm has a runtime of O( 1 ε log( 1/ε ) log? n) rounds. For coloring, existing lower bounds imply that the dependencies on 1/ε and logn are best possible. For independent set, we prove that Ω( 1/ε ) rounds are necessary.

Independent sets play a central role in distributed algorithmics. We examine here the minimal requirements for computing non-trivial independent sets. In particular, we focus on algorithms that operate in a single communication round. A classic result of Linial shows that a constant number of rounds does not suffice to compute a maximal independent set. We are therefore interested in the size of the solution that can be computed, especially in comparison to the optimal. Our main result is a randomized one-round algorithm that achieves poly-logarithmic approximation on graphs of polynomially bounded-independence. Specifically, we show that the algorithm achieves the Caro-Wei bound (an extension of the Turán bound for independent sets) in general graphs up to a constant factor, and that the Caro-Wei bound yields a poly-logarithmic approximation on bounded-independence graphs. The algorithm uses only a single bit message and operates in a beeping model, where a node receives only the disjunction of the bits transmitted by its neighbors. We give limitation results that show that these are the minimal requirements for obtaining non-trivial solutions. In particular, a sublinear approximation cannot be obtained in a single round on general graphs, nor when nodes cannot both transmit and receive messages. We also show that our analysis of the Caro-Wei bound on polynomially bounded-independence graphs is tight, and that the poly-logarithmic approximation factor does not extend to $$\mathrm {O}(1)$$ -claw free graphs.

The densest $k$-subgraph (D$k$S) problem and its corresponding minimization problem smallest $p$-edge subgraph (S$p$ES) have come to play a central role in approximation algorithms. This is due both to their practical importance and to their usefulness as a tool for solving and establishing approximation bounds for other problems. These two problems are not well understood, and it is widely believed that they do not admit a subpolynomial approximation ratio (although the best-known hardness results do not rule this out). In this paper we generalize both D$k$S and S$p$ES from graphs to hypergraphs. We consider the densest $k$-subhypergraph (D$k$SH) problem (given a hypergraph $(V, E)$, find a subset $W\subseteq V$ of $k$ vertices so as to maximize the number of hyperedges contained in $W$), and define the minimum $p$-union (M$p$U) problem (given a hypergraph, choose $p$ of the hyperedges so as to minimize the number of vertices in their union). We focus in particular on the case where all hyperedges have size 3, as this is the simplest nongraph setting. For this case we provide an $O(n^{4(4-\sqrt{3})/13 + \epsilon}) < O(n^{0.697831+\epsilon})$-approximation (for arbitrary constant $\epsilon > 0$) for D$k$SH and an $\tilde{O}(n^{2/5})$-approximation for M$p$U. We also give an $O(\sqrt{m})$-approximation for M$p$U in general hypergraphs. Finally, we examine the interesting special case of interval hypergraphs (instances where the vertices are a subset of the natural numbers and the hyperedges are intervals of the line) and prove that both problems admit an exact polynomial-time solution on these instances.

We provide simple but surprisingly useful direct product theorems for proving lower bounds on online algorithms with a limited amount of advice about the future. As a consequence, we are able to translate decades of research on randomized online algorithms to the advice complexity model. Doing so improves significantly on the previous best advice complexity lower bounds for many online problems, or provides the first known lower bounds. For example, if $n$ is the number of requests, we show that: (1) A paging algorithm needs $Ω(n)$ bits of advice to achieve a competitive ratio better than $H_k=Ω(\log k)$, where $k$ is the cache size. Previously, it was only known that $Ω(n)$ bits of advice were necessary to achieve a constant competitive ratio smaller than $5/4$. (2) Every $O(n^{1-\varepsilon})$-competitive vertex coloring algorithm must use $Ω(n\log n)$ bits of advice. Previously, it was only known that $Ω(n\log n)$ bits of advice were necessary to be optimal. For certain online problems, including the MTS, $k$-server, paging, list update, and dynamic binary search tree problem, our results imply that randomization and sublinear advice are equally powerful (if the underlying metric space or node set is finite). This means that several long-standing open questions regarding randomized online algorithms can be equivalently stated as questions regarding online algorithms with sublinear advice. For example, we show that there exists a deterministic $O(\log k)$-competitive $k$-server algorithm with advice complexity $o(n)$ if and only if there exists a randomized $O(\log k)$-competitive $k$-server algorithm without advice. Technically, our main direct product theorem is obtained by extending an information theoretical lower bound technique due to Emek, Fraigniaud, Korman, and Rosén [ICALP'09].

We study streaming algorithms for partitioning integer sequences and trees. In the case of trees, we suppose that the input tree is provided by a stream consisting of a depth-first-traversal of the input tree. This captures the problem of partitioning XML streams, among other problems. We show that both problems admit deterministic (1+epsilon)-approximation streaming algorithms, where a single pass is sufficient for integer sequences and two passes are required for trees. The space complexity for partitioning integer sequences is O((1/epsilon) * p * log(nm)) and for partitioning trees is O((1/epsilon) * p^2 * log(nm)), where n is the length of the input stream, m is the maximal weight of an element in the stream, and p is the number of partitions to be created. Furthermore, for the problem of partitioning integer sequences, we show that computing an optimal solution in one pass requires Omega(n) space, and computing a (1+epsilon)-approximation in one pass requires Omega((1/epsilon) * log(n)) space, rendering our algorithm tight for instances with p,m in O(1).

We show that the first phase of the Linial-Saks network decomposition algorithm gives a randomized distributed O(nε)-approximation algorithm for the maximum independent set problem that operates in O(1/ε) rounds, and we give a matching lower bound that holds even for bipartite graphs.

We study the streaming complexity and communication complexity of approximating unweighted semi-matchings. A semi-matching in a bipartite graph G = ( A , B , E ) with n = | A | is a subset of edges S ⊆ E that matches all A vertices to B vertices with the goal usually being to do this as fairly as possible. While the term semi-matching was coined in 2003 by Harvey et al. [2003], the problem had already previously been studied in the scheduling literature under different names. We present a deterministic one-pass streaming algorithm that for any 0 ⩽ ϵ ⩽ 1 uses space Õ( n 1+ϵ and computes an O( n (1−ϵ)/2 )-approximation to the semi-matching problem. Furthermore, with O(log n ) passes it is possible to compute an O(log n )-approximation with space Õ( n ). In the one-way two-party communication setting, we show that for every ϵ > 0, deterministic communication protocols for computing an O( n 1/(1+ϵ) c +1) -approximation require a message of size more than cn bits. We present two deterministic protocols communicating n and 2 n edges that compute an O√ n and an O(n 1/3 )-approximation, respectively. Finally, we improve on the results of Harvey et al. [2003] and prove new links between semi-matchings and matchings. While it was known that an optimal semi-matching contains a maximum matching, we show that there is a hierarchical decomposition of an optimal semi-matching into maximum matchings. A similar result holds for semi-matchings that do not admit length-two degree-minimizing paths.

Set reconciliation is a fundamental problem in distributed databases, where two parties each holding a set of elements wish to find their difference, so as to establish data consistency. Efficient algorithms exist for this problem with communication cost proportional only to the difference of the two sets, as opposed to the cardinality of the sets themselves. However, all existing work on set reconciliation considers two elements to be the same only if they are exactly equal. We observe that, in many applications, the elements correspond to objects on which a distance function can be defined, e.g., points in the Euclidean space, and close points often actually represent the same object. During the reconciliation, the algorithm should only find the truly different elements in the two sets while tolerating small perturbations. In this paper, we propose the robust set reconciliation problem, and take a principled approach to address this issue via the earth mover's distance. We have developed a communication and time-efficient algorithm with provable guarantees on the quality of the reconciliation. This is then complemented with an essentially matching lower bound showing the optimality of the algorithm. Our experimental results on both synthetic and real data sets have demonstrated that our algorithm also performs very well in practice.

We study the problem of validating XML documents of size N against general DTDs in the context of streaming algorithms. The starting point of this work is a well-known space lower bound. There are XML documents and DTDs for which p -pass streaming algorithms require Ω( N / p ) space. We show that when allowing access to external memory, there is a deterministic streaming algorithm that solves this problem with memory space O(log 2 N ), a constant number of auxiliary read/write streams, and O(log N ) total number of passes on the XML document and auxiliary streams. An important intermediate step of this algorithm is the computation of the First-Child-Next-Sibling (FCNS) encoding of the initial XML document in a streaming fashion. We study this problem independently, and we also provide memory-efficient streaming algorithms for decoding an XML document given in its FCNS encoding. Furthermore, validating XML documents encoding binary trees against any DTD in the usual streaming model without external memory can be done with sublinear memory. There is a one-pass algorithm using O(√ N log N ) space, and a bidirectional two-pass algorithm using O(log 2 N ) space which perform this task.

We study the problem of validating XML documents of size N against general DTDs in the context of streaming algorithms. The starting point of this work is a well-known space lower bound. There are XML documents and DTDs for which p-pass streaming algorithms require Ω(N/p) space.