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

Revisions: 1

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 >>> TR21-159 | 15th November 2021 Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams #### Constructive Separations and Their Consequences For a complexity class$C$and language$L$, a constructive separation of$L \notin C$gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every$C$-algorithm attempting to decide$L\$. We study the questions: Which lower bounds can be made constructive? What are the consequences ... more >>>

TR22-066 | 4th May 2022
Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy

#### On sketching approximations for symmetric Boolean CSPs

A Boolean maximum constraint satisfaction problem, Max-CSP$$(f)$$, is specified by a predicate $$f:\{-1,1\}^k\to\{0,1\}$$. An $$n$$-variable instance of Max-CSP$$(f)$$ consists of a list of constraints, each of which applies $$f$$ to $$k$$ distinct literals drawn from the $$n$$ variables. For $$k=2$$, Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios ... more >>>

ISSN 1433-8092 | Imprint