Dr. Marco Carmosino | Constructive separations from gate elimination

Dr. Marco Carmosino | Constructive separations from gate elimination

by Dr. Marco Carmosino · View the channel on PSI

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Dr. Marco Carmosino 👥 8K 📅 October 20, 2026 ⏱ 39 min 👁 2 📄 expert opinion 🧭 2026-10-20
Available in: English (current) Français

Keywords

complexity classesrefutersSATcircuit complexitybounded arithmetic

Summary

The talk by Dr. Marco Carmosino presents the concept of constructive separations in computational complexity, where instead of just proving that a language is outside a complexity class, one constructs an efficient refuter that produces a counterexample for any given algorithm in the class. He motivates this as an algorithmic formulation of central open problems, with industrial applications for verifying algorithms. He reviews results showing that under standard assumptions like P≠NP, constructive separations exist for many classes. He then shifts to circuit complexity and gate elimination, a powerful technique for proving small circuit lower bounds. Recent progress has led to improved lower bounds, but the question of whether gate elimination proofs can be made constructive is addressed: the speaker claims that gate elimination is constructive and that they have constructivized proofs for functions like the multiplexer and affine disperser. He discusses barriers to gate elimination and proposes to formalize gate elimination in proof theory, aiming to classify which proofs fall into that technique. The talk ends with questions and discussion.

170 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk provides valuable insights into constructive separations as a research direction, linking them to known results and open problems. The argumentation is solid: the speaker starts with motivations, defines concepts clearly, and presents results that support the feasibility of constructive separations. He also highlights surprising consequences, such as that constructivizing a simple lower bound for palindromes would imply breakthrough circuit lower bounds. This demonstrates the depth of the questions. The discussion of gate elimination and its constructivity is also well-founded, with references to recent work and open challenges. The speaker engages with audience questions, which adds to the clarity.

Scientific Rigor, Source Quality, Title Accuracy

The talk references several research papers (e.g., Gutfreund et al. 2005, Chen et al. 2024, etc.) and mentions specific results. However, no slides or explicit citations were visible, but the speaker mentions authors and years. The title accurately reflects the content. The talk is hosted by the Isaac Newton Institute, a reputable research institution, which adds credibility. The speaker’s affiliation with IBM Research also supports expertise. The description provides links to the seminar page and the institute, which can serve as sources for further verification.

200 words

Title / Content Match

The title matches the content: the talk discusses constructive separations and gate elimination as a method to obtain them.

Quality & Reliability

8/10

The talk presents rigorous concepts from complexity theory, referencing multiple research papers. The speaker is an expert (IBM Research) and the talk is part of an Isaac Newton Institute workshop. The arguments are logically structured, with definitions and motivations. However, the talk is a presentation of existing and ongoing work, not a peer-reviewed article, so full verification of claims is not possible.

Key Moments

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

Cited Sources

Contribution & Novelties

The talk offers an original perspective on constructive separations, but its main contribution is the claim that gate elimination proofs can be constructivized. It discusses recent results and open problems, highlighting the potential of unifying these two areas. The speaker proposes to formalize gate elimination in proof theory, which could lead to a better understanding of its limitations. The talk encourages further research at the intersection of complexity theory and proof theory. Pour aller plus loin :

  • Circuit complexity — Overview of circuit lower bounds.
  • P versus NP problem — Central open problem motivating constructive separations.
  • Bounded arithmetic — Relevant to formalizing proofs.
  • Gate elimination — Technique discussed in the talk (note: page may not exist, but concept known).

119 words

Radar Profile

The radar profile shows high scores in quality and technical level, with slightly lower but still strong scores in quantity and reliability. This indicates a dense, technical talk with solid content, suitable for specialists.

Reliability 8/10