Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

McGill University

$38,000.00

Analytic techniques in communication complexity, information complexity, and property testing

EF 2019-20

Résumé
***Communication complexity is one of the most active fields of research in theoretical computer science. It has a broad range of applications, and employs a surprisingly diverse range of techniques and tools from other areas of mathematics (e.g. linear algebra, Fourier analysis, discrepancy theory, functional analysis, additive combinatorics, information theory, etc). In addition to its applications in other subfields of complexity theory, it has real world applications via data structures and data streaming algorithms. ***Although communication complexity has, since its birth, been witnessing steady and rapid progress, it was not until a few years ago that a focus on an information theoretic approach resulted in new and deeper understanding of some of the classical problems of the area. This gave birth to a new area of complexity theory called information complexity. While communication complexity is concerned with minimizing the amount of communication required for two players to evaluate a function that depends on their private inputs, information complexity, on the other hand, is concerned with the amount of information that the communicated bits reveal about the inputs of the two players. The field of information complexity is deeply connected to communication complexity. Shannon, in one of the most important mathematical papers of the 20th century, introduced the notion of entropy to capture the amount of information in a random variable, and set the foundations for the era of digital communication. Shannon's setting is the simplest setting of communication where there is a one-way channel and one player wants to transmit her data to the other player. The general setting of communication complexity is more complicated as the players are allowed to interact. However as the recent results in this area have demonstrated, similar to the way that the information content of a random variable gives the asymptotics of the transmission cost, information complexity of a function provides valuable information about the communication complexity.*** ***One of the main goals of this proposal is to study protocols with optimal information cost and in particular to find a paradigm in which such protocols can be defined properly. This is important as currently we have little understanding of how the optimal protocols look like. The second goal of this proposal is to extend the information theoretic approach to other areas of complexity theory, and the third goal of this proposal is to investigate further applications of recent advances in additive combinatorics to communication complexity and the area of property testing. Additive combinatorics has seen exciting advances in recent years. Some of the tools in this field has found applications in theoretical computer science. We propose to study further applications of these techniques in the areas of communication complexity and property testing.*****
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2016-05807
Name nom
Hatami, Hamed
Department département
Computer Science, School of
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2016
Award amount
38000
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
Installment
inst:4 - 5
Partie
4
Nb partie
5
Application title
Analytic techniques in communication complexity, information complexity, and property testing
Keyword
NSERC
Application summary
***Communication complexity is one of the most active fields of research in theoretical computer science. It has a broad range of applications, and employs a surprisingly diverse range of techniques and tools from other areas of mathematics (e.g. linear algebra, Fourier analysis, discrepancy theory, functional analysis, additive combinatorics, information theory, etc). In addition to its applications in other subfields of complexity theory, it has real world applications via data structures and data streaming algorithms. ***Although communication complexity has, since its birth, been witnessing steady and rapid progress, it was not until a few years ago that a focus on an information theoretic approach resulted in new and deeper understanding of some of the classical problems of the area. This gave birth to a new area of complexity theory called information complexity. While communication complexity is concerned with minimizing the amount of communication required for two players to evaluate a function that depends on their private inputs, information complexity, on the other hand, is concerned with the amount of information that the communicated bits reveal about the inputs of the two players. The field of information complexity is deeply connected to communication complexity. Shannon, in one of the most important mathematical papers of the 20th century, introduced the notion of entropy to capture the amount of information in a random variable, and set the foundations for the era of digital communication. Shannon's setting is the simplest setting of communication where there is a one-way channel and one player wants to transmit her data to the other player. The general setting of communication complexity is more complicated as the players are allowed to interact. However as the recent results in this area have demonstrated, similar to the way that the information content of a random variable gives the asymptotics of the transmission cost, information complexity of a function provides valuable information about the communication complexity.*** ***One of the main goals of this proposal is to study protocols with optimal information cost and in particular to find a paradigm in which such protocols can be defined properly. This is important as currently we have little understanding of how the optimal protocols look like. The second goal of this proposal is to extend the information theoretic approach to other areas of complexity theory, and the third goal of this proposal is to investigate further applications of recent advances in additive combinatorics to communication complexity and the area of property testing. Additive combinatorics has seen exciting advances in recent years. Some of the tools in this field has found applications in theoretical computer science. We propose to study further applications of these techniques in the areas of communication complexity and property testing.*****