Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > DMITRY PARAMONOV:
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

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 >>>


TR22-166 | 23rd November 2022
Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu

Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

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 >>>


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

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 >>>


TR21-160 | 15th November 2021
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Tight Bounds for General Computation in Noisy Broadcast Networks

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 >>>


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

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 >>>


TR21-001 | 1st January 2021
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Computation Over the Noisy Broadcast Channel with Malicious Parties

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 >>>




ISSN 1433-8092 | Imprint