Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > STREAMING:
Reports tagged with streaming:
TR13-002 | 31st December 2012
Venkatesan Guruswami, Krzysztof Onak

#### Superlinear lower bounds for multipass graph processing

Revisions: 3

We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:

* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),

* testing if two ... more >>>

TR15-083 | 14th May 2015
Omri Weinstein, David Woodruff

We study $k$-party set disjointness in the simultaneous message-passing model, and show that even if each element $i\in[n]$ is guaranteed to either belong to all $k$ parties or to at most $O(1)$ parties in expectation (and to at most $O(\log n)$ parties with high probability), then $\Omega(n \min(\log 1/\delta, \log ... more >>> TR15-111 | 8th July 2015 Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky #### Low Distortion Embedding from Edit to Hamming Distance using Coupling Revisions: 1 The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings$x,y$lying in the Boolean hypercube. The edit distance between$x$and$y$is defined as the minimum number of character insertion, deletion, and bit flips needed for converting$x$into$y$. ... more >>> TR18-129 | 13th July 2018 Jelani Nelson, Huacheng Yu #### Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation Revisions: 1 We show optimal lower bounds for spanning forest computation in two different models: * One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of$n$vertices. The sole allowed query asks for a spanning forest, which the ... more >>> TR21-064 | 5th May 2021 Noah Singer, Madhu Sudan, Santhoshini Velusamy #### Streaming approximation resistance of every ordering CSP Revisions: 2 An ordering constraint satisfaction problem (OCSP) is given by a positive integer$k$and a constraint predicate$\Pi$mapping permutations on$\{1,\ldots,k\}$to$\{0,1\}$. Given an instance of OCSP$(\Pi)$on$n$variables and$m$constraints, the goal is to find an ordering of the$n\$ variables that maximizes the number ... more >>>

ISSN 1433-8092 | Imprint