Seminar Program Synthesis

Seminar in Theoretical CS, Winter 2023/24


  • 17.05.2023: We are online!


Dates & Deadlines

Oct 11, 2023; 16:30Kick-off meeting (CS Department, building E1, 2nd floor, room 4201b)
Oct 16, 2023Topic preferences due
Nov 20, 2023Detailed outline due
Dec 18, 2023Full report due
Jan 15, 2024Presentation slides due
Jan 22, 2024 (afternoon)Seminar talks

Note that the full versions of your report and your slides should be your final submissionand the camera-ready versions should differ only with regard to minor remarks, comments, and corrections by your supervisor. Please feel free, however, to talk to your supervisor about submitting preliminary versions before the due dates.


Program synthesis refers to the task of automatically finding a program in the underlying programming language that satisfies the user intent expressed in the form of some specification. This task is typically solved by performing some kind of search over the space of programs to generate a program that is consistent with the specification. The latter can be given in various forms, such as input/output examples, natural language, program templates, or logical assertions. A comprehensive overview to relevant approaches and techniques is provided in the survey report Program Synthesis by Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh.


Basic knowledge in Formal Languages and Automata Theory and Mathematical Logic is expected. For some of the topics, experience with Formal Semantics of Programming Languages and Probabilistic Programming is helpful.

Schedule of Talks

TimeMonday, January 22
14:00 – 15:30Jakob van Sprang, Rico Stanosek, Krzysztof Kostrzewa
15:45 – 16:45Yussur Mustafa Oraji, Andreas Holzinger
17:00 – 18:00Dominik Geißler, Markus Rümenapp


Syntax-Guided Synthesis
1R. Alur, R. Bodik, G. Juniwal, M.M.K. Martin, M. Raghothaman, S.A. Seshia, R. Singh, A. Solar-Lezama, E. Torlak, A. Udupa: Syntax-guided synthesis. FMCAD 2013Yussur Mustafa OrajiLutz Klinkenberg
2A. Solar-Lezama: Program Sketching. STTT 15, 2013Dominik GeißlerTobias Winkler
3A.V. Nori, S. Ozair, S.K. Rajamani, D. Vijaykeerthy: Efficient synthesis of probabilistic programs. ACM SIGPLAN Notices 50, 2015
Synthesis by Deductive Search
4S. Srivastava, S. Gulwani, J.S. Foster: From program verification to program synthesis. POPL 2010
5N. Polikarpova, I. Sergey: Structuring the Synthesis of Heap-Manipulating Programs. POPL 2019Jakob van SprangThomas Noll
Synthesis from Input/Output Examples
6J. Hamza, V. Kuncak: Minimal Synthesis of String To String Functions From Examples. VMCAI 2019Markus RümenappTobias Winkler
7S. Chasins, P.M. Phothilimthana: Data-Driven Synthesis of Full Probabilistic Programs. CAV 2017
8K. Shi, J. Steinhardt, P. Liang: FrAngel: component-based synthesis with control structures. POPL 2019Rico StanosekThomas Noll
Synthesis using Large Language Models
9J. Austin, A. Odena, M. Nye, M. Bosma, H. Michalewski, D. Dohan, E. Jiang, C. Cai, M. Terry, Q. Le, C. Sutton: Program Synthesis with Large Language Models. arXiv 2021Andreas HolzingerLutz Klinkenberg
10E. Nijkamp, B. Pang, H. Hayashi, L. Tu, H. Wang, Y. Zhou, S. Savarese, C. Xiong: CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis. arXiv 2022
Synthesis by Reinforcement Learning
11D.J. Mankowitz et al.: Faster sorting algorithms discovered using deep reinforcement learning. Nature 618, 2023Krzysztof KostrzewaThomas Noll


Registration to the seminar is handled via the SuPra system.

Grading Scheme

You can access the grading scheme here:

Additional Material


Thomas Noll