Showing 2023Show all
2 papers · 1 filter
cs.CC2023
On the Existence of Seedless Condensers: Exploring the Terrain
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach
We prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, online NOSF (oNOSF) sources [AO…
cs.CC2023
Extractors for Polynomial Sources over
Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani
We explicitly construct the first nontrivial extractors for degree polynomial sources over . Our extractor requires min-entropy $k\geq n - \tildeΩ(\sqrt{\…