2008+
- : Solving NP-hard semirandom graph problems in polynomial expected time, Journal of Algorithms. to appear.
- : Coloring semirandom graphs, Combinatorics, Probability and Computing. to appear.
- : Counting connected graphs and hypergraphs via the probabilistic method, Random Structures and Algorithms. to appear.
2007
- : Quasi-randomness and algorithmic regularity for graphs with general degree distributions. January. Preprint.
- : The order of the giant component of random hypergraphs. January. Preprint.
- : Local limit theorems and the number of connected hypergraphs. January. Preprint.
- : Strong refutation heuristics for random k-SAT, Combinatorics, Probability and Computing, 16: 5-28.
- : Why almost all k-colorable graphs are easy. To appear in the Proceedings of STACS 2007.
- : On the chromatic number of random graphs. January. Preprint.
2006
- : Zufällige Graphen. In: Wolfgang Reisig und Johann Christoph Freytag (Herausgeber): Informatik - Aktuelle Themen im historischen Kontext, Seiten 49-77. Springer.
- : A spectral heuristic for bisecting random graphs, Random Structures and Algorithms, 29: 351-398.
- : Finding large independent sets in polynomial expected time, Combinatorics, Probability and Computing, 15: 731-751.
- : Graph partitioning via adaptive spectral techniques. July. Preprint.
- : An adaptive spectral heuristic for partitioning random graphs. In: ICALP, Nummer 4051 in LNCS, Seiten 691-702. Springer. JOURNAL VERSION.
- : Spectral partitioning of random graphs with given expected degrees. In: Gonzalo Navarro, Leopoldo Bertossi und Yoshiharu Kohayakawa (Herausgeber): 4th IFIP International Conference on Theoretical Computer Science - TCS 2006 (19th World Computer Congress 2006, Santiago de Chile), Seiten 271-282.
- : A heuristic for the stacker crane problem on trees which is almost surely exact, Journal of Algorithms, 61: 1-19.
- : An improved algorithm for approximating the chromatic number of G(n,p), Information Processing Letters, 99: 234-238.
- : The spectral gap of random graphs with given expected degrees. In: ICALP, Nummer 4051 in LNCS, Seiten 15-26. Springer.
- : MAX k-CUT and approximating the chromatic number of random graphs, Random Structures and Algorithms, 28: 289-322.
2005
- : A spectral heuristic for bisecting random graphs. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, Seiten 850-859. JOURNAL VERSION.
- : Spectral techniques, semidefinite programs, and random graphs. Habilitationsschrift, Humboldt Universität zu Berlin, Institut für Informatik.
- : The Lovasz number of random graphs, Combinatorics, Probability and Computing, 14: 439-465.
- : On the Laplacian eigenvalues of G(n,p). Preprint.
- : The evolution of the min-min random graph process. Preprint.
- : A hard dial-a-ride problem that is easy on average, Journal of Scheduling, 8: 197-210.
- : Limit theorems for non-commutative random variables, Journal of Theoretical Probability, 18: 595-614.
2004
- : Coloring semirandom graphs optimally. In: Josep Diaz, Juhani Karhumäki, Arto Lepistö und Donald Sannella (Herausgeber): Automata, Languages and Programming: 31st International Colloquium (ICALP 2004), Band 3142 der Reihe LNCS, Seiten 383-395. Springer. JOURNAL VERSION.
- : Strong refutation heuristics for random k-SAT. In: Klaus Jansen, Sanjeev Khanna, Jose D. P. Rolim und Dana Ron (Herausgeber): Approximation, Randomization, and Combinatorial Optimization, Nummer 3122 in LNCS, Seiten 310-321. Springer. JOURNAL VERSION.
- : Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT, Theoretical Computer Science, 329: 1-45.
- : Counting connected graphs and hypergraphs via the probabilistic method. In: Klaus Jansen, Sanjeev Khanna, Jose D. P. Rolim und Dana Ron (Herausgeber): Approximation, Randomization, and Combinatorial Optimization, Nummer 3122, Seiten 322-333. Springer. JOURNAL VERSION.
- : Exact and approximative algorithms for coloring G(n,p), Random Structures and Algorithms, 24(3): 259-278, May.
2003
- : Finding large independent sets in polynomial expected time. In: Helmut Alt und M. Habib (Herausgeber): STACS 2003, Band 2607 der Reihe LNCS, Seiten 511-522. Springer. JOURNAL VERSION.
- : The Lovasz number of random graphs. In: Sanjeev Arora, Klaus Jansen, Jose D. P. Rolim und A. Sahai (Herausgeber): Approximation, randomization, and combinatorial optimization, Band 2764 der Reihe LNCS, Seiten 228-239. Springer. JOURNAL VERSION.
- : Certifying unsatisfiability of random 2k-SAT formulas using approximation techniques. In: A. Lingas und B. J. Nilsson (Herausgeber): FCT 2003, Band 2751 der Reihe LNCS, Seiten 15-26. Springer. JOURNAL VERSION.
- : A heuristic for the stacker crane problem on trees which is almost surely exact. In: Algorithms and Computation, 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings, Band 2906 der Reihe LNCS, Seiten 605-614. Springer. JOURNAL VERSION.
- : MAX k-CUT and approximating the chromatic number of random graphs. In: J. C. M. Baeten, Jan Karel Lenstra, J. Parrow und Gerhard J. Woeginger (Herausgeber): Automata, Languages and Programming (30th International Colloquium, ICALP 2003), Band 2719 der Reihe LNCS, Seiten 200-211. Springer. JOURNAL VERSION.
- : Revisiting the algebra of Petri net processes under the collective token philosophy, Fundamenta Informaticae, 54: 151-164.
- : Colouring random graphs in polynomial expected time. In: Helmut Alt und M. Habib (Herausgeber): STACS 2003, Band 2607 der Reihe LNCS, Seiten 487-498. Springer. JOURNAL VERSION.
2002
- : Varianz und Erwartungswert in Operatoralgebren. Doktorarbeit, University of Hamburg.
- : Coloring k-colorable Semi-Random Graphs in Polynomial Expected Time via Semidefinite Programming. In: Krzystof Diks und W. Rytter (Herausgeber): Mathematical Foundations of Computer Science 2002, Band 2420 der Reihe LNCS, Seiten 201-211. JOURNAL VERSION.
- : Finding sparse induced subgraphs of semirandom graphs. In: Jose D. P. Rolim und S. Vadhan (Herausgeber): Randomization and approximation techniques in computer science, Band 2483 der Reihe LNCS, Seiten 139-148. Springer. JOURNAL VERSION.
