AF: Small: Spectral and SDP Techniques: Average-Case Analysis and Subexponential Algorithms
AF:小:谱和 SDP 技术:平均情况分析和次指数算法
基本信息
- 批准号:1815434
- 负责人:
- 金额:$ 50万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2018
- 资助国家:美国
- 起止时间:2018-08-01 至 2021-07-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This project involves the design and analysis of algorithms for combinatorial problems using techniques from linear algebra and convex optimization. The project bridges pure mathematics and data science, allowing new applications of mathematical ideas to the practice of computing, and from the activities on dissemination, exposition, outreach and mentoring. The project will create open-access lecture notes, surveys and blog posts, making highly technical results accessible to a broader audience. This project will play a key role in the training of graduate students, including two students belonging to underrepresented groups in computer science, and in the design of a new graduate course.The project involves novel approaches to fundamental problems, such as certifying the unsatisfiability of random constraint satisfaction problems, efficiently certifying properties of sparse random graphs and sparse random matrices, understanding the power of sub-exponential size relaxations in the sum-of-squares hierarchies, developing new construction of graph sparsifiers and finding new ways to analyze certain probabilistic distributed processes. Some of the problems in the scope of this project are not believed to admit algorithms that perform correctly and efficiently on all inputs. For this reason, the project will focus on: (a) algorithms whose running time scale "sub-exponentially" and that outperform brute-force combinatorial search, and (b) algorithms that may perform poorly on a few inputs but that perform well on average on random inputs. The second goal depends on how the inputs are distributed, and a key focus of this project is to generalize past results that apply to certain specific distributions to broader classes of distributions.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.
这个项目涉及使用线性代数和凸优化技术来设计和分析组合问题的算法。该项目将纯数学和数据科学联系起来,允许将数学思想应用于计算实践,并从传播,展览,推广和指导活动中获得新的应用。该项目将创建开放获取的讲义、调查和博客文章,使更广泛的受众能够获得高度技术性的成果。该项目将在培养研究生方面发挥关键作用,包括两名属于计算机科学领域代表性不足的学生,以及设计新的研究生课程。该项目涉及基础问题的新方法,如证明随机约束满足问题的不可满足性,有效证明稀疏随机图和稀疏随机矩阵的性质,理解平方和层次结构中的次指数大小松弛的能力,开发新的图形稀疏化结构,并找到新的方法来分析某些概率分布过程。在这个项目的范围内的一些问题被认为不承认算法,正确和有效地执行所有输入。出于这个原因,该项目将集中在:(a)算法的运行时间规模“次指数”,并优于蛮力组合搜索,和(B)算法,可能表现不佳的几个输入,但表现良好的平均随机输入。第二个目标取决于输入是如何分布的,这个项目的一个重点是将过去适用于某些特定分布的结果推广到更广泛的分布类别。这个奖项反映了NSF的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(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 }}
Luca Trevisan其他文献
Lecture Notes on Computational Complexity
- DOI:
- 发表时间:
2004 - 期刊:
- 影响因子:0
- 作者:
Luca Trevisan - 通讯作者:
Luca Trevisan
Improved Pseudorandom Generators for Depth 2 Circuits
改进的深度 2 电路伪随机发生器
- DOI:
- 发表时间:
2010 - 期刊:
- 影响因子:0
- 作者:
Anindya De;Omid Etesami;Luca Trevisan;Madhur Tulsiani - 通讯作者:
Madhur Tulsiani
The Minority Dynamics and the Power of Synchronicity
少数派动态和同步性的力量
- DOI:
10.48550/arxiv.2310.13558 - 发表时间:
2023 - 期刊:
- 影响因子:0
- 作者:
L. Becchetti;A. Clementi;F. Pasquale;Luca Trevisan;Robin Vacus;Isabella Ziccardi - 通讯作者:
Isabella Ziccardi
A tight characterization of NP with 3 query PCPs
具有 3 个查询 PCP 的 NP 的严格表征
- DOI:
10.1109/sfcs.1998.743424 - 发表时间:
1998 - 期刊:
- 影响因子:0
- 作者:
V. Guruswami;Daniel Lewin;Madhu Sudan;Luca Trevisan - 通讯作者:
Luca Trevisan
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover
顶点覆盖Lovasz-Schrijver SDP松弛的线性圆下界
- DOI:
- 发表时间:
2007 - 期刊:
- 影响因子:0
- 作者:
Grant Schoenebeck;Luca Trevisan;Madhur Tulsiani - 通讯作者:
Madhur Tulsiani
Luca Trevisan的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Luca Trevisan', 18)}}的其他基金
EAGER: New Graph and CSP Algorithms Based on Spectral and SDP Techniques
EAGER:基于谱和 SDP 技术的新图和 CSP 算法
- 批准号:
1655215 - 财政年份:2016
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Graph Partitioning and Spectral Methods
AF:小:图划分和谱方法
- 批准号:
1540685 - 财政年份:2014
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Graph Partitioning and Spectral Methods
AF:小:图划分和谱方法
- 批准号:
1216642 - 财政年份:2012
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Unconditional Lower Bounds in Approximability and Cryptography
AF:小:近似性和密码学的无条件下界
- 批准号:
1161812 - 财政年份:2011
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
AF: Small: Unconditional Lower Bounds in Approximability and Cryptography
AF:小:近似性和密码学的无条件下界
- 批准号:
1017403 - 财政年份:2010
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
Applications of Artihmetic Combinatorics in Computer Science
算术组合在计算机科学中的应用
- 批准号:
0729137 - 财政年份:2007
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Average-Case Complexity, Derandomization and Inapproximability
平均情况复杂性、去随机化和不可近似性
- 批准号:
0515231 - 财政年份:2005
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
CAREER: Randomized Computations and Probabilistically Checkable Proofs
职业:随机计算和概率可检查证明
- 批准号:
0406156 - 财政年份:2003
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
CAREER: Randomized Computations and Probabilistically Checkable Proofs
职业:随机计算和概率可检查证明
- 批准号:
9984703 - 财政年份:2000
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
SWIFT: SMALL: xNGRAN Navigating Spectral Utilization, LTE/WiFi Coexistence, and Cost Tradeoffs in Next Gen Radio Access Networks through Cross-Layer Design
SWIFT:小型:xNGRAN 通过跨层设计实现下一代无线接入网络中的频谱利用、LTE/WiFi 共存和成本权衡
- 批准号:
2030101 - 财政年份:2020
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
CNS Core: Small: Collaborative Research: Attaining the New Frontier of Spectral Efficiency with Tradeoffs in Computation Through Cloud Radio Access Networks
CNS 核心:小型:协作研究:通过云无线接入网络权衡计算实现频谱效率的新前沿
- 批准号:
1909186 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
SHF: Small: Spectral Reduction of Large Graphs and Circuit Networks
SHF:小:大型图和电路网络的频谱缩减
- 批准号:
2021309 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
CNS Core: Small: Collaborative Research: Attaining the New Frontier of Spectral Efficiency with Tradeoffs in Computation Through Cloud Radio Access Networks
CNS 核心:小型:协作研究:通过云无线接入网络权衡计算实现频谱效率的新前沿
- 批准号:
1910594 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
SHF: Small: Scalable Spectral Sparsification of Graph Laplacians and Integrated Circuits
SHF:小:图拉普拉斯和集成电路的可扩展谱稀疏化
- 批准号:
2011412 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Explaining the dark matter small-scale crisis with spectral distortions
用光谱扭曲解释暗物质小规模危机
- 批准号:
FT180100031 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
ARC Future Fellowships
SHF: Small: Spectral Reduction of Large Graphs and Circuit Networks
SHF:小:大型图和电路网络的频谱缩减
- 批准号:
1909105 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
CHS: Small: Collaborative Research: 3D Printing for High Fidelity Image Reproduction Capturing Texture, Spectral Color, Gloss, and Translucency
CHS:小型:协作研究:用于高保真图像再现的 3D 打印捕获纹理、光谱颜色、光泽度和半透明度
- 批准号:
1815585 - 财政年份:2018
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
NeTS: Small: Modally-multiplexed Spatio-Spectral DispersionCompensation and Routing for Photonic Networks
NeTS:小型:光子网络的模态复用空间光谱色散补偿和路由
- 批准号:
1817174 - 财政年份:2018
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
CHS: Small: Collaborative Research: 3D Printing for High Fidelity Image Reproduction Capturing Texture, Spectral Color, Gloss, and Translucency
CHS:小型:协作研究:用于高保真图像再现的 3D 打印捕获纹理、光谱颜色、光泽度和半透明度
- 批准号:
1815070 - 财政年份:2018
- 资助金额:
$ 50万 - 项目类别:
Standard Grant