Grant: Discovery Grants Program - Individual
University of Waterloo
$46,000.00
Effective tools for the analysis of discrete structures
EF 2023-24
Résumé
The need to analyze patterns and predict the cost of computing with complex systems has never been greater than it is today. In computer science, digital information is modeled using discrete structures, such as graphs (which model connections in networks like the internet) and formal words (which model sequences of letters like DNA). A fundamental problem in computer science, and the related field of combinatorics, is thus the derivation of large-scale behaviour of structures from their formal definitions. This is often accomplished by providing an "asymptotic" estimate for the number of objects with size n (for instance, the number of graphs with n nodes) whose error goes to zero as n gets arbitrarily large. One can also examine the behaviour of parameters among objects of large size (for instance, counting the number of DNA-like sequences with a fixed number of letters by the number of times it contains some fixed pattern). Strikingly, for large classes of structures the behaviour of parameters is dictated by well-known limit theorems from probability. Such results can predict phase transitions in statistical mechanical models, separate DNA patterns which arise via natural selection from random noise, and classify the average behaviour of sorting algorithms on vast amounts of data. This research adapts theoretical mathematical techniques -- both modern and classical -- to create tools for this large-scale analysis: the goal is to develop rigorous methods that can be implemented in software and easily applied by others. The key idea to calculating asymptotic behaviour is to encode a sequence of numbers describing some family of objects by its generating function, an infinite sum whose terms describe the sequence. Well known theories exist to derive equations satisfied by the generating functions enumerating objects with various properties, which then serve as implicit encodings of the sequences. Computational tools can be used to automate much of this process. For generating functions in a single variable, the now well-established field of analytic combinatorics shows how to use tools from complex analysis to determine asymptotic behaviour. For multivariate generating functions -- needed, for instance, when calculating limit theorems for objects with multiple parameters -- much less is known. This research develops the rapidly growing field of analytic combinatorics in several variables, which draws on and extends methods from areas of mathematics as diverse as differential geometry, topology, and computer algebra. We exploit deep mathematical techniques to develop easy-to-use software for the analysis of discrete structures that can be put to use by other researchers across diverse fields. Furthermore, by extending previous methods this work also pushes forward the underlying mathematical theory. The theoretical work is guided by impactful and cutting-edge applications, which include quantum computing, bioinformatics, and queuing theory.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2021-02382
Name nom
Melczer, Stephen
Department département
Department of Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2021
Award amount
46000
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
2714
Research subject group en
Information technology
Research subject group fr
Mathematics of computing
Research subject en
Technologie de l'information
Research subject fr
Mathématiques de l'informatique
Application title
Effective tools for the analysis of discrete structures
Keyword
algorithmic combinatorics; analysis of algorithms; analytic combinatorics; computer algebra
Application summary
The need to analyze patterns and predict the cost of computing with complex systems has never been greater than it is today. In computer science, digital information is modeled using discrete structures, such as graphs (which model connections in networks like the internet) and formal words (which model sequences of letters like DNA). A fundamental problem in computer science, and the related field of combinatorics, is thus the derivation of large-scale behaviour of structures from their formal definitions. This is often accomplished by providing an "asymptotic" estimate for the number of objects with size n (for instance, the number of graphs with n nodes) whose error goes to zero as n gets arbitrarily large. One can also examine the behaviour of parameters among objects of large size (for instance, counting the number of DNA-like sequences with a fixed number of letters by the number of times it contains some fixed pattern). Strikingly, for large classes of structures the behaviour of parameters is dictated by well-known limit theorems from probability. Such results can predict phase transitions in statistical mechanical models, separate DNA patterns which arise via natural selection from random noise, and classify the average behaviour of sorting algorithms on vast amounts of data. This research adapts theoretical mathematical techniques -- both modern and classical -- to create tools for this large-scale analysis: the goal is to develop rigorous methods that can be implemented in software and easily applied by others. The key idea to calculating asymptotic behaviour is to encode a sequence of numbers describing some family of objects by its generating function, an infinite sum whose terms describe the sequence. Well known theories exist to derive equations satisfied by the generating functions enumerating objects with various properties, which then serve as implicit encodings of the sequences. Computational tools can be used to automate much of this process. For generating functions in a single variable, the now well-established field of analytic combinatorics shows how to use tools from complex analysis to determine asymptotic behaviour. For multivariate generating functions -- needed, for instance, when calculating limit theorems for objects with multiple parameters -- much less is known. This research develops the rapidly growing field of analytic combinatorics in several variables, which draws on and extends methods from areas of mathematics as diverse as differential geometry, topology, and computer algebra. We exploit deep mathematical techniques to develop easy-to-use software for the analysis of discrete structures that can be put to use by other researchers across diverse fields. Furthermore, by extending previous methods this work also pushes forward the underlying mathematical theory. The theoretical work is guided by impactful and cutting-edge applications, which include quantum computing, bioinformatics, and queuing theory.