AF: Small: The Complexity of Random CSPs

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.