Prof. Antonina Kolokolova | Representation-independent lower bounds

Item: Prof. Antonina Kolokolova | Representation-independent lower bounds
Rating: 4
Author: PostSingularity Institute

by Antonina Kolokolova · View the channel on PSI

Formal & Physical Sciences Computing & Cybersecurity UYComputer science UYAMathematical theory of computation

🎙 Antonina Kolokolova 👥 8K 📅 October 20, 2026 ⏱ 43 min 👁 3 📄 original study 🧭 2026-10-20

Available in: English (current) Français

Keywords

representationNP verifierproof systempigeonhole principlethree-coloring

Summary

This talk by Professor Antonina Kolokolova at the Isaac Newton Institute addresses the question of how the choice of representation of a computational problem affects the complexity of proving its unsatisfiability in given proof systems. The speaker proposes to equate a problem with an NP verifier (a black-box predicate on input-output pairs), and defines a representation as any syntactic object from a fixed class (circuits, formulas, inequality systems) that agrees with the verifier on every (x,y) pair. The complexity measure for a representation combines the description size and the worst-case proof length in a proof system S for unsatisfiable instances. The talk reviews earlier work on knowledge compilation, shows that changing the underlying language can dramatically affect proof complexity (e.g., pigeonhole principle in cutting planes), and presents new results: representation-dependent lower bounds can be transformed into representation-independent ones for problems with certain model-theoretic structure, such as three-coloring. The talk also discusses connections to complexity conjectures and oracle separations, and outlines a research agenda for determining when representation can help or cannot help. The presentation emphasizes the conceptual distinction between encoding a problem and choosing a verifier, and argues that the choice of representation is a crucial yet often overlooked parameter in proof complexity.

203 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk presents a clear conceptual contribution: formalizing the intuitive notion that the representation of a problem matters for proof complexity. The argumentation is solid, transitioning from motivating examples (pigeonhole principle, matching) to a rigorous definition and then to structural results. The speaker acknowledges prior work (knowledge compilation) and open questions. The logical flow is coherent, and the proposed framework has the potential to unify encoding-dependent lower bounds.

Scientific Rigor, Source Quality, Title Accuracy

The title accurately reflects the content: the talk focuses on lower bounds that are independent of representation for certain problems. The speaker cites specific works, including the knowledge compilation map by Darwiche and Marquis, and the work of Robert and others, though no explicit URLs are provided within the talk itself. The institutional source (Isaac Newton Institute) lends credibility. The presentation is rigorous, with definitions and proofs sketched, and no obvious unsupported claims. The content is highly specialized but coherent.

163 words

Title / Content Match

The title accurately represents the content: the talk focuses on lower bounds that are independent of how the problem is represented, a precise and appropriate description.

Quality & Reliability

8/10

The talk is a rigorous research presentation at a leading mathematics institute, with clear definitions and logical progression. The speaker is a recognized researcher in proof complexity, and the content is supported by examples and prior literature, though no detailed proof is given for all claims.

Key Moments

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

Cited Sources

Isaac Newton Institute for Mathematical Sciences — Host institution for the seminar, providing venue and context.
Seminar page for this talk — Official event page with details about the talk and the program.

Concurring Sources

Proof complexity on Wikipedia — General background on the field of proof complexity, corroborating the talk's subject.
Knowledge compilation on Wikipedia — Related area of research that studies how representation choices affect reasoning efficiency.

Contribution & Novelties

The main novelty is the introduction of a formal framework to study representation-dependent vs representation-independent lower bounds in proof complexity, and the demonstration that certain problems (three-coloring) have representation-independent lower bounds based on logical structure. This goes beyond typical knowledge compilation results by tying proof system parameters to the representation class. The talk also provides oracle separations highlighting the limits of such results.

Pour aller plus loin :

Proof complexity — Foundational background on measuring the difficulty of proving tautologies.
Knowledge compilation — Related field studying representation choices for efficient reasoning.
Constraint satisfaction problem — The dichotomy results and links to model theory, relevant to the three-coloring lower bound.
Pigeonhole principle — A central example in the talk, showing how different encodings affect proof complexity.

125 words

Radar Profile

The radar profile shows high technical depth and good reliability, with slightly lower quantity of information due to the focus on a specific research contribution rather than a broad survey.

Reliability 8/10