All reports by Author Dmitry Paramonov:

__
TR22-174
| 23rd November 2022
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds

__
TR22-166
| 23rd November 2022
__

Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu#### Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

__
TR22-161
| 9th November 2022
__

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu#### Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut

__
TR21-160
| 15th November 2021
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Tight Bounds for General Computation in Noisy Broadcast Networks

__
TR21-027
| 24th February 2021
__

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu#### Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability

__
TR21-001
| 1st January 2021
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Computation Over the Noisy Broadcast Channel with Malicious Parties

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Much of today's communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric $f$-channels: In every round of the $f$-channel, each of its $n$ parties decides to either ... more >>>

Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu

We study boolean constraint satisfaction problems (CSPs) $\mathrm{Max}\text{-}\mathrm{CSP}^f_n$ for all predicates $f: \{ 0, 1 \} ^k \to \{ 0, 1 \}$. In these problems, given an integer $v$ and a list of constraints over $n$ boolean variables, each obtained by applying $f$ to a sequence of literals, we wish ... more >>>

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

We consider the Max-Cut problem, asking how much space is needed by a streaming algorithm in order to estimate the value of the maximum cut in a graph. This problem has been extensively studied over the last decade, and we now have a near-optimal lower bound for one-pass streaming algorithms, ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Let $\Pi$ be a protocol over the $n$-party broadcast channel, where in each round, a pre-specified party broadcasts a symbol to all other parties. We wish to design a scheme that takes such a protocol $\Pi$ as input and outputs a noise resilient protocol $\Pi'$ that simulates $\Pi$ over the ... more >>>

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

We give an almost quadratic $n^{2-o(1)}$ lower bound on the space consumption of any $o(\sqrt{\log n})$-pass streaming algorithm solving the (directed) $s$-$t$ reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

We study the $n$-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts ... more >>>