Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR25-016 | 9th February 2025
James Cook

Another way to show $\mathrm{BPL} \subseteq \mathrm{CL}$ and $\mathrm{BPL} \subseteq \mathrm{P}$

We present a new technique for using catalytic space to simulate space-bounded randomized algorithms.
Allocate one bit on the catalytic tape for each configuration of a randomized machine.
Simulate the machine several times.
Each time it requests a random bit, use the bit from the catalytic tape corresponding to its ... more >>>


TR25-015 | 20th February 2025
Abhibhav Garg, Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Ashutosh Shankar

An exposition of recent list-size bounds of FRS Codes

In the last year, there have been some remarkable improvements in the combinatorial list-size bounds of Folded Reed Solomon codes and multiplicity codes. Starting from the work on Kopparty, Ron-Zewi, Saraf and Wootters (and subsequent simplifications due to Tamo), we have had dramatic improvements in the list-size bounds of FRS ... more >>>


TR25-014 | 18th February 2025
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh Saxena

Information Dissemination via Broadcasts in the Presence of Adversarial Noise

We initiate the study of error correcting codes over the multi-party adversarial broadcast channel. Specifically, we consider the classic information dissemination problem where $n$ parties, each holding an input bit, wish to know each other's input. For this, they communicate in rounds, where, in each round, one designated party sends ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint