课题基金 / 基金详情

AF: Small: The Complexity of Random CSPs

AF: Small: The Complexity of Random CSPs
AF:小:随机 CSP 的复杂性
批准号:
1717606
负责人:
Ryan O'Donnell
金额:
$45.0万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2017
资助国家:
美国
项目状态:
已结题
起止时间:
2017-09-01 至 2020-08-31

项目摘要

项目成果

Ryan O'Donnell的其他基金

相似基金

相关文献

中文摘要
翻译
这个项目关注于理解解决称为“约束满足问题”的非常大的、随机生成的任务的计算困难。这项研究的一个主要动机是密码学。用于传输和计算安全加密数据的密码协议依赖于我们轻松生成随机、难以解决的计算任务的能力。例如,许多密码协议依赖于这样的假设,即如果将两个随机的多位素数相乘,得到的乘积在计算上是困难的。最近的密码学研究已经寻找了容易产生困难问题的新来源,这既是为了增加灵活性,也是为了促进不同类型的加密任务。然而,尽管我们对哪种计算任务在最坏的情况下可能很难解决有相当好的理解,但对于随机选择哪种计算任务预计会很困难,我们几乎不知道。对于随机选择的一类很难解决的问题,“约束满足问题(CSP)”似乎是一个很好的和潜在有用的候选者。这个项目将包括加深我们对随机CSP计算可行性的理解,研究涉及的各种参数(如约束与变量的比率,约束的种类等)。影响他们的舒适度/难度。该项目的另一个方面是对卡内基梅隆大学的计算机科学本科生和研究生进行科学和教育培训,以及广泛传播研究成果。在更技术性的层面上,该项目有几个与随机CSP的计算复杂性有关的问题,以及解决这些问题的算法。PI将考虑约束密度、约束类型、近似/反驳算法的质量和运行时间之间的权衡。特别是,PI将在随机CSP的背景下调查强大的“平方和(SOS)半定规划体系”的能力和局限性。PI还将基于假设的随机CSP的难解性,调查非CSP和学习理论问题的潜在新的困难结果。
英文摘要
This project is concerned with understanding the computational difficulty of solving very large, randomly generated tasks called "constraint satisfaction problems." One major motivation for this study is cryptography. Cryptographic protocols used to transmit and compute on securely encrypted data rely on our ability to easily generate random, hard-to-solve computational tasks. As an example, many cryptographic protocols rely on the assumption that if you multiply together two random prime numbers of many digits, it is computationally difficult to factor the resulting product. Recent research in cryptography has sought new sources of easy-to-generate hard problems, both for added flexibility and for facilitating different types of cryptographic tasks. However, although we have a fairly good understanding of what kinds of computational tasks can be hard to solve in the worst case, we do not know nearly as much about what kinds of computational tasks are expected to be hard when they are chosen at random. The class of "constraint satisfaction problems (CSPs)" seems to be a good and potentially useful candidate for a class of problems that is hard when chosen at random. This project will involve furthering our understanding of the computational feasibility of random CSPs, studying how the various parameters involved (such as the ratio of constraints to variables, the kinds of constraints, etc.) affects their easiness/difficulty. An additional aspect of the project will be scientific and educational training for computer science undergraduate and graduate students at Carnegie Mellon University, as well as wide dissemination of the research produced.At a more technical level, the project has several lines of inquiry related both to the computational complexity of random CSPs, as well as algorithms for their solution. The PI will consider the tradeoffs between constraint density, constraint type, quality of approximation/refutation algorithms, and running time. Particularly, the PI will investigate the power and limitations of the powerful "Sum-of-Squares (SOS) semidefinite programming hierarchy" in the context of random CSPs. The PI will also investigate potential new hardness results for non-CSPs and learning theory problems, based on the assumed intractability of random CSPs.
期刊论文(8)
专著(0)
科研奖励(0)
会议论文
DOI: 10.1145/3357713.3384231
发表时间: 2019-09
期刊: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子: --
作者: [Sidhanth Mohanty;R. O'Donnell;Pedro Paredes]
通讯作者: Sidhanth Mohanty;R. O'Donnell;Pedro Paredes
DOI: 10.1137/1.9781611975482.140
发表时间: 2018-04
期刊: ArXiv
影响因子: --
作者: [Y. Deshpande;A. Montanari;R. O'Donnell;T. Schramm;S. Sen]
通讯作者: Y. Deshpande;A. Montanari;R. O'Donnell;T. Schramm;S. Sen
The SDP Value for Random Two-Eigenvalue CSPs
随机二特征值 CSP 的 SDP 值
DOI: 10.4230/lipics.stacs.2020.50
发表时间: 2020
期刊: Symposium on Theoretical Aspects of Computer Science
影响因子: --
作者: [Mohanty, Sidhanth, O'Donnell, Ryan, Paredes, Pedro]
通讯作者: Paredes, Pedro
A Log-Sobolev Inequality for the Multislice, with Applications
多层切片的 Log-Sobolev 不等式及其应用
DOI: 10.4230/lipics.itcs.2019.34
发表时间: 2019
期刊: Innovations in Theoretical Computer Science
影响因子: --
作者: [Filmus, Yuval, O'Donnell, Ryan, Wu, Xinyu]
通讯作者: Wu, Xinyu
8
    FET: Small: Foundations of Quantum State Learning and Testing
    • 批准号:
      1909310
    • 项目类别:
      Standard Grant
    • 资助金额:
      $47.0万
    • 财政年份:
      2019
    • 负责人:
      Ryan O'Donnell
    • 依托单位:
    AF: Small: Harmonic Analysis for Quantum Complexity
    • 批准号:
      1618679
    • 项目类别:
      Standard Grant
    • 资助金额:
      $45.0万
    • 财政年份:
      2016
    • 负责人:
      Ryan O'Donnell
    • 依托单位:
    AF: Small: CSPs --- Approximability versus Time
    • 批准号:
      1319743
    • 项目类别:
      Standard Grant
    • 资助金额:
      $42.62万
    • 财政年份:
      2013
    • 负责人:
      Ryan O'Donnell
    • 依托单位:
    AF: Small: Analysis of Boolean Functions
    • 批准号:
      1116594
    • 项目类别:
      Standard Grant
    • 资助金额:
      $47.64万
    • 财政年份:
      2011
    • 负责人:
      Ryan O'Donnell
    • 依托单位:
    国内基金
    海外基金
    昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
    • 批准号:
    • 项目类别:
      省市级项目
    • 资助金额:
      --
    • 批准年份:
      2024
    • 负责人:
    • 依托单位:
    tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
    • 批准号:
    • 项目类别:
      省市级项目
    • 资助金额:
      10.0万元
    • 批准年份:
      2022
    • 负责人:
      张祥忠
    • 依托单位:
    Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
    Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
    • 批准号:
      31972324
    • 项目类别:
      面上项目
    • 资助金额:
      58.0万元
    • 批准年份:
      2019
    • 负责人:
      高学文
    • 依托单位: