7 papers
Time- and Space-Efficient List Decoding up to Capacity
Dorsa Fathollahi, Noga Ron-Zewi, Mary Wootters
In the theory of error correcting codes, list-decoding refers to the following problem. Given a code and a received word , find all codewords …
On the Error Probability of RPA Decoding of Reed-Muller Codes over BMS Channels
Dorsa Fathollahi, V. Arvind Rameshwar, V. Lalitha
We analyze the performance of the Recursive Projection-Aggregation (RPA) decoder of Ye and Abbe (2020), for Reed-Muller (RM) codes, over general binary memoryless symmetric (BMS) c…
Interactive Coding with Small Memory and Improved Rate
Dorsa Fathollahi, Bernhard Haeupler, Nicolas Resch +1
In this work, we study two-party interactive coding for adversarial noise, when both parties have limited memory. We show how to convert any adaptive protocol into a protocol $…
Robust Gray Codes Approaching the Optimal Rate
Roni Con, Dorsa Fathollahi, Ryan Gabrys +2
Robust Gray codes were introduced by (Lolck and Pagh, SODA 2024). Informally, a robust Gray code is a (binary) Gray code so that, given a noisy version of the encodin…
Improved Construction of Robust Gray Code
Dorsa Fathollahi, Mary Wootters
A robust Gray code, formally introduced by (Lolck and Pagh, SODA 2024), is a Gray code that additionally has the property that, given a noisy version of the encoding of an integer…
Polar Coded Computing: The Role of the Scaling Exponent
Dorsa Fathollahi, Marco Mondelli
We consider the problem of coded distributed computing using polar codes. The average execution time of a coded computing system is related to the error probability for transmissio…
Sparse Multi-Decoder Recursive Projection Aggregation for Reed-Muller Codes
Dorsa Fathollahi, Nariman Farsad, Seyyed Ali Hashemi +1
Reed-Muller (RM) codes are one of the oldest families of codes. Recently, a recursive projection aggregation (RPA) decoder has been proposed, which achieves a performance that is c…