AF: Small: Randomness in Computation - New Directions and Techniques

点击翻译按钮获取中文摘要

The overarching goal of this project is to improve our understanding of the power of randomness in designing efficient algorithms, constructing graphs that behave like "random" graphs, and in proving certain mathematical results. One of the basic questions in randomness is that of obtaining "pure" random bits from real-world sources of randomness. Procedures developed for this purpose are called extractors and have found many applications, some of which are completely unrelated to their original motivation. A recent line of research (by the PI and others) has resulted in new techniques, especially algebraic, being introduced to this area. This resulted in new constructions of extractors that go beyond previous barriers. One of the main goals of this project is to further study these techniques and obtain better constructions of extractors producing more random bits of higher quality than known before.Another central question studied in this project is Polynomial Identity Testing (PIT) - testing whether a given arithmetic expression is an identity or not. This can be done efficiently using randomness but a deterministic algorithm is not known. The importance of finding deterministic algorithms for this problem (or even to special cases of it) is of major importance and attracted a lot of attention (including work by the PI with co-authors). A third major goal of this project is to obtain deterministic PIT algorithms for classes of circuits for which only randomized algorithms are known. This is tightly related to proving new computational hardness results, being a yet another target for this project.This project aims at expanding our understanding of randomness as a computational resource while developing new and transformative mathematical techniques and concepts for attacking long-standing problems in this area. Progress on could lead to new practically useful insights into algorithms, coding theory and cryptography among others. The PI will be involved in organizing seminars, reading groups and writing survey articles aimed at disseminating knowledge gained during the proposed research to the wider academic community. In addition, the PI will give public talks, including to high school students, and those aimed at a non-technical audience.