CAREER: Information Theoretic Methods in Data Structures

职业:数据结构中的信息论方法

基本信息

  • 批准号:
    1844887
  • 负责人:
  • 金额:
    $ 50.76万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2019
  • 资助国家:
    美国
  • 起止时间:
    2019-02-01 至 2022-01-31
  • 项目状态:
    已结题

项目摘要

Data structures constitute the backbone of algorithm design and information retrieval, and underlie the performance of countless industrial-scale applications, from internet routing and road navigation to cloud storage, search and compression. As such, understanding what data structures can, and cannot, compute efficiently is a fundamental question in both theory and practice. Motivated by this question and the growing amounts of data to be processed in modern databases, this project is focused on two primary themes: (1) developing new mathematical tools for proving unconditional lower bounds on the operational time and memory consumption of static and dynamic data structures, thereby reducing the (huge) existing gaps from known upper bounds; (2) exploring the interplay between information theory and data structures in large-scale storage applications. In particular, the second part of the project will focus on designing novel data structures for information retrieval (mainly compression and search) over correlated datasets. The project reflects a scientific agenda for conducting interdisciplinary research in the intersection of theoretical computer science and information theory, bridging and impacting research and education in both communities.In recent years, information theory and communication complexity have emerged as powerful mathematical tools for proving unconditional lower bounds on the operational time of data structures and for analyzing the power of pre-processing information. Proving time-space lower bounds in the "cell-probe" model has long been recognized as one of the major challenges of complexity theory, with many implications on theory and practice. The first part of this project will develop new information-theoretic tools for proving such trade-offs, and will explore connections between data-structure lower bounds and other areas in computational complexity and mathematics, such as locally-decodable codes, circuit complexity, streaming, functional analysis, rigidity and algebraic geometry. Apart from its role as an analytic tool for computation, the interplay between information theory and data structures is particularly vital in large-scale storage applications. The increasing size and complexity of data sets being uploaded and processed on remote data centers, pose a real problem of scalability for traditional data compression and database architectures. The second part of this project establishes a new research program for storage and information-retrieval problems that arise over massive correlated data sets, focusing on the (unexplored) problem of locally decodable source coding for correlated files in static and dynamic scenarios.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
数据结构构成了算法设计和信息检索的支柱,并支撑着无数工业规模应用的性能,从互联网路由和道路导航到云存储,搜索和压缩。因此,理解什么数据结构可以和不能有效地计算是理论和实践中的一个基本问题。基于这个问题和现代数据库中需要处理的数据量的不断增长,本项目集中于两个主要主题:(1)开发新的数学工具,用于证明静态和动态数据结构的操作时间和内存消耗的无条件下限,从而减少已知上限的(巨大的)现有差距;(2)探索信息论与数据结构在大规模存储应用中的相互作用。特别是,该项目的第二部分将侧重于设计新的数据结构,用于相关数据集的信息检索(主要是压缩和搜索)。该项目反映了在理论计算机科学和信息理论的交叉点进行跨学科研究的科学议程,桥接和影响两个社区的研究和教育。近年来,信息理论和通信复杂性已经成为证明数据结构运算时间无条件下限和分析预处理信息能力的强大数学工具。证明“细胞探测”模型的时空下界一直被认为是复杂性理论的主要挑战之一,具有许多理论和实践意义。该项目的第一部分将开发新的信息理论工具来证明这种权衡,并将探索数据结构下界与计算复杂性和数学中的其他领域之间的联系,例如局部可解码代码,电路复杂性,流,功能分析,刚性和代数几何。除了作为计算的分析工具之外,信息论和数据结构之间的相互作用在大规模存储应用中尤为重要。在远程数据中心上传和处理的数据集的规模和复杂性不断增加,给传统的数据压缩和数据库架构带来了真实的可扩展性问题。该项目的第二部分建立了一个新的研究计划,存储和信息检索问题,出现在大量的相关数据集,重点是(未开发的)问题的本地解码源编码的相关文件在静态和动态的情况下。这个奖项反映了NSF的法定使命,并已被认为是值得支持的评估使用基金会的智力价值和更广泛的影响审查标准。

项目成果

期刊论文数量(7)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
A faster algorithm for solving general LPs
A Faster Algorithm for General LPs
适用于一般 LP 的更快算法
  • DOI:
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Shunhua Jiang, Zhao Song
  • 通讯作者:
    Shunhua Jiang, Zhao Song
An Adaptive Step Toward the Multiphase Conjecture and Lower Bounds on Nonlinear Networks
非线性网络多相猜想和下界的自适应步骤
  • DOI:
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Young Kun Ko, Omri Weinstein
  • 通讯作者:
    Young Kun Ko, Omri Weinstein
Polynomial Data Structure Lower Bounds in the Group Model
群模型中的多项式数据结构下界
  • DOI:
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Alexander Golovnev, Gleb Posobin
  • 通讯作者:
    Alexander Golovnev, Gleb Posobin
Settling the relationship between Wilber’s bounds for dynamic optimality
解决威尔伯动态最优性界限之间的关系
  • DOI:
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Victor Lecomte, Omri Weinstein
  • 通讯作者:
    Victor Lecomte, Omri Weinstein
{{ 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 }}

Omri Weinstein其他文献

Fe b 20 19 Static Data Structure Lower Bounds Imply Rigidity
Fe b 20 19 静态数据结构下界意味着刚性
  • DOI:
  • 发表时间:
    2019
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Zeev Dvir;Alexander Golovnev;Omri Weinstein
  • 通讯作者:
    Omri Weinstein
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication
四方通信的摊销动态单元探测下限
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity
近似单调布尔函数对 $O(sqrt{n})$ 查询复杂度的影响
  • DOI:
    10.1007/978-3-642-22935-0_56
  • 发表时间:
    2011
  • 期刊:
  • 影响因子:
    0
  • 作者:
    D. Ron;R. Rubinfeld;S. Safra;Omri Weinstein
  • 通讯作者:
    Omri Weinstein
Information Complexity and the Quest for Interactive Compression
信息复杂性和交互式压缩的探索
Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis
在 no(log n) 时间内逼近最佳纳什均衡打破了指数时间假设

Omri Weinstein的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

相似国自然基金

基于行为学理论的ICU护患非语言沟通干预方案构建与应用研究
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
循环码的自同构群理论与应用研究
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
多源网络攻击下Markov跳变信息物理系 统的安全性分析与控制
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
面向信息效用的卫星互联网通信理论与 技术
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
复杂探测任务下深空信息传输理论与优化策略研究
  • 批准号:
    Z25F010021
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
面向沉浸式通信的语义信息传输理论与方法
  • 批准号:
    Z25F010031
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
基于信息-动机-行为技能模型理论的山区PICC带管居家患者自我管理方案构建与应用研究
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
时空信息论驱动的纠缠光量子定位理论与方法研究
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
新型网络环境中的隐写理论与关键技术研究
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
基于先验信息的矩阵恢复理论与算法研究
  • 批准号:
  • 批准年份:
    2025
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目

相似海外基金

CAREER: Information-Theoretic Measures for Fairness and Explainability in High-Stakes Applications
职业:高风险应用中公平性和可解释性的信息论测量
  • 批准号:
    2340006
  • 财政年份:
    2024
  • 资助金额:
    $ 50.76万
  • 项目类别:
    Continuing Grant
CAREER: Towards Trustworthy Machine Learning via Learning Trustworthy Representations: An Information-Theoretic Framework
职业:通过学习可信表示实现可信机器学习:信息理论框架
  • 批准号:
    2339686
  • 财政年份:
    2024
  • 资助金额:
    $ 50.76万
  • 项目类别:
    Continuing Grant
CAREER: Optimism in Causal Reasoning via Information-theoretic Methods
职业:通过信息论方法进行因果推理的乐观主义
  • 批准号:
    2239375
  • 财政年份:
    2023
  • 资助金额:
    $ 50.76万
  • 项目类别:
    Continuing Grant
CAREER: Information-Theoretic Approach to Turbulence: Causality, Modeling & Control
职业:湍流的信息理论方法:因果关系、建模
  • 批准号:
    2140775
  • 财政年份:
    2021
  • 资助金额:
    $ 50.76万
  • 项目类别:
    Continuing Grant
CAREER: Information-Theoretic and Statistical Foundations of Generative Models
职业:生成模型的信息理论和统计基础
  • 批准号:
    1942230
  • 财政年份:
    2020
  • 资助金额:
    $ 50.76万
  • 项目类别:
    Continuing Grant
CAREER: Information-Theoretic Foundations of Fairness in Machine Learning
职业:机器学习公平性的信息理论基础
  • 批准号:
    1845852
  • 财政年份:
    2019
  • 资助金额:
    $ 50.76万
  • 项目类别:
    Continuing Grant
CAREER: Communication- Efficient Distributed Computation: Information- Theoretic Foundations and Algorithms
职业:通信高效分布式计算:信息理论基础和算法
  • 批准号:
    1651492
  • 财政年份:
    2017
  • 资助金额:
    $ 50.76万
  • 项目类别:
    Continuing Grant
CAREER: Information-Theoretic Methods for RNA Analytics
职业:RNA 分析的信息理论方法
  • 批准号:
    1651236
  • 财政年份:
    2017
  • 资助金额:
    $ 50.76万
  • 项目类别:
    Continuing Grant
CAREER: An Information Theoretic Perspective of Consistent Distributed Storage Systems
职业:一致分布式存储系统的信息论视角
  • 批准号:
    1553248
  • 财政年份:
    2016
  • 资助金额:
    $ 50.76万
  • 项目类别:
    Continuing Grant
CAREER: An Information-Theoretic Approach to Communication-Constrained Statistical Learning
职业:通信受限统计学习的信息论方法
  • 批准号:
    1254041
  • 财政年份:
    2013
  • 资助金额:
    $ 50.76万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了