Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Victoria

$34,000.00

Understanding complexity through function composition

FY 2024-25

Summary
Fundamental problems about the nature of efficient computation are of immense theoretical, philosophical and practical importance. However, despite their immense importance, the progress has been slow due to meta-mathematical barriers which rule out most approaches. Of a handful that remains, an approach based on fundamental connections between computation and communication has seen promising developments recently. In this proposal, we focus on the following fundamental questions that remain wide open: 1. Are there tasks for which parallel computing does not offer (exponential) speedup? 2. Can we translate computational hardness from weak models of computation to hardness in stronger models? These questions are tightly related to the complexity of a basic operation known as function composition. Function composition abstracts a common strategy in computing: Given a complex task 1) divide the tasks into sub-tasks, 2) solve them, 3) and then combine the results of the sub-tasks to produce the result for the original task. The natural question is, when is this strategy optimal? Answering this question in the model of parallel algorithms and communication protocols would answer the two fundamental questions listed above. Studying function composition in various computational models, including parallel algorithms and communication protocols, is tightly related to the communication complexity of relations (a strict generalization of functions). Unfortunately, most tools and techniques from communication complexity are made for functions and fail to work for relations. Thus, we propose a systematic study of the communication complexity of relations guided by the fundamental questions above. We will use tools and techniques from various areas of computer science like communication complexity, information theory, lifting theorems, quantum computation, circuit complexity, analysis of Boolean functions, pseudo-randomness, and combinatorics. Function composition is fundamental in diverse computational settings like neural networks, quantum circuits, parallel algorithms, cryptographic primitives. More importantly, the best algorithms for many important problems are built using this operation alone in many settings. Thus, the long-term goal of this research direction of understanding the complexity function composition results in breakthrough insights about the powers and limitations of these models. The long-term goals of this proposal will result in significant breakthroughs in theoretical computer science. Even partial progress on the goals (both long-term and short-term) would imply new and important results in many areas like proof complexity, quantum communication, and combinatorial optimization. Because of the ubiquitous nature of function composition, the tools and techniques we develop would also help in many other areas of computer science. Moreover, the training HQP receive will have broad applications in industry and academia.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2022-05211
Name nom
Koroth, Sajin
Department département
Computer Science
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2022
Award amount
34000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
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
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
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
Understanding complexity through function composition
Keywords
communication complexity; circuit complexity; krw conjecture; lifting theorems; query complexity; pseudorandomness; proof complexity; quantum communication complexity
Application summary
Fundamental problems about the nature of efficient computation are of immense theoretical, philosophical and practical importance. However, despite their immense importance, the progress has been slow due to meta-mathematical barriers which rule out most approaches. Of a handful that remains, an approach based on fundamental connections between computation and communication has seen promising developments recently. In this proposal, we focus on the following fundamental questions that remain wide open: 1. Are there tasks for which parallel computing does not offer (exponential) speedup? 2. Can we translate computational hardness from weak models of computation to hardness in stronger models? These questions are tightly related to the complexity of a basic operation known as function composition. Function composition abstracts a common strategy in computing: Given a complex task 1) divide the tasks into sub-tasks, 2) solve them, 3) and then combine the results of the sub-tasks to produce the result for the original task. The natural question is, when is this strategy optimal? Answering this question in the model of parallel algorithms and communication protocols would answer the two fundamental questions listed above. Studying function composition in various computational models, including parallel algorithms and communication protocols, is tightly related to the communication complexity of relations (a strict generalization of functions). Unfortunately, most tools and techniques from communication complexity are made for functions and fail to work for relations. Thus, we propose a systematic study of the communication complexity of relations guided by the fundamental questions above. We will use tools and techniques from various areas of computer science like communication complexity, information theory, lifting theorems, quantum computation, circuit complexity, analysis of Boolean functions, pseudo-randomness, and combinatorics. Function composition is fundamental in diverse computational settings like neural networks, quantum circuits, parallel algorithms, cryptographic primitives. More importantly, the best algorithms for many important problems are built using this operation alone in many settings. Thus, the long-term goal of this research direction of understanding the complexity function composition results in breakthrough insights about the powers and limitations of these models. The long-term goals of this proposal will result in significant breakthroughs in theoretical computer science. Even partial progress on the goals (both long-term and short-term) would imply new and important results in many areas like proof complexity, quantum communication, and combinatorial optimization. Because of the ubiquitous nature of function composition, the tools and techniques we develop would also help in many other areas of computer science. Moreover, the training HQP receive will have broad applications in industry and academia.