École d'été | 10 juin 2026 : Boolean Is Not Too Restrictive par Pouya Shati

Value of the Information & Strength of the Argument

The talk provides valuable insights into the application of MaxSAT to machine learning problems, specifically decision tree learning. The argumentation is solid, building on the premise that Boolean encodings can be effective despite initial appearances. Shati systematically presents components of his research, explaining the rationale behind each encoding choice. He convincingly demonstrates that shadow encoding avoids the need for explicit binarization, and that proxy optimization can handle complex objectives. The discussion of user constraints and performance techniques adds practical value. However, the talk is a high-level overview, and some claims would benefit from more detailed evidence or examples, which are deferred to the thesis.

Scientific Rigor, Source Quality, Title Accuracy

The talk is based on the speaker’s PhD thesis, which is a credible academic source. The presentation is well-structured and technically rigorous, with clear explanations of the encoding techniques. The title accurately reflects the content, as the speaker argues that Boolean encodings are not too restrictive for learning optimal decision trees. The talk does not cite external sources explicitly, but the thesis likely contains references to relevant literature. The content is presented in a logical manner, and the speaker acknowledges the limitations of the presentation, directing the audience to the thesis for more details.

The title accurately reflects the content: the speaker argues that Boolean encodings are not too restrictive for learning optimal decision trees, and demonstrates this through MaxSAT encodings.

8/10

The talk is based on the speaker's PhD thesis, which is a rigorous academic work. The content is well-structured and technically sound, with clear explanations of the encoding techniques. However, the presentation is a summary and lacks detailed proofs, which are deferred to the thesis.

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

• 00:00Introduction and motivation: the speaker introduces the topic and the central claim that Boolean encodings are not too restrictive.
• 03:00Background on SAT, MaxSAT, and decision trees, including the interpretability and constraint satisfaction benefits.
• 07:00Structural encodings: how to encode decision trees into Boolean logic, introducing the concept of shadow encoding for numerical thresholds.
• 10:00Objectives: max accuracy, minimum depth, and clustering objectives (maximum diameter and minimum split) with proxy optimization.
• 13:00User constraints: must-links and cannot-links in clustering, and their encoding.
• 15:00Performance enhancements: approximation techniques, smart pairs preprocessing, and symmetry breaking.
• 18:00Advanced topics and conclusion: the speaker briefly mentions advanced parts and encourages the audience to read the thesis.

• PhD thesis of Pouya Shati — The talk is primarily based on the speaker's PhD thesis, which contains proofs, formulations, and references to relevant papers.

• MaxSAT — The talk builds on MaxSAT solvers, which are known to be efficient for combinatorial optimization problems.
• Decision tree learning — The talk focuses on learning decision trees, a well-studied area in machine learning.