Grant: Discovery Grants Program - Individual
University of Victoria
$55,000.00
The Complexity of Computing with Infinite Data
FY 2024-25
Summary
Traditional computational complexity theory deals with computation on finite inputs, such as natural numbers or finite graphs. However, in many settings it is natural to consider computation over infinitary input data. For example, many programming languages support infinitary data such as streams or higher-order functions, and many semantic models for these languages are inherently continuous. In computable real analysis, models based on computability over real numbers are used to abstract numerical computation. In ordinary complexity theory and cryptography, computation with respect to oracles is used to understand the relationship between classes and assumptions. As a final example, many approaches to the proof theory of constructive formal systems rely on higher-order computable functions.
There has been considerable work on computability over infinite data, dating back to Turing's model for computable real numbers, but in general the intersection between such models and complexity theory remains relatively unexplored. The goal of my research is to refine our understanding of the complexity of computing with infinite data. While this work is of fundamental interest, it has the potential to impact a variety of applications, including techniques for reasoning about the efficiency of programs that utilize higher-order features or perform numerical computation, foundational results on the complexity of mathematical axioms, and a better understanding of relationships between classes of NP search problems and the use of oracles in cryptographic proofs.
A guiding principle in my approach is to retain the finitary nature of computation: computations have finite length, storage is finite, and any input or output operation involves only a finite amount of data. As a result, the representation of input data becomes a matter of central concern. I will use well-understood models, such as ordinary Turing machines taking finite inputs (type-one) or equipped with an oracle (type-two), and formulate input representations to model infinite inputs. This approach is common in the study of computation, and may lead to models which capture complexity. For example, computation of real-valued functions may be modeled in the type-one setting, by considering inputs and outputs represented by rational approximations; in this setting it is also possible to model complexity. Computable operators that take computable functions as input may also be modeled in the type-one setting by using Goedel numbers to represent inputs, but in this case there is no simple way to model complexity. For many applications it is necessary to go beyond the type-one framework. This includes the complexity of operators in analysis, search complexity, and interpretations of constructive logics. My proposed research builds on my previous work on complexity for type-level two and higher, while exploring new approaches based on representations tailored to application-specific input domains.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2021-02481
Name nom
Kapron, Bruce
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
2021
Award amount
55000
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
802
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
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
The Complexity of Computing with Infinite Data
Keywords
higher-order computability; computational complexity; feasible analysis; models for programming languages; constructive logic; black-box constructions; search complexity
Application summary
Traditional computational complexity theory deals with computation on finite inputs, such as natural numbers or finite graphs. However, in many settings it is natural to consider computation over infinitary input data. For example, many programming languages support infinitary data such as streams or higher-order functions, and many semantic models for these languages are inherently continuous. In computable real analysis, models based on computability over real numbers are used to abstract numerical computation. In ordinary complexity theory and cryptography, computation with respect to oracles is used to understand the relationship between classes and assumptions. As a final example, many approaches to the proof theory of constructive formal systems rely on higher-order computable functions.
There has been considerable work on computability over infinite data, dating back to Turing's model for computable real numbers, but in general the intersection between such models and complexity theory remains relatively unexplored. The goal of my research is to refine our understanding of the complexity of computing with infinite data. While this work is of fundamental interest, it has the potential to impact a variety of applications, including techniques for reasoning about the efficiency of programs that utilize higher-order features or perform numerical computation, foundational results on the complexity of mathematical axioms, and a better understanding of relationships between classes of NP search problems and the use of oracles in cryptographic proofs.
A guiding principle in my approach is to retain the finitary nature of computation: computations have finite length, storage is finite, and any input or output operation involves only a finite amount of data. As a result, the representation of input data becomes a matter of central concern. I will use well-understood models, such as ordinary Turing machines taking finite inputs (type-one) or equipped with an oracle (type-two), and formulate input representations to model infinite inputs. This approach is common in the study of computation, and may lead to models which capture complexity. For example, computation of real-valued functions may be modeled in the type-one setting, by considering inputs and outputs represented by rational approximations; in this setting it is also possible to model complexity. Computable operators that take computable functions as input may also be modeled in the type-one setting by using Goedel numbers to represent inputs, but in this case there is no simple way to model complexity. For many applications it is necessary to go beyond the type-one framework. This includes the complexity of operators in analysis, search complexity, and interpretations of constructive logics. My proposed research builds on my previous work on complexity for type-level two and higher, while exploring new approaches based on representations tailored to application-specific input domains.