Logic Seminar
Andrew Marks
University of California Berkeley
The recursive compression method for proving incomputability results
Abstract: We discuss a technique called recursive compression for proving incomputability results. The method has developed independently in mathematics and theoretical computer science, and gives a way of showing some set is incomputable by reducing the halting problem to it. Recursive compression was used by Durand, Romashchenko, and Chen in 2008 to give a new proof that the Wang tiling problem is incomputable. In quantum information theory, recursive compression was used by Ji, Natarajan, Vidick, Wright, and Yuen in 2020 to prove the MIP*=RE result that the halting problem is reducible to approximating the quantum value of a nonlocal game. Their result implies a negative answer to the longstanding Connes embedding problem in operator algebras.
We formulate a general recursive compression lemma which abstracts the technique used in these applications. A recursive compression f of a set A ⊂ 2ω is a polytime computable function which takes as input a program e computing a string x in exponential time, and outputs a program f(e) computing a string y in polynomial time so that x ∈ A iff y ∈ A. If A has a recursive compression, and A and its complement are nonempty, then A is incomputable. We also show a converse of the recursive compression lemma: the halting problem is polytime reducible to an r.e. set if and only if there is a recursive compression. Finally, we generalize the recursive compression lemma throughout the arithmetical hierarchy, giving a way to show that a language is Σ0n-hard using recursive compression. This is joint work with Seyed Sajjad Nezhadi and Henry Yuen.
Tuesday April 1, 2025 at 4:00 PM in 636 SEO