Seminar in Theoretical CS, Winter 2023/24
News
- 17.05.2023: We are online!
Introduction and Assignment of Topics
- Slides of introduction (TBA)
Dates & Deadlines
| TBA | Topic preferences due |
| TBA | Detailed outline due |
| TBA | Full report due |
| TBA | Presentation slides due |
| TBA | 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 | ||
| 2 | A. Solar-Lezama: Program Sketching. STTT 15, 2013 | ||
| 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 | ||
| Synthesis from Input/Output Examples | |||
| 6 | J. Hamza, V. Kuncak: Minimal Synthesis of String To String Functions From Examples. VMCAI 2019 | ||
| 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 | ||
| Synthesis by Equational Term Rewriting | |||
| 9 | C. Smith, A. Albarghouthi: Program Synthesis with Equivalence Reduction. VMCAI 2019 | ||
| Synthesis using Large Language Models | |||
| 10 | 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 | ||
| 11 | 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 | ||
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 (TBA)
- Presentation template (TBA)
- How to Write a Seminar Paper
- Ethische Richtlinien für das Verfassen wissenschaftlicher Arbeiten
- How to Give Presentations
- Introduction to LaTeX