3 papers
cs.CR2026
Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli
Andrej Bogdanov, Kel Zin Tan, Prashant Nalini Vasudevan
The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning…
cs.CC2025
Decoding Balanced Linear Codes With Preprocessing
Andrej Bogdanov, Rohit Chatterjee, Yunqi Li +1
Prange's information set algorithm is a decoding algorithm for arbitrary linear codes. It decodes corrupted codewords of any -linear code of message length up…
cs.CC2023
Bounded Simultaneous Messages
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus +3
We consider the following question of bounded simultaneous messages (BSM) protocols: Can computationally unbounded Alice and Bob evaluate a function of their inputs by sen…