Heidi Gebauer

Contact Postal Address: Institut für Theoretische Informatik ETH Zürich, CAB G 31.2 Universitätstrasse 6 CH-8092 Zürich Switzerland Phone: +41-44-632 28 66 Fax: +41-44-632 10 63 e-mail: gebauerh at inf.ethz.ch

Publications

• The Local Lemma is Tight for SAT (with T. Szabó and G. Tardos), Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (2011), 664-674.


• On the Clique-Game, European Journal of Combinatorics, to appear


• A Doubly Exponentially Crumbled Cake (with T. Christ, A. Franke, J. Matoušek and T. Uno), Proc. European Conference on Combinatorics (EuroComb), (2011), to appear


• Disproof of the Neighborhood Conjecture with Implications to SAT, Proc. 17th Annual European Symposium on Algorithms (ESA), (2009), 764-775.


• The Lovász Local Lemma and Satisfiability (with R. A. Moser, D. Scheder, E. Welzl), Efficient Algorithms - Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, (2009) LNCS 5760, 30-54 .
  


• Asymptotic Random Graph Intuition for the Biased Connectivity Game (with T. Szabó), Random Structures & Algorithms, 35 (2009), 431-443.
  

• Finding and Enumerating Hamilton Cycles in 4-Regular Graphs, Journal of Theoretical Computer Science, to appear.

  An extended abstract appeared in Proc. 5th Workshop on Analytic Algorithmics and Combinatorics (ANALCO), (2008), 241-248

  
  

• Enumerating all Hamilton Cycles and Bounding the Number of Hamilton Cycles in 3-Regular Graphs, Electronic Journal of Combinatorics, to appear.

  An extended abstract appeared in Proc. 5th Workshop on Analytic Algorithmics and Combinatorics (ANALCO), (2008), 241-248

  
  

• Fast Exponential-Time Algorithms for the Forest Counting and the Tutte Polynomial Computation in Graph Classes (with Y.Okamoto), International Journal of Foundations of Computer Science, 20 (2009), 25-44 .

  An extended abstract appeared in Proc. 13th Computing: The Australasian Theory Symposium (CATS), 65 (2007), 63-69.

  
  

Awards

• Best Student Paper Award at the Annual European Symposium on Algorithms (ESA), 2009.


• ETH Medal Award for outstanding Master Thesis, Computer Science, 2007.
  Title: How many Hamiltonian Cycles, Spanning Trees, Perfect Matchings are there?
  Supervisors: Dr. Tibor Szabo, Prof. Emo Welzl

Teaching Assistance

• Diskrete Mathematik (D-ITET), Fall 10, lecturers: Prof. Angelika Steger, Prof. Emo Welzl.


• Graphs and Algorithms: Advanced Topics, Fall 10, lecturer: Dr. Uli Wagner.


• SAT Seminar, Spring 10, responsible: Prof. Emo Welzl.


• Datenstrukturen und Algorithmen, Spring 10, lecturer: Prof. Peter Widmayer.


• Graphs and Algorithms: Advanced Topics, Fall 09, lecturers: Dr. Dan Hefetz, Dr. Uli Wagner.


• SAT Seminar, Spring 09, responsible: Prof. Emo Welzl.


• Datenstrukturen und Algorithmen, Spring 09, lecturer: Prof. Peter Widmayer.


• Algorithms, Probability and Computing, Fall 08, lecturers: Prof. Angelika Steger, Prof. Emo Welzl, Prof. Peter Widmayer.


• Algorithms, Probability and Computing, Fall 07, lecturers: Prof. Angelika Steger, Prof. Emo Welzl, Prof. Peter Widmayer.