MENU 
Theory Seminar
On the Existence of Seedless Condensers: Exploring the Terrain
Mohit GurumukhaniCornell University
WHERE:
3725 Beyster BuildingMap
WHEN:
Friday, April 5, 2024 @ 2:00 pm - 3:00 pm
This event is free and open to the publicAdd to Google Calendar
This event is free and open to the publicAdd to Google Calendar
WEB: Event Website
SHARE:
While the existence of randomness extractors has been thoroughly studied, very little is known regarding the existence of seedless condensers. We prove several new results regarding seedless condensers for three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, one-sided NOSF sources, and almost Chor-Goldreich (CG) sources. We think of these sources as a sequence of random variables on l symbols where at least g symbols are “good”, and the remaining “bad” symbols adversarially depend on the good symbols. The difference between each of these sources is realized by restrictions on the power of the adversary.
The following are our main results:
– When g <= l/2, for all three classes of sources, condensing above rate 1/floor(l/g) is impossible. In fact, this is tight for one-sided NOSF sources and uniform almost CG sources.
– For g > l/2, we show the existence of excellent condensers for uniform one-sided NOSF sources and uniform almost CG sources. In addition, we show the existence of similar condensers for one-sided NOSF sources with only logarithmic min-entropy.
– We show that condensing above rate g/l is impossible for uniform NOSF sources for any g and l.
This is joint work with Eshan Chattopadhyay and Noam Ringach.