CRII: CIF: Locality in Error Correcting Codes: Fundamental Trade-Offs

CRII:CIF:纠错码的局部性:基本权衡

基本信息

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

项目摘要

This project investigates the fundamental trade-offs surrounding locality in error correcting codes. In error correcting codes, "locality" refers to several ways of quantifying how easily a small amount of information can be recovered from encoded data. Notions of locality have been around almost as long as coding theory itself, and today the study of locality in error correcting codes is fundamental to applications ranging from the very theoretical (complexity theory) to the very practical (distributed storage schemes). This research improves our basic scientific understanding of locality, and in doing so it makes progress on these applications. Beyond its scientific impact, this project has broader educational impact, through the development of course materials and by providing opportunities for graduate and undergraduate research.The approach of this research is to bridge a gap between two different bodies of literature. In Theoretical Computer Science, Locally Decodable and Locally Correctable Codes have been studied for over 15 years, and have been linked to many fundamental problems in complexity theory and cryptography. In the past five years, the study of locality has also taken off in distributed storage, in the form of Locally Recoverable Codes and related notions. These two lines of research operate in different parameter regimes and are motivated by different applications. The current research ties the two together by studying intermediate parameter regimes, and explores the fundamental mathematical trade-offs surrounding locality. By extending our understanding of locality in coding theory, this research can make progress on important problems in coding, complexity theory, cryptography, and distributed storage; it also develops a theory which could find many more applications going forward.
本计画探讨错误更正码中局部性的基本权衡。 在纠错码中,“局部性”是指量化从编码数据中恢复少量信息的容易程度的几种方法。 局部性的概念几乎与编码理论本身一样长,今天纠错码中局部性的研究对于从非常理论的(复杂性理论)到非常实用的(分布式存储方案)的应用都是基础。 这项研究提高了我们对局部性的基本科学理解,并在此过程中在这些应用方面取得了进展。 除了其科学影响,该项目具有更广泛的教育影响,通过课程材料的开发,并通过提供研究生和本科生research. Approach研究的机会是弥合两个不同的文学机构之间的差距。 在理论计算机科学中,局部可解码和局部可纠正码已经研究了15年以上,并且与复杂性理论和密码学中的许多基本问题有关。在过去的五年中,局部性的研究也在分布式存储中以局部可恢复代码和相关概念的形式开始。 这两条线的研究工作在不同的参数制度,并由不同的应用程序的动机。目前的研究通过研究中间参数机制将两者联系在一起,并探索了围绕局部性的基本数学权衡。 通过扩展我们对编码理论中局部性的理解,这项研究可以在编码,复杂性理论,密码学和分布式存储中的重要问题上取得进展;它还开发了一种可以找到更多应用的理论。

项目成果

期刊论文数量(4)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Local List Recovery of High-Rate Tensor Codes & Applications
高速张量代码的本地列表恢复
Repairing Multiple Failures for Scalar MDS Codes
修复标量 MDS 代码的多个故障
Locality via Partially Lifted Codes
通过部分提升代码的局部性
Limitations of piggybacking codes with low substriping
{{ 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 }}

Mary Wootters其他文献

Reusable low-error compressive sampling schemes through privacy
通过隐私可重复使用的低误差压缩采样方案
  • DOI:
  • 发表时间:
    2012
  • 期刊:
  • 影响因子:
    0
  • 作者:
    A. Gilbert;B. Hemenway;M. Strauss;David P. Woodruff;Mary Wootters
  • 通讯作者:
    Mary Wootters
Linear-Time List Recovery of High-Rate Expander Codes
高速扩展器代码的线性时间列表恢复
  • DOI:
    10.1007/978-3-662-47672-7_57
  • 发表时间:
    2015
  • 期刊:
  • 影响因子:
    0
  • 作者:
    B. Hemenway;Mary Wootters
  • 通讯作者:
    Mary Wootters
A Note on the Permuted Puzzles Toy Conjecture
关于排列拼图玩具猜想的一个注解
  • DOI:
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Keller Blackwell;Mary Wootters
  • 通讯作者:
    Mary Wootters
Configuration spaces of convex and embedded polygons in the plane
  • DOI:
    10.1007/s10711-013-9910-x
  • 发表时间:
    2013-08-31
  • 期刊:
  • 影响因子:
    0.500
  • 作者:
    Don Shimamoto;Mary Wootters
  • 通讯作者:
    Mary Wootters
List-Decodability of Structured Ensembles of Codes (Invited Talk)
结构化代码集合的列表可解码性(特邀演讲)

Mary Wootters的其他文献

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

{{ truncateString('Mary Wootters', 18)}}的其他基金

NSF-BSF: AF: Small: Advancing Coding Theory Through the Lens of Pseudorandomness
NSF-BSF:AF:小:通过伪随机性的视角推进编码理论
  • 批准号:
    2231157
  • 财政年份:
    2023
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
NSF-BSF: AF: Small: Algorithms for Graph-Based Codes
NSF-BSF:AF:小型:基于图形的代码算法
  • 批准号:
    2133154
  • 财政年份:
    2022
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
NSF Student Travel Grant for 2022 Theoretical Computer Science (TCS) Women Meeting at Symposium on Theory of Computing (STOC)
NSF 学生旅费补助金用于 2022 年理论计算机科学 (TCS) 女性在计算理论研讨会 (STOC) 上的会议
  • 批准号:
    2226116
  • 财政年份:
    2022
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
CAREER: New Fundamentals in Coding Theory
职业:编码理论的新基础
  • 批准号:
    1844628
  • 财政年份:
    2019
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
CCF-BSF: AF: CIF: Small: Low Complexity Error Correction
CCF-BSF:AF:CIF:小:低复杂性纠错
  • 批准号:
    1814629
  • 财政年份:
    2018
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
PostDoctoral Research Fellowship
博士后研究奖学金
  • 批准号:
    1400558
  • 财政年份:
    2014
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Fellowship Award

相似国自然基金

Wolbachia的cif因子与天麻蚜蝇dsx基因协同调控生殖不育的机制研究
  • 批准号:
    JCZRQN202501187
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
SHR和CIF协同调控植物根系凯氏带形成的机制
  • 批准号:
    31900169
  • 批准年份:
    2019
  • 资助金额:
    23.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

Collaborative Research: CIF: Medium: Snapshot Computational Imaging with Metaoptics
合作研究:CIF:Medium:Metaoptics 快照计算成像
  • 批准号:
    2403122
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
Collaborative Research: CIF-Medium: Privacy-preserving Machine Learning on Graphs
合作研究:CIF-Medium:图上的隐私保护机器学习
  • 批准号:
    2402815
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
Collaborative Research: CIF: Small: Mathematical and Algorithmic Foundations of Multi-Task Learning
协作研究:CIF:小型:多任务学习的数学和算法基础
  • 批准号:
    2343599
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
Collaborative Research: CIF: Small: Mathematical and Algorithmic Foundations of Multi-Task Learning
协作研究:CIF:小型:多任务学习的数学和算法基础
  • 批准号:
    2343600
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
CIF: Small: Learning Low-Dimensional Representations with Heteroscedastic Data Sources
CIF:小:使用异方差数据源学习低维表示
  • 批准号:
    2331590
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
Collaborative Research: CIF-Medium: Privacy-preserving Machine Learning on Graphs
合作研究:CIF-Medium:图上的隐私保护机器学习
  • 批准号:
    2402817
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
CAREER: CCF: CIF: Randomized Experimentation for Systems with Time-varying Dynamics and Network Interference
职业:CCF:CIF:具有时变动态和网络干扰的系统的随机实验
  • 批准号:
    2337796
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
CIF: Small: Graph Structure Discovery of Networked Dynamical Systems
CIF:小:网络动力系统的图结构发现
  • 批准号:
    2327905
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
Collaborative Research: NSF-AoF: CIF: Small: AI-assisted Waveform and Beamforming Design for Integrated Sensing and Communication
合作研究:NSF-AoF:CIF:小型:用于集成传感和通信的人工智能辅助波形和波束成形设计
  • 批准号:
    2326622
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
CIF: Small: Signal Processing and Learning for NOMA Millimeter-Wave Massive MIMO Systems
CIF:小型:NOMA 毫米波大规模 MIMO 系统的信号处理和学习
  • 批准号:
    2413622
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了