Seminar in Theoretical CS, Winter 2023/24
News
- 17.05.2023: We are online!
Introduction
Dates & Deadlines
| Oct 11, 2023; 16:30 | Kick-off meeting (CS Department, building E1, 2nd floor, room 4201b) |
| Oct 16, 2023 | Topic preferences due |
| Nov 20, 2023 | Detailed outline due |
| Dec 18, 2023 | Full report due |
| Jan 15, 2024 | Presentation slides due |
| Jan 22-23, 2024 (?) | 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.
Overview
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.
Prerequisites
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.
Topics
| No. | Topic | Student | Supervisor |
|---|---|---|---|
| Syntax-Guided Synthesis | |||
| 1 | R. 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 2013 | Yussur Mustafa Oraji | Lutz Klinkenberg |
| 2 | A. Solar-Lezama: Program Sketching. STTT 15, 2013 | Dominik Geißler | Tobias Winkler |
| 3 | A.V. Nori, S. Ozair, S.K. Rajamani, D. Vijaykeerthy: Efficient synthesis of probabilistic programs. ACM SIGPLAN Notices 50, 2015 | – | – |
| Synthesis by Deductive Search | |||
| 4 | S. Srivastava, S. Gulwani, J.S. Foster: From program verification to program synthesis. POPL 2010 | – | – |
| 5 | N. Polikarpova, I. Sergey: Structuring the Synthesis of Heap-Manipulating Programs. POPL 2019 | Jakob van Sprang | Thomas Noll |
| Synthesis from Input/Output Examples | |||
| 6 | J. Hamza, V. Kuncak: Minimal Synthesis of String To String Functions From Examples. VMCAI 2019 | Markus Rümenapp | Tobias Winkler |
| 7 | S. Chasins, P.M. Phothilimthana: Data-Driven Synthesis of Full Probabilistic Programs. CAV 2017 | – | – |
| 8 | K. Shi, J. Steinhardt, P. Liang: FrAngel: component-based synthesis with control structures. POPL 2019 | Rico Stanosek | Thomas Noll |
| Synthesis using Large Language Models | |||
| 9 | J. 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 2021 | Andreas Holzinger | Lutz Klinkenberg |
| 10 | E. 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 | |||
| 11 | D.J. Mankowitz et al.: Faster sorting algorithms discovered using deep reinforcement learning. Nature 618, 2023 | Krzysztof Adam Kostrzewa | Thomas Noll |
Registration
Registration to the seminar is handled via the SuPra system.
Grading Scheme
You can access the grading scheme here: https://moves.rwth-aachen.de/wp-content/uploads/seminar_grading_scheme.pdf
Additional Material
- Report template
- Presentation template
- How to Write a Seminar Paper
- Ethische Richtlinien für das Verfassen wissenschaftlicher Arbeiten
- How to Give Presentations
- Introduction to LaTeX