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 电路伪随机发生器
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 的严格表征
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover
顶点覆盖Lovasz-Schrijver SDP松弛的线性圆下界

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 RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.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
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了