Prof. Valentine Kabanets | Synergies between proof complexity and cryptography

Prof. Valentine Kabanets | Synergies between proof complexity and cryptography

Title history
  • Prof. Valentine Kabanets | Synergies between proof complexity and cryptography — observed on 20261025-1505 UTC (YouTube)

by Valentine Kabanets · View the channel on PSI

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Valentine Kabanets 👥 8K 📅 October 23, 2026 ⏱ 45 min 👁 178 📄 original study 🧭 2026-10-25
Available in: English (current) Français

Keywords

proof complexitycryptographyMCSPoptimal proof systemsindistinguishability obfuscation

Summary

The talk by Professor Valentine Kabanets, jointly with Haley Goldberg and Mandar Juvekar, explores deep connections between proof complexity, meta-complexity, and cryptography. It focuses on the minimum circuit size problem (MCSP) and introduces a variant called implicit MCSP, where the truth table is represented by a sampling circuit. The main result shows that under two plausible assumptions—the non-existence of optimal proof systems (a proof complexity assumption) and the existence of indistinguishability obfuscation (a cryptographic assumption)—the implicit MCSP is NP-hard under randomized polynomial-time reductions. The proof strategy relies on an ’enhancing reductions’ lemma, which forces any given polynomial-time reduction from SAT to satisfy a desired Pi-1 property on all outputs, not just on satisfiable formulas. This is achieved by using hard tautologies generated from the no-optimal-proof-systems assumption. The talk also reviews background on proof systems, the Cook-Reckhow theorem, and the Krajicek-Pudlak equivalence, and contrasts the result with prior work by Hirahara and Elango. The framework highlights a constructive separation between NP and co-NP and demonstrates how cryptographic constructions like obfuscation can be combined with proof complexity to yield new complexity-theoretic conclusions.

180 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk delivers high scientific value by establishing a novel link between proof complexity and cryptography, specifically showing how a proof-complexity assumption (no optimal proof systems) can be leveraged to strengthen cryptographic reductions. The argumentation is rigorous: the enhancing reductions lemma is proved in detail, with careful attention to soundness and completeness of the constructed proof system. The speaker addresses audience questions, clarifying subtle points such as the promise nature of the sampling circuit and the role of infinite-often vs. almost-always versions of the assumptions. The presentation builds on known results (Cook-Reckhow, Krajicek-Pudlak, Applebaum-Barak-Xiao) and situates the new contribution relative to prior work. The technical depth is substantial, and the logical flow from definitions to the main theorem is coherent and well-motivated.

Scientific Rigor, Source Quality, Title Accuracy

The talk is given at the Isaac Newton Institute, a world-renowned research center, and is part of a formal workshop on logical foundations of complexity theory. The speaker cites foundational works in the field, and the presentation is consistent with published literature. The title accurately matches the content: the talk systematically explores synergies between proof complexity and cryptography. No commercial or advertising content is present. The sources mentioned (such as Cook-Reckhow, Krajicek-Pudlak, Applebaum-Barak-Xiao) are appropriate and credible. The talk does not overclaim; it clearly states assumptions and the conditional nature of the results. Overall, a model of rigorous scientific communication.

237 words

Title / Content Match

The title accurately reflects the content: the talk focuses on formal connections between proof complexity and cryptography, particularly through the minimum circuit size problem and obfuscation.

Quality & Reliability

9/10

High-quality research talk from a leading mathematical sciences institute, presenting rigorous formal results with clear definitions and assumptions. The technical content is consistent with state-of-the-art complexity theory and proof complexity.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Contribution & Novelties

The talk contributes a new reduction framework (enhancing reductions) that can enforce Pi-1 properties on outputs of a reduction, and applies it to show NP-hardness of implicit MCSP under the assumptions of no optimal proof systems and indistinguishability obfuscation. This is an original combination that strengthens the known connections between proof complexity and cryptography. The result uses randomized polynomial-time many-one reductions, whereas prior work by Hirahara and Elango relied on stronger assumptions and quasi-polynomial Turing reductions.

Pour aller plus loin :

  • Proof complexity — Overview of the field; relevant for understanding proof systems and lower bounds.
  • Indistinguishability obfuscation — Cryptographic primitive central to the assumptions used; explains its definition and significance.
  • Circuit minimization problem (MCSP) — Classical problem; foundational to meta-complexity and the talk’s main topic.

126 words

Radar Profile

The radar profile is nearly square, reflecting uniformly high scores across quantity, quality, technical level, and reliability. The talk is dense, rigorous, and technically demanding, with no notable weakness; it is typical of a specialized research seminar.

Reliability 9/10