Structural theorems in communication complexity
通信复杂性的结构定理
基本信息
- 批准号:RGPIN-2022-03745
- 负责人:
- 金额:$ 3.5万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2022
- 资助国家:加拿大
- 起止时间:2022-01-01 至 2023-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Communication occurs in several forms across the domains of science and technology. For example, it occurs as interactions between different parts of the human brain, as the transmission of data through the internet, as the exchange of signals between different parts of a microchip, as the exchange of information among a handful of supercomputers. The field of communication complexity provides a rigorous framework for measuring, studying, and understanding communication. It is supported by a rich and deep mathematical theory that employs a surprisingly diverse collection of techniques and tools from other areas of mathematics. This proposal aims to investigate a class of mathematical problems in communication complexity that appear across different fields of computer science and pure mathematics in various disguises. Several seemingly different problems in the fields of communication complexity and machine learning on the one hand, and the purely mathematical fields of abstract harmonic analysis and operator theory, on the other hand, are essentially equivalent. This proposal aims to understand these connections better and devise potential approaches to resolve the fundamental underlying mathematical problems. The problems mentioned above arise from the study of very efficient algorithms in communication complexity. As large data sets become more common in science and technology, it has become increasingly important to understand which problems can be solved super-efficiently. The primary objectives of this proposal arise from the study of this problem in the context of communication complexity: Which communication problems are solvable by protocols that exchange only a few bits of communication? It turns out that the above problem has deep connections to problems in complexity theory, machine learning, harmonic analysis, and operator theory. Communication problems, in the most commonly studied framework, are represented by Boolean matrices. Such matrices also represent binary data. For example, the entries of such a matrix could take true or false values depending on which people show which medical symptoms. Machine learning classification algorithms, which predict the label of a new data point based on a known set of correctly labeled points, often rely on the assumption that it is possible to model the data points and their labels geometrically. The performance and accuracy of many of these algorithms rely on the existence of low-dimensional large-margin representations. The mathematical problems considered in this proposal will help us understand which data sets have such desirable geometric representations.
科学技术领域的交流以多种形式出现。 例如,它发生在人脑不同部分之间的交互、通过互联网传输数据、微芯片不同部分之间的信号交换、以及少数超级计算机之间的信息交换等。通信复杂性领域为测量、研究和理解通信提供了严格的框架。它得到了丰富而深刻的数学理论的支持,该理论采用了来自其他数学领域的令人惊讶的多样化技术和工具。 该提案旨在研究一类通信复杂性中的数学问题,这些问题以各种形式出现在计算机科学和纯数学的不同领域。一方面,通信复杂性和机器学习领域中的几个看似不同的问题,另一方面,抽象调和分析和算子理论等纯数学领域,本质上是等价的。该提案旨在更好地理解这些联系,并设计潜在的方法来解决基本的数学问题。上述问题源于对通信复杂性中非常有效的算法的研究。随着大数据集在科学技术中变得越来越普遍,了解哪些问题可以超高效地解决变得越来越重要。该提案的主要目标源于在通信复杂性的背景下对这个问题的研究:哪些通信问题可以通过仅交换少量通信位的协议来解决? 事实证明,上述问题与复杂性理论、机器学习、调和分析和算子理论中的问题有着深刻的联系。 在最常研究的框架中,通信问题由布尔矩阵表示。这样的矩阵也表示二进制数据。例如,这样的矩阵的条目可以取真值或假值,具体取决于哪些人表现出哪些医疗症状。机器学习分类算法基于一组已知的正确标记点来预测新数据点的标签,通常依赖于可以对数据点及其标签进行几何建模的假设。许多这些算法的性能和准确性依赖于低维大裕度表示的存在。该提案中考虑的数学问题将帮助我们了解哪些数据集具有如此理想的几何表示。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Hatami, Hamed其他文献
Online Learning and Disambiguations of Partial Concept Classes
部分概念类的在线学习与消歧
- DOI:
10.4230/lipics.icalp.2023.42 - 发表时间:
2023 - 期刊:
- 影响因子:0
- 作者:
Cheung, Tsun-Ming;Hatami, Hamed;Hatami, Pooya;Hosseini, Kaave - 通讯作者:
Hosseini, Kaave
The Implicit Graph Conjecture is False
隐式图猜想是错误的
- DOI:
- 发表时间:
2022 - 期刊:
- 影响因子:0
- 作者:
Hatami, Hamed;Hatami, Pooya - 通讯作者:
Hatami, Pooya
Graph norms and Sidorenko's conjecture
- DOI:
10.1007/s11856-010-0005-1 - 发表时间:
2010-01-01 - 期刊:
- 影响因子:1
- 作者:
Hatami, Hamed - 通讯作者:
Hatami, Hamed
A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
通过随机通信复杂性的概率通用图猜想的反例
- DOI:
10.1016/j.dam.2022.07.023 - 发表时间:
2022 - 期刊:
- 影响因子:1.1
- 作者:
Hambardzumyan, Lianna;Hatami, Hamed;Hatami, Pooya - 通讯作者:
Hatami, Pooya
Importance of lactate dehydrogenase (LDH) and monocarboxylate transporters (MCTs) in cancer cells.
- DOI:
10.1002/hsr2.996 - 发表时间:
2023-01 - 期刊:
- 影响因子:2
- 作者:
Hatami, Hamed;Sajedi, Atefe;Mir, Seyed Mostafa;Memar, Mohammad Yousef - 通讯作者:
Memar, Mohammad Yousef
Hatami, Hamed的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Hatami, Hamed', 18)}}的其他基金
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2021
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2020
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2019
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2018
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2017
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2016
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Theory of graph homomorphisms and extremal combinatorics
图同态和极值组合理论
- 批准号:
408045-2011 - 财政年份:2015
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Theory of graph homomorphisms and extremal combinatorics
图同态和极值组合理论
- 批准号:
408045-2011 - 财政年份:2014
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Theory of graph homomorphisms and extremal combinatorics
图同态和极值组合理论
- 批准号:
408045-2011 - 财政年份:2013
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Theory of graph homomorphisms and extremal combinatorics
图同态和极值组合理论
- 批准号:
408045-2011 - 财政年份:2012
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
相似海外基金
Testing Theorems in Analytic Function Theory, Harmonic Analysis and Operator Theory
解析函数论、调和分析和算子理论中的检验定理
- 批准号:
2349868 - 财政年份:2024
- 资助金额:
$ 3.5万 - 项目类别:
Standard Grant
CAREER: KKM-Type Theorems for Piercing Numbers, Mass Partition, and Fair Division
职业:刺穿数、质量划分和公平除法的 KKM 型定理
- 批准号:
2336239 - 财政年份:2024
- 资助金额:
$ 3.5万 - 项目类别:
Continuing Grant
Product structures theorems and unified methods of algorithm design for geometrically constructed graphs
几何构造图的乘积结构定理和算法设计统一方法
- 批准号:
23K10982 - 财政年份:2023
- 资助金额:
$ 3.5万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Limit Theorems and Structural Properties of Stochastic Models
随机模型的极限定理和结构性质
- 批准号:
2889380 - 财政年份:2023
- 资助金额:
$ 3.5万 - 项目类别:
Studentship
New development of geometric complex analysis based on L2 estimates and L2 extension theorems
基于L2估计和L2可拓定理的几何复形分析新进展
- 批准号:
23K12978 - 财政年份:2023
- 资助金额:
$ 3.5万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
Combinatorics of Sharing Theorems, Stratifications, Bruhat Theory and Shimura Varieties
共享定理、分层、Bruhat 理论和 Shimura 簇的组合
- 批准号:
2247382 - 财政年份:2023
- 资助金额:
$ 3.5万 - 项目类别:
Standard Grant
New developments of limit theorems for random walks
随机游走极限定理的新发展
- 批准号:
23K12986 - 财政年份:2023
- 资助金额:
$ 3.5万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
CAREER: Empirical Tests of the Fundamental Theorems of Evolution and Natural Selection
职业:进化和自然选择基本定理的实证检验
- 批准号:
2240063 - 财政年份:2023
- 资助金额:
$ 3.5万 - 项目类别:
Continuing Grant
Positivity and vanishing theorems of direct image of relative canonical bundle
相关正则丛直像的正定理和消失定理
- 批准号:
23KJ0673 - 财政年份:2023
- 资助金额:
$ 3.5万 - 项目类别:
Grant-in-Aid for JSPS Fellows