Grant: Discovery Launch Supplement
University of Toronto
$12,500.00
New approaches for studying the BPP = P conjecture, and their broad implications
FY 2024-25
Summary
Randomness has been an invaluable algorithmic tool since the early days of computer science. However, despite its widespread use, we still do not have a good understanding of the value of randomness for algorithms. In particular, we do not know in which settings randomness is actually necessary for algorithms to solve the problem at hand, and in which settings randomness is superfluous, and can be simulated by careful deterministic approaches.
The core challenge in studying this question is called derandomization: This is the challenge of deterministically simulating randomness, which allows to replace randomized algorithms by deterministic ones. This challenge is important theoretically, since studying it helps us understand the value of randomness for algorithms. And it is also important for practical applications, since deterministic algorithms are more reliable and less vulnerable to malevolent tampering, compared to algorithms that use heuristics to produce supposedly random choices.
The classical paradigm for derandomization was introduced in the 1980s, and has been highly influential. In recent years, a new method for derandomization has been developed. The new method has the potential to bypass inherent limitations of the classical paradigm, simulating randomness deterministically in ways that are extremely efficient and that have better theoretical guarantees. Moreover, the study of this new method turned out to be closely related to recent research in other areas of computer science, such as cryptography and interactive proof systems.
The goal of this research program is to leverage the new method for derandomization in order to improve our understanding of the value of randomness for algorithms. We will design deterministic algorithms that simulate randomness with better theoretical guarantees, compared to currently known algorithms. In addition, we will design algorithms that simulate randomness in extremely efficient ways, in terms of time and memory consumption. Lastly, we will leverage recent research in other areas of computer science, such as cryptography and interactive proof systems, to better relate the study of derandomization to other important questions.
Program
Discovery Launch Supplement
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
DGECR-2024-00453
Name nom
Tell, Roy
Department département
Computer and Mathematical Sciences
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
12500
Program id
DGECR
Program name en
Discovery Launch Supplement
Program name fr
Supplément Tremplin vers la découverte
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
803
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer communications
Area of application fr
Téléinformatique
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
New approaches for studying the BPP = P conjecture, and their broad implications
Keywords
theoretical computer science; computational complexity theory; randomness in computation; pseudorandomness and derandomization; circuit complexity; targeted pseudorandom generators; circuit-analysis algorithms; explicit constructions
Application summary
Randomness has been an invaluable algorithmic tool since the early days of computer science. However, despite its widespread use, we still do not have a good understanding of the value of randomness for algorithms. In particular, we do not know in which settings randomness is actually necessary for algorithms to solve the problem at hand, and in which settings randomness is superfluous, and can be simulated by careful deterministic approaches.
The core challenge in studying this question is called derandomization: This is the challenge of deterministically simulating randomness, which allows to replace randomized algorithms by deterministic ones. This challenge is important theoretically, since studying it helps us understand the value of randomness for algorithms. And it is also important for practical applications, since deterministic algorithms are more reliable and less vulnerable to malevolent tampering, compared to algorithms that use heuristics to produce supposedly random choices.
The classical paradigm for derandomization was introduced in the 1980s, and has been highly influential. In recent years, a new method for derandomization has been developed. The new method has the potential to bypass inherent limitations of the classical paradigm, simulating randomness deterministically in ways that are extremely efficient and that have better theoretical guarantees. Moreover, the study of this new method turned out to be closely related to recent research in other areas of computer science, such as cryptography and interactive proof systems.
The goal of this research program is to leverage the new method for derandomization in order to improve our understanding of the value of randomness for algorithms. We will design deterministic algorithms that simulate randomness with better theoretical guarantees, compared to currently known algorithms. In addition, we will design algorithms that simulate randomness in extremely efficient ways, in terms of time and memory consumption. Lastly, we will leverage recent research in other areas of computer science, such as cryptography and interactive proof systems, to better relate the study of derandomization to other important questions.