3 papers
math.CO2024
Improved Exponent for Marton's Conjecture in
Jyun-Jie Liao
A conjecture of Marton, widely known as the polynomial Freiman-Ruzsa conjecture, was recently proved by Gowers, Green, Manners and Tao for any bounded-torsion Abelian group . In…
cs.CC2021
Extractors for Sum of Two Sources
Eshan Chattopadhyay, Jyun-Jie Liao
We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An -sumset…
cs.CC2020
Optimal Error Pseudodistributions for Read-Once Branching Programs
Eshan Chattopadhyay, Jyun-Jie Liao
In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length and width read-once branching programs with seed length $O(\log n\cdot \log(nw)+…