EAGER: Complexity of Computation on Codes and Lattices
EAGER:码和格计算的复杂性
基本信息
- 批准号:1649515
- 负责人:
- 金额:$ 20万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2016
- 资助国家:美国
- 起止时间:2016-09-01 至 2018-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Error-correcting codes and point lattices are central primitives in science and engineering (e.g., in communication and storage systems, electronic circuit design, and secure cryptographic systems). These algebraic primitives also have deep connections with fundamental questions in theoretical computer science and mathematics. Despite being intensely studied for their practical relevance, many computational problems on such algebraic objects remain widely open. Consequently, improving our understanding of the power and limitations of codes and lattices in diverse computational models will have a significant impact in many application domains. The research plan outlined in this project aims to address algorithmic challenges at the heart of modern cryptography and coding theory, by proposing novel approaches and models of computation. The project aims to reveal influential interconnections between codes and lattices, and between the computational problems specific to them, by leveraging algebraic and geometric aspects, together with notions of structure and symmetry. The outcomes of this project will be integrated in new courses, and in undergraduate and graduate research. This project will also help support an active theory group at Purdue University, and help train students to become competitive in their future careers. Specifically, the proposed project will advance the state of the art of computational problems that can be abstracted as variants of nearest-neighbor search problems in the context of error-correcting codes and point lattices. Efficient algorithms for these problems could play a transformative role in applications to storage systems, and hardness results could impact the security of lattice-base cryptography. The project will also focus on conceptualizing and formalizing models of sublinear computation for lattice problems, with the goal of overcoming known barriers from the study of sublinear models for codes. Super-efficient algorithms for lattice problems could have applications in mathematical optimization, and in lattice-based communication. The project will explore and develop insights from diverse areas including coding and information theory, sublinear algorithms, cryptography, and optimizations.
纠错码和点格是科学和工程(例如,在通信和存储系统、电子电路设计和安全密码系统中)的中心原语。这些代数原语也与理论计算机科学和数学中的基本问题有着深刻的联系。尽管由于其实际意义而被广泛研究,但许多关于此类代数对象的计算问题仍然广泛开放。因此,提高我们对不同计算模型中代码和格的能力和局限性的理解将对许多应用领域产生重大影响。本项目概述的研究计划旨在通过提出新的计算方法和模型来解决现代密码学和编码理论核心的算法挑战。该项目旨在通过利用代数和几何方面,以及结构和对称的概念,揭示代码和晶格之间以及特定于它们的计算问题之间有影响力的相互联系。这个项目的成果将被整合到新课程中,以及本科和研究生的研究中。该项目还将帮助支持普渡大学的一个活跃的理论小组,并帮助培养学生在未来的职业生涯中具有竞争力。具体来说,提议的项目将推动计算问题的发展,这些问题可以抽象为纠错码和点格环境中最近邻搜索问题的变体。针对这些问题的有效算法可能在存储系统的应用中发挥变革性作用,而硬度结果可能影响格基加密的安全性。该项目还将侧重于点阵问题的次线性计算模型的概念化和形式化,目标是克服代码次线性模型研究中的已知障碍。格问题的超高效算法可以应用于数学优化和基于格的通信。该项目将探索和发展不同领域的见解,包括编码和信息论、次线性算法、密码学和优化。
项目成果
期刊论文数量(16)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels
简短公告:计算有限通道中放宽的局部可校正代码
- DOI:
- 发表时间:2018
- 期刊:
- 影响因子:0
- 作者:Blocki, J;Gandikota, V;Grigorescu, E;Zhou, S.
- 通讯作者:Zhou, S.
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
检测植入派系的统计算法和下界
- DOI:10.1145/3046674
- 发表时间:2017
- 期刊:
- 影响因子:2.5
- 作者:Feldman, Vitaly;Grigorescu, Elena;Reyzin, Lev;Vempala, Santosh S.;Xiao, Ying
- 通讯作者:Xiao, Ying
Testing k-Monotonicity
测试 k-单调性
- DOI:
- 发表时间:2017
- 期刊:
- 影响因子:0
- 作者:Canonne, C;Grigorescu, E.;Guo, S;Kumar, A;Wimmer, K.
- 通讯作者:Wimmer, K.
Communication-Efficient Distributed Learning of Discrete Distributions
- DOI:
- 发表时间:2017
- 期刊:
- 影响因子:0
- 作者:Ilias Diakonikolas;Elena Grigorescu;Jerry Li;Abhiram Natarajan;Krzysztof Onak;Ludwig Schmidt
- 通讯作者:Ilias Diakonikolas;Elena Grigorescu;Jerry Li;Abhiram Natarajan;Krzysztof Onak;Ludwig Schmidt
Maximally recoverable codes: The bounded case
最大可恢复代码:有界情况
- DOI:
- 发表时间:2017
- 期刊:
- 影响因子:0
- 作者:Gandikota, V;Grigorescu, E.;Thomas, C;Zhu, M.
- 通讯作者:Zhu, M.
{{
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 }}
Elena Grigorescu其他文献
Nearly optimal sparse group testing
接近最优的稀疏组测试
- DOI:
10.1109/allerton.2016.7852259 - 发表时间:
2016 - 期刊:
- 影响因子:0
- 作者:
V. Gandikota;Elena Grigorescu;S. Jaggi;Samson Zhou - 通讯作者:
Samson Zhou
Transitive-Closure Spanners
传递闭包扳手
- DOI:
- 发表时间:
2008 - 期刊:
- 影响因子:0
- 作者:
Arnab Bhattacharyya;Elena Grigorescu;Kyomin Jung;Sofya Raskhodnikova;David P. Woodruff - 通讯作者:
David P. Woodruff
An Optimal Lower Bound for Monotonicity Testing over Hypergrids
超网格单调性测试的最佳下界
- DOI:
- 发表时间:
2013 - 期刊:
- 影响因子:1
- 作者:
Elena Grigorescu;Karl Wimmer;Alan Guo;R. Rubinfeld;Uri Stemmer;Janardhan Kulkarni;Benjamin Moseley;Adi Rosen - 通讯作者:
Adi Rosen
A local decision test for sparse polynomials
稀疏多项式的局部决策检验
- DOI:
- 发表时间:
2010 - 期刊:
- 影响因子:0.5
- 作者:
Elena Grigorescu;Kyomin Jung;R. Rubinfeld - 通讯作者:
R. Rubinfeld
A Unified Framework for Testing Linear-Invariant Properties
测试线性不变属性的统一框架
- DOI:
10.1002/rsa.20507 - 发表时间:
2010 - 期刊:
- 影响因子:0
- 作者:
Arnab Bhattacharyya;Elena Grigorescu;A. Shapira - 通讯作者:
A. Shapira
Elena Grigorescu的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Elena Grigorescu', 18)}}的其他基金
Fast and Robust Algorithms with Partial Data Access
具有部分数据访问功能的快速、稳健的算法
- 批准号:
2228814 - 财政年份:2022
- 资助金额:
$ 20万 - 项目类别:
Standard Grant
AF: Small: New Efficient Algorithms for Complex Data
AF:小:复杂数据的新高效算法
- 批准号:
1910411 - 财政年份:2019
- 资助金额:
$ 20万 - 项目类别:
Standard Grant
CIF: Small: Ultra-Efficient Codes for Communication and Verifiable Storage
CIF:小型:用于通信和可验证存储的超高效代码
- 批准号:
1910659 - 财政年份:2019
- 资助金额:
$ 20万 - 项目类别:
Standard Grant
相似海外基金
Quantum Information, Computation, and Complexity
量子信息、计算和复杂性
- 批准号:
RGPIN-2019-03949 - 财政年份:2022
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
A new low-complexity paradigm for analogue computation and hardware learning
用于模拟计算和硬件学习的新的低复杂度范式
- 批准号:
EP/V002759/1 - 财政年份:2021
- 资助金额:
$ 20万 - 项目类别:
Fellowship
Quantum Information, Computation, and Complexity
量子信息、计算和复杂性
- 批准号:
RGPIN-2019-03949 - 财政年份:2021
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
Quantum Information, Computation, and Complexity
量子信息、计算和复杂性
- 批准号:
RGPIN-2019-03949 - 财政年份:2020
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
Quantum computation: through the algorithm and complexity theory lens
量子计算:通过算法和复杂性理论镜头
- 批准号:
DP200100950 - 财政年份:2020
- 资助金额:
$ 20万 - 项目类别:
Discovery Projects
Quantum Information, Computation, and Complexity
量子信息、计算和复杂性
- 批准号:
RGPIN-2019-03949 - 财政年份:2019
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
Algorithms and Complexity of Distributed Computation
分布式计算的算法和复杂性
- 批准号:
RGPIN-2014-04739 - 财政年份:2018
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
Theory of Parameterized Complexity for Local Search-Type Computation
局部搜索型计算的参数化复杂度理论
- 批准号:
17H01698 - 财政年份:2017
- 资助金额:
$ 20万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
Algorithms and Complexity of Distributed Computation
分布式计算的算法和复杂性
- 批准号:
RGPIN-2014-04739 - 财政年份:2017
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
Finite-length analysis with computation complexity
计算复杂度有限长度分析
- 批准号:
17H01280 - 财政年份:2017
- 资助金额:
$ 20万 - 项目类别:
Grant-in-Aid for Scientific Research (A)