2 papers
cs.LG2026
Prediction Under Imperfect Compression: A Theory of Approximate MDL
Qian Li, Xinyu Mao, Shang-Hua Teng +1
Minimum Description Length (MDL) formalizes the principle of Occam's razor by optimizing the total description length: . Fo…
cs.CC2024
Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
Xinyu Mao, Guangxu Yang, Jiapeng Zhang
We prove an Ω(n/k+k) communication lower bound on (k-1)-round distributional complexity of the k-step pointer chasing problem under uniform input distribution, improving the Ω(n/…