Abstract Synthesis16 Des 2025

Grammar Filtering For Syntax-Guided Synthesis - Mark Santolucito

Leading program synthesis researcher Mark Santolucito (Assistant Professor, Barnard College, Columbia University) discusses his paper "Grammar Filtering for Syntax-Guided Synthesis".

This conversation explores how machine learning can be used to shrink the search space of syntax-guided synthesis (SyGuS) problems, dramatically speeding up synthesis without sacrificing the strong correctness guarantees of formal methods.

Mark shares the unexpected origin story of the paper, which began at a hackathon in Bermuda, explains the core ideas behind grammar filtering, and reflects on the broader role of neurosymbolic approaches in modern program synthesis.

In This Episode -

• What program synthesis is and why it matters

• Intro to syntax-guided synthesis (SyGuS)

• Why grammar size dominates synthesis runtime

• How machine learning can safely prune grammars before synthesis

• Predicting both criticality and runtime impact of grammar terminals

• Combining neural guidance with SMT-based synthesis solvers

• Results from SyGuS benchmarks (including ~50% runtime improvements)

• Reflections on the future of neurosymbolic program synthesis

About the Paper -

"Grammar Filtering for Syntax-Guided Synthesis"

Kairo Morton, William Hallahan, Elven Shum, Ruzica Piskac, Mark Santolucito

Published at AAAI 2020

The paper introduces a machine-learning–based technique for identifying and removing low-utility grammar terminals in SyGuS problems, significantly accelerating synthesis while maintaining correctness guarantees.

https://arxiv.org/abs/2002.02884

About the Guest -

Mark Santolucito is an Assistant Professor of Computer Science at Barnard College, Columbia University, where he develops novel program synthesis and analysis techniques to help programmers interact with code more effectively with a focus on Temporal Logic.

https://www.marksantolucito.com

Credits -

• Host & Music: Bryan Landers, Technical Staff, Ndea

• Editor: Alejandro Ramirez

• https://x.com/ndea

• https://ndea.com

• https://x.com/bryanlanders

Denne episoden er hentet fra en åpen RSS-feed og er ikke publisert av Podme. Den kan derfor inneholde annonser.

Episoder(16)

Why Creativity Cannot Be Interpolated - MLST

Jeremy Budd, Assistant Professor at the University of Birmingham, and Tim Scarfe, CEO of Machine Learning Street Talk, discuss the paper “Why Creativity Cannot Be Interpolated”, which argues that genu...

22 Jul 1h 3min

Constrained Adaptive Rejection Sampling - Loris D’Antoni

Loris D’Antoni, Professor of Computer Science and Engineering at UC San Diego, discusses his paper “Constrained Adaptive Rejection Sampling,” which introduces a constrained decoding algorithm that pre...

1 Jul 49min

Inventing Inductive Logic Programming - Stephen Muggleton

Stephen Muggleton, Emeritus Professor at Imperial College London, discusses his paper “Inductive Logic Programming”, which introduced and named the field. The paper presents a framework that combines ...

18 Jun 57min

Recursive Program Synthesis - Aws Albarghouthi

Aws Albarghouthi, Associate Professor of Computer Science at the University of Wisconsin-Madison, discusses his paper “Recursive Program Synthesis”, which introduced Escher, an inductive synthesis alg...

27 Mai 55min

DreamCoder's Wake-Sleep Library Learning - Kevin Ellis

Kevin Ellis, Assistant Professor at Cornell University, discusses his influential paper “DreamCoder,” which presents a system that jointly learns reusable program abstractions and a neural search stra...

7 Apr 47min

Semantic Programming by Example with Pre-trained Models - Gust Verbruggen

Gust Verbruggen, Senior AI researcher and member of the PROSE team at Microsoft, discusses his paper "Semantic Programming by Example with Pre-trained Models," which introduces a framework for integra...

3 Mar 1h 15min

February 2026 Podcast Recap

Program synthesis is the problem of automatically generating code that satisfies a specification. The real challenge isn’t searching faster, it’s making the right parts of the search space searchable ...

9 Feb 6min

Relational Decomposition for Program Synthesis - Céline Hocquette

The way a problem is represented can determine whether it is solvable at all.Céline Hocquette, AI researcher at Ndea and former postdoctoral researcher at the University of Oxford, discusses her paper...

2 Feb 47min