Dissertations
-
Nicolas El Maalouly, Towards a Deterministic Polynomial Time Algorithm for the Exact Matching Problem.
Advisor: Bernd Gärtner (referee) / Co-referees: Ola Svensson (EPFL), Emo Welzl
Examination: February 16, 2024.
-
Saeed Ilchi,Deterministic Distributed Algorithms for Hitting and Dominating Sets, Spanners, and Network Decompositions.
Advisor: M. Ghaffari (referee) / Co-referees: B. Gärtner, Surender Baswana (IIT Kanpur), Fabian Kuhn (University of Freiburg)
Examination: June 13, 2023.
-
Meghana Mallik Reddy, Beyond-Planar Graphs: Simple and Maximal.
Advisor: Emo Welzl (referee) / Co-referees: Stefan Felsner (TU Berlin), Michael Hoffmann
Examination: November 20, 2023.
-
Hung Hoang, On Two Combinatorial Reconfiguration Problems: Reachability and Hamiltonicity.
Advisor: Bernd Gärtner (referee) / Co-referees: Jean Cardinal (Université Libre de Bruxelles), Torsten Mütze (University of Warwick), Emo Welzl
Examination: August 23, 2022
-
Nicolas Grelier, Maximum Clique in Generalisations of Disk Graphs and Plane Geometric Graphs on Degenerate Point Sets.
Advisor: Emo Welzl (referee) / Co-referees: Marthe Bonamy (CNRS), Michael Hoffmann, Wolfgang Mulzer (Freie Universität Berlin)
Examination: July 20, 2022
-
Patrick Schnider, Variations on the Center Transversal Theorem.
Advisor: Emo Welzl (referee) / Co-referees: Erin Wolf Chambers (Saint Louis University), Pablo Soberon (City University of New York), Uli Wagner (IST Austria)
Examination: June 22, 2020
-
Ahad N. Zehmakan, On the Spread of Information Through Graphs.
Advisor: Bernd Gärtner (referee) / Co-referees: David Peleg (Weizmann Institute), Roger Wattenhofer (D–ITET)
Examination: December 19, 2019
-
Malte Milatz, Grid Orientations.
Advisor: Bernd Gärtner (referee) / Co-referees: Volker Kaibel (OVGU Magdeburg), Angelika Steger (D–INFK)
Examination: January 31, 2019
-
Jerri Nummenpalo, Odd Graph Hamiltonicity and Satisfiability Sampling.
Advisor: Emo Welzl (referee) / Co-referees: Jean Cardinal (ULB Bruxelles), Torsten Mütze (TU Berlin), Angelika Steger (D–INFK)
Examination: Dec 18, 2018
-
Manuel Wettstein, On the Multiplicity of Crossing-free Geometric Graphs.
Advisor: Emo Welzl (referee) / Co-referee: Stefan Felsner (TU Berlin)
Examination: Jun 1, 2018
-
Antonis Thomas, Unique Sink Orientations: Complexity, Structure and Algorithms.
Advisor: Bernd Gärtner (referee) / Co-referees: Emo Welzl, Thomas Dueholm Hansen (Aarhus University).
Examination: Oct 24, 2017.
-
May Szedlák, Redundancy in Linear Systems: Combinatorics, Algorithms and Analysis.
Advisor: Bernd Gärtner (referee) / Co-referees: Rico Zenklusen (D-MATH), Komei Fukuda, Kenneth L. Clarkson (IBM Research).
Examination: May 3, 2017.
-
Chidambaram Annamalai, Algorithmic Advances in Allocation and Scheduling.
Advisor: Emo Welzl (referee) / Co-referees: Penny Haxell (University
of Waterloo), Rico Zenklusen (D-MATH), Ola Svensson (EPFL).
Examination: Feb 22, 2017.
-
Hemant Tyagi,
On low dimensional models for functions in high dimensions
Advisor: Bernd Gärtner (referee) / Co-referees: Andreas Krause, ETH Zürich, Jared Tanner, University of Oxford / Examination: Mar 17, 2016.
-
Vincent Kusters,
Simultaneous Embeddings
Advisor: Emo Welzl (referee) / Co-referees: Michael Hoffmann, Michael Kaufmann, University of Tübingen / Examination: Dec 4, 2015.
-
Timon Hertli,
Improved Exponential Algorithms for SAT and CISP
Advisor: Emo Welzl (referee) / Co-referees: Kazuo Iwama, Kyoto University, Ramamohan Paturi, University of California, San Diego / Examination: Dec 17, 2014.
-
Sebastian Stich,
Convex Optimization with Random Pursuit
Advisor: Bernd Gärtner (referee) / Co-referees: Yurii Nesterov, Université catholique de Louvain, Christian L. Müller, New York University, Emo Welzl, ETH Zürich / Examination: Jul 11, 2014.
-
Anna Gundert,
On Expansion and Spectral Properties of Simplicial Complexes
Advisor: Emo Welzl (referee) / Co-referees: Uli Wagner, IST Austria, Michael Farber, University of Warwick / Examination: Nov 22, 2013.
-
Yves Brise,
Integral Methods for Quadratic Programming: Theory and Implementation
Advisor: Emo Welzl (referee) /
Co-referees: Bernd Gärtner, ETH Zürich, Friedrich Eisenbrand, EPF Lausanne
/
Examination: Sep 13, 2012.
-
Robin Moser,
Exact Algorithms for Constraint Satisfaction Problems
Advisor: Emo Welzl (referee) /
Co-referees: Uwe Schöning, Universität Ulm, Germany; Gábor Tardos, Alfré Rényi Institute of Mathematics, Budapest, Hungary
/
Examination: Sep 11, 2012.
-
Heidi Gebauer,
Combinatorial Games on Graphs
Advisors: Tibor Szabó, Freie Universität Berlin, Germany (co-referee), Emo Welzl (referee) /
Co-referees: Tomasz Łuczak, Adam Mickiewicz University, Poland
/
Examination: Oct 21, 2011.
-
Martin Jaggi,
Sparse Convex Optimization Methods for Machine Learning
Advisors: Bernd Gärtner (co-referee), Emo Welzl (referee) /
Co-referees: Joachim Buhmann, ETH; Joachim Giesen, Friedrich-Schiller-Univ. Jena, Germany; Elad Hazan, Technion - Israel Institute of Technology, Haifa, Israel
/
Examination: Oct 4, 2011.
-
Tobias Christ,
Discrete Descriptions of Geometric Objects
Advisors: Michael Hoffmann (co-referee), Emo Welzl (referee) /
Co-referee: Joseph O'Rourke, Smith College, Northampton, USA
/
Examination: Aug 31, 2011.
-
Marek Sulovský,
Geometric Hypergraphs - k-Sets and Conflict-Free Coloring
Advisors: Uli Wagner (co-referee), Emo Welzl (referee) /
Co-referee: Boris Aronov, New York University, Polytechnic Institute, USA
/
Examination: Jun 23, 2011.
-
Dominik Scheder,
Algorithms and Extremal Properties of SAT and CSP
Advisor: Emo Welzl (referee) / Co-referee: Ramamohan Paturi, University of California, San Diego, USA
/
Examination: Mar 21, 2011.
-
Patrick Traxler,
Exponential Time Complexity of SAT and Related Problems
Advisor: Emo Welzl (referee)
/
Co-referee: Martin Grohe, Humboldt-Universität Berlin, Germany
/
Examination: Mar 8, 2010
-
Philipp Zumstein,
Extremal Colorings and Extremal Satisfiability
Advisors: Tibor Szabó (co-referee), Emo Welzl (referee)
/
Examination: Sep 15, 2009
-
Andreas Razen,
Crossing-Free Configurations on Planar Point Sets
Advisors: Emo Welzl (referee)
/
Co-referee: Jack Snoeyink, University of North Carolina at Chapel Hill, USA;
Uli Wagner
/
Examination: Sep 16, 2009
-
Robert Berke,
Colorings and Transversals of Graphs
Advisors: Tibor Szabó (co-referee), Emo Welzl (referee)
/
Co-referee: Nati Linial, Hebrew University of Jerusalem, Israel.
/
Examination: May 19, 2008
-
Eva-Maria Schuberth,
Measuring the Perceived Quality of Parameterized Multimedia Algorithms
Advisors: Joachim Giesen, Emo Welzl (referee)
/
Co-referee: Joachim Giesen, ETH Zurich and Max-Planck Institute für Informatik, Saarbrücken; Klaus Simon, EMPA Medientechnik, St. Gallen.
/
Examination: Sep 24, 2007
-
Leo Rüst,
The P-Matrix Linear Complementarity Problem - Generalizations and Specializations
Advisors: B. Gärtner, E. Welzl (referee)
/
Co-referees: B. Gärtner, ETH Zurich; H.-J. Lüthi, ETH Zurich; W. D. Morris, George Mason University, Fairfax
/
Examination: Aug 21, 2007
-
Dieter Mitsche,
Spectral Methods for Reconstruction Problems
Advisors: Joachim Giesen, Emo Welzl (referee)
/
Co-referees: Josep Diaz, Universitat Politecnica de Catalunya, Barcelona; Joachim Giesen, MPI für Informatik, Saarbrücken
/
Examination: Dec 18, 2006
-
Shankar Ram Lakshminarayanan,
Approximation Results for the Traveling Salesman and Related Problems
Advisors: Markus Bläser, Universität des Saarlandes, Saarbrücken, Germany (referee)
/
Co-referees: Lars Engebretsen, Google Switzerland GmbH; Emo Welzl
/
Examination: Aug 21, 2006
- Milos Stojakovic,
Positional Games on Graphs
Advisors: Tibor Szabó; Emo Welzl (referee)
/
Co-referees: Jozsef Beck, Rutgers University, USA, and Tibor Szabó, ETH Zurich
/
Examination: Sep 23, 2005
- Kaspar Fischer,
Smallest Enclosing Balls -
Combinatorial Structure and Algorithms
Advisors: B. Gärtner; E. Welzl (referee)
/
Co-referees: B. Gärtner, ETH Zurich, and
Jiri Matousek, Charles University Prague, Czech Republic
/
Examination: Jul 8, 2005
- Yoshio Okamoto,
Structural Parameters in Combinatorial Objects
Advisor: Emo Welzl (referee)
/
Co-referee: Komei Fukuda, ETH Zurich
/
Examination: Jan 25, 2005
- Michael Hoffmann,
On the Existence of Paths and Cycles
Advisor: Emo Welzl (referee)
/
Co-referee: Erik Demaine,
Massachusetts Institute of Technology, USA
/
Examination: Jan 21, 2005
- Ingo Schurr,
Unique Sink Orientations of Cubes
Advisors: Tibor Szabó (co-referee), D-INFK, ETH Zurich, Emo Welzl (referee)
/
Co-referee: Günter Ziegler, TU Berlin
/
Examination: Oct 4, 2004
- Udo Adamy,
Call Admission Control and On-Line Interval Coloring
Advisors: Thomas Erlebach, D-ITET, ETH Zurich, Emo Welzl (referee)
/
Co-referee: Thomas Erlebach, D-ITET, ETH Zurich
/
Examination: Dec 11, 2003
- Matthias John,
Flow complexes - Structure, Algorithms and Applications
Advisors: J. Giesen; E. Welzl (referee)
/
Co-referees: Nina
Amenta, University of California at Davis, California, USA, and
J. Giesen, ETH Zurich
/
Examination: Jun 27, 2003
- Uli Wagner,
k-Sets
and Applications
Advisor: E. Welzl
/
Co-referee:
Jiri Matousek, Charles University, Prague, Czech Republic
/
Defense (at D-MATH): Jun 26, 2003
- Falk Tschirschnitz,
LP-Related Properties of Polytopes with Few Facets
Advisors: B. Gärtner; E. Welzl (referee)
/
Co-referees:Walter
Morris, George Mason University, Fairfax, Virginia, USA, and
B. Gärtner, ETH Zurich
/
Examination: Jun 25, 2003
- Sven Schönherr,
Quadratic Programming in Geometric Optimization:
Theory, Implementation, and Applications
Advisors: B. Gärtner, E. Welzl (referee)
/
Co-referees: B. Gärtner, and T. M. Liebling, EPFL Lausanne
/
Examination: Jul 12, 2002
- Alexander Below,
Complexity of Triangulation
Advisor: J. Richter-Gebert, TU München (formerly ETH Zürich)
/
Co-referees: P. Gritzmann, TU München, and
E. Welzl
/
Examination: Jun 3, 2002
- Csaba D. Tóth,
Planar Subdivisions
Advisor: E. Welzl
/
Co-referee: G. Rote, Freie Univ. Berlin
/
Examination: May 3, 2002
- Christoph Ambühl,
On the List Update Problem
Advisors: B. Gärtner; B. von Stengel; E. Welzl (referee)
/
Co-referees: S. Albers,
Univ. Freiburg, and
B. von Stengel, London School of Economics and Political Science
/
Examination: Feb 8, 2002
- József Solymosi,
Ramsey-Type Results on Planar Geometric Objects
Advisor: E. Welzl
/
Co-referees: J. Pach, Courant Inst., NYU, and G. Rote, FU Berlin
/
Examination: Mar 2, 2001
- Joachim Giesen,
Curve Reconstruction
Advisor: E. Welzl
/
Co-referees: K. Mehlhorn, Max-Planck-Inst. f. Informatik, Saarbrücken
/
Examination: Jan 24, 2000
- Artur Andrzejak,
On
k-Sets and their Generalizations
Advisor: E. Welzl
/
Co-referees: K. Fukuda, Departement Mathematik, ETH
/
Examination: Dec 19, 1999
- Lutz Kettner,
Software Design in Computational Geometry and
Contour-Edge Based Polyhedron Visualization
Advisor: E. Welzl
/
Co-referees: J.-D. Boissonnat, INRIA Sophia-Antipolis
/
Examination: Sep 24, 1999
- Will, Hans-Martin,
Computation of Additively Weighted Voronoi Cells for
Applications in Molecular Biology
Advisor: E. Welzl
/
Co-referees: H. Edelsbrunner, University of Illinois at Urbana Champaign,
S. Wodak, Free University of Brussels
/
Examination: Jun 25, 1999