Research Institute for Discrete Mathematics

Lecture Course "Chip Design"

Summer Term 2026

Module V4C3 and MA-INF 1202

This course is part of the Master's Programs in Mathematics and Computer Science. Basic knowledge in combinatorial optimization is required.

Chip design is one of the most interesting application areas of mathematics. We discuss theory and practice. Many applications of combinatorial optimization are shown. Recent theory, algorithms, and implications of new chip technologies are discussed. The course covers topics in Boolean circuit optimization, placement, timing optimization, and routing.

This course is in English. Since there exists no suitable (mathematical) textbook yet, I will distribute some lecture notes. Many topics and references can also be found in:

S. Held, B. Korte, D. Rautenbach, J. Vygen: Combinatorial optimization in VLSI design. In: "Combinatorial Optimization: Methods and Applications" (V. Chvátal, ed.), IOS Press 2011, pp. 33-96
C.J. Alpert, D.P. Mehta, S.S. Sapatnekar, eds.: Handbook of Algorithms for VLSI Physical Design Automation. Taylor and Francis 2009
L. Lavagno, I.L. Markov, G. Martin, and L.K. Scheffer, eds.: Electronic Design Automation for IC Implementation, Circuit Design, and Process Technology. CRC Press, 2nd edition, 2016.
A.B. Kahng, J. Lienig, I.L. Markov, J. Hu: VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer 2011

See here for a very brief introduction. The Arithmeum hosts parts the comprehensive 2019 exposition "Mathematics and aesthetics of chip design" and online videos and games about chip design .
They help to understand the overall chip design problem and give an impression on some of the problems that we will study mathematically in depth.

Class Hours: Tuesdays and Thursdays, 12:15–13:45
Room: Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2)
Exercise Classes: two hours per week, t.b.a.
Exams: oral, in the weeks August 10–14 and September 14–18, to be scheduled individually

Prof. Dr. J. Vygen

Class Hours:	Tuesdays and Thursdays, 12:15–13:45
Room:	Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2)
Exercise Classes:	two hours per week, t.b.a.
Exams:	oral, in the weeks August 10–14 and September 14–18, to be scheduled individually