Nathanaël Fijalkow: Machine-learning guided program synthesis

Writing software is tedious, error-prone, and accessible only to a small share of the population – yet coding grows increasingly important as the digital world plays larger and larger roles in peoples’ lives. Program synthesis seeks to make programming more reliable and accessible by developing methods for automatically constructing programs from specifications.

In this talk, I will discuss a very successful line of attack for program synthesis, combining two paradigms: symbolic algorithms for logical reasoning, and machine learning or statistical techniques for guiding the search towards a solution program. This way we get the best of
both worlds: the mathematical guarantees, verifiability, and explainability of symbolic methods, together with the empirical success of machine learning and statistical approaches.

Based on some recent work (to appear in AAAI’22, see below) we will explore an unexpected connection between program synthesis, airport screening, and DNA sequencing: they are all about finding a needle in a (probabilistic) haystack!