AF: Small: The Complexity of Random CSPs

AF：小：随机 CSP 的复杂性

• 批准号: 1717606
• 负责人: Ryan O'Donnell
• 金额: $ 45万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1717606&HistoricalAwards=false
• 关键词: AF; Small; Complexity; Random; CSPs

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.

这个项目是关于理解解决非常大的，随机生成的任务的计算难度，称为“约束满足问题”。“这项研究的一个主要动机是密码学。 用于传输和计算安全加密数据的加密协议依赖于我们轻松生成随机、难以解决的计算任务的能力。 例如，许多密码协议都依赖于这样的假设：如果你将两个随机的多位素数相乘，那么在计算上很难对所得乘积进行因子分解。 密码学的最新研究已经寻找了易于生成的难题的新来源，以增加灵活性并促进不同类型的密码学任务。 然而，尽管我们对什么样的计算任务在最坏的情况下很难解决有相当好的理解，但我们对随机选择的计算任务的难度却知之甚少。 一类“约束满足问题（CSP）”似乎是一个很好的和潜在的有用的候选人一类的问题，是很难随机选择。 这个项目将涉及进一步了解随机CSP的计算可行性，研究如何涉及的各种参数（如约束变量的比例，约束的种类等）。影响其难易程度。 该项目的另一个方面将是对卡内基梅隆大学计算机科学本科生和研究生的科学和教育培训，以及广泛传播所产生的研究成果。在更技术的层面上，该项目有几条与随机CSP的计算复杂性以及求解算法相关的调查路线。 PI将考虑约束密度、约束类型、近似/反驳算法的质量和运行时间之间的权衡。 特别是，PI将调查的权力和限制的强大的“平方和（SOS）半定规划层次”的背景下，随机CSP。 PI还将根据随机CSP的假设棘手性，调查非CSP和学习理论问题的潜在新硬度结果。

项目成果

Explicit near-Ramanujan graphs of every degree

• 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

The threshold for SDP-refutation of random regular NAE-3SAT

• DOI: 10.1137/1.9781611975482.140
• 发表时间: 2018-04
• 期刊: ArXiv
• 作者: 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

Waring Rank, Parameterized and Exact Algorithms

Waring Rank、参数化和精确算法

• DOI: 10.1109/focs.2019.00053
• 发表时间: 2019
• 期刊: IEEE Foundations of Computer Science
• 作者: Pratt, Kevin