Reproduce “Multiplicative and Additive Extractors for Low Entropy Samplable Sources Under Reduced Assumptions” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Marshall Ball, Eshan Chattopadhyay, Mohit Gurumukhani, Ronen Shaltiel, Yunya Zhao
The authors construct seedless extractors for dependent sources generated by samplers, using hashed high-entropy views and correlation breaking. Under nondeterministic-circuit hardness, it extracts one bit with constant error from min-entropy C log n, and near-all bits in polynomial time from entropy n^α. At polylogarithmic entropy, near-all extraction takes quasipolynomial time under nondeterministic hardness, or polynomial time under stronger Σ₂-circuit hardness.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.