Extractors are efficient procedures that produce high-quality randomness from lower-quality randomness. They are a basic building-block primitive in many areas and consequently they have been studied intensively. The project extends the investigation of extractors in several new important directions. Broadly speaking, the goal is to build extractors with significantly better efficiency and robustness.
Specifically, one objective is to design bitwise locally computable extractors which are the information-theoretical analogue of pseudo-random functions. Such extractors produce each of their output bits separately in time polylogarithmic in the length of the weakly-random string. Another objective is the study of exposure-resilient extractors. These extractors are stronger than standard extractors in that they pass statistical tests that adjust themselves adaptively depending on the source of randomness. Exposure-resilient extractors have applications in cryptography and in the derandomization of probabilistic sublinear-time algorithms, including algorithms in property testing and machine learning. The project investigates the possibility of constructing exposure-resilient extractors with superior parameters, studies lower bounds on the achievable parameters, and explores the field of applications of such extractors, which appears to be vast.
Intellectual Merit. The research tackles natural problems that are new and challenging. It has the promise to build extractors with attributes that have a real impact in theoretical and practical applications. Some preliminary results have already been obtained and they required the development of novel techniques. The concept of exposure-resilient extractors adds a new dimension in the study of extractors and opens the possibility of some new applications.
Broader Impact. Extractors have applications in randomized algorithms, constructive combinatorics, cryptography, error-correcting codes, and other areas. This research will make many of these applications more practical and more robust. Some parts of the project are likely to have implications in areas that currently are not linked to extractors such as property testing. The project will allow undergraduate and graduate students to participate in research activities that have a strong theoretical flavor and the promise of real-world applications. It will help in establishing a theoretical line in the new doctorate program at Towson University. The results will be communicated at seminars and conferences in the US and abroad and will be made widely available.
