Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Nearly-Linear Time Seeded Extractors with Short Seeds
Dean Doron, João Ribeiro
Seeded extractors are fundamental objects in pseudorandomness and cryptography, and a deep line of work has designed polynomial-time seeded extractors with nearly-optimal parameter…
cs.CC2025
Low-Degree Polynomials Are Good Extractors
Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff +1
We prove that random low-degree polynomials (over ) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomne…