This National Science Foundation Project Grant of $600,000 supports research on the complexity of satisfiable constraint satisfaction problems at the Massachusetts Institute of Technology from January 2023 through December 2025. Funded through the Computer and Information Science and Engineering program (CFDA 47.070), this award will advance the development of probabilistically checkable proofs theory through focused study of satisfiable constraint satisfaction problems, a fundamental class of problems in complexity theory. Key products include new tools and mathematical connections to analyze the best approximation algorithm for constraint satisfaction problems given a solution exists. Broader impacts incorporate course development, mentoring, and workshop organization. Outcomes from this research have the potential to impact non-centralized systems such as blockchains and cryptocurrencies.
Generated 1/6/24, 4:30 PM