7 papers
PASCAL: A Phase-Aware Shared-Cache Model for Parallel Scans
Zhongchun Zhou, Chengtao Lai, Songtao Mao
In modern AI Accelerators and GPGPUs, many concurrent cores repeatedly access the same shared data. This pattern occurs in attention, where different query tiles share the same K/V…
Abelian Cayley High-Dimensional Expanders with Polylogarithmic Degree
Songtao Mao
We construct an explicit infinite family of simple two-dimensional Cayley complexes over whose degree is polynomial in and whose nontrivial vertex-link eigenva…
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-correcting codes that allow recovery of any single message symbol by probing only a small number of positions from the (possibly corrupted)…