5 papers
The Polynomial-Time Low-Degree Conjecture is False
Songtao Mao
The low-degree method and its associated lower bounds are widely used to guide algorithm design and to provide evidence of computational hardness in average-case inference, high-di…
High-Rate Public-Key Pseudorandom Codes for Edit Errors
Shengtang Huang, Xin Li, Songtao Mao +1
Pseudorandom codes (PRCs), introduced by Christ and Gunn (CRYPTO '2024), are error-correcting codes whose codewords are computationally indistinguishable from uniformly random stri…
Near Optimal Algorithms for Noisy -XOR under Low-Degree Heuristic
Songtao Mao
Noisy -XOR is a basic average-case inference problem in which one observes random noisy -ary parity constraints and seeks to recover, or more weakly, detect, a hidden Boolean…
When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
Kuan Cheng, Xin Li, Songtao Mao
Locally decodable codes (LDCs) are error correction codes that allow recovery of any single message symbol by probing only a small number of positions from the (possibly corrupted)…
Improved Explicit Near-Optimal Codes in the High-Noise Regimes
Xin Li, Songtao Mao
We study uniquely decodable codes and list decodable codes in the high-noise regime, specifically codes that are uniquely decodable from fraction of error…