Professur Theoretische Informatik

Manuscripts

  1. Andreas Goerdt, Lutz Falke.
    Satisfiability thresholds beyond k-XORSAT
  2. Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink.
    Tight Thresholds for Cuckoo Hashing via XORSAT

Random Structures

Journals
  1. Amin Coja-Oghlan, Andreas Goerdt, André Lanka.
    Strong Refutation Heuristics for random k-SAT.
    Combinatorics, Probability and Computing 16, Issue 1, 2007, 5-28.

  2. Joel Friedman, Andreas Goerdt, Michael Krivelevich.
    Recognizing more Random Unsatisfiable k-SAT Instances efficiently.
    SIAM Journal on Computing 35, 2005, 408-430.

  3. Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich.
    Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT.
    Theoretical Computer Science 329, 2004, 1-45.

  4. Andreas Goerdt, André Lanka.
    Recognizing more Random Unsatisfiable 3-SAT Instances efficiently.
    Electronic Notes in Discrete Mathematics 16, 2003.

  5. Andreas Goerdt, Tomasz Jurdzinski.
    Some results on Random Unsatisfiable k-SAT Instances and Approximation Algorithms Applied to Random Structures.
    Combinatorics, Probability and Computing 12, 2003, 245 - 267.

  6. Andreas Goerdt, Mike Molloy.
    Analysis of Edge Deletion Processes on Faulty Random Regular Graphs.
    Theoretical Computer Science 297, 2003, 241 - 260.

  7. Andreas Goerdt.
    Random Regular Graphs with Edge Faults: Expansion Through Cores.
    Theoretical Computer Science 264, 2001, 91 - 125.

  8. -
    The Giant Component Threshold for Random Regular Graphs with Edge Faults.
    Theoretical Computer Science 259, 2001, 307 - 321.

  9. -
    A Remark on Random 2-SAT.
    Discrete Applied Mathematics 96/97, 1999, 107 - 110.

  10. -
    A Threshold for Unsatisfiability.
    Journal of Computer and System Sciences 53(3), 1996, 469 - 486.

Conferences
  1. Andreas Goerdt.
    On Random Betweenness Constraints.
    In: 17th FCT 2009, LNCS 5699, 157-168.

  2. -
    On Random Ordering Constraints.
    In: CSR 2009, LNCS 5675, 105-116.

  3. Amin Coja-Oghlan, Andreas Goerdt and André Lanka.
    Spectral partitioning of random graphs with given expected degrees.
    In: 4th IFIP International Conference on Theoretical Computer Science - TCS 2006, 271-282.

  4. Andreas Goerdt, André Lanka.
    On the hardness and easiness of random 4-SAT formulas.
    In Proceedings ISAAC 2004,LNCS 3341, 470-483.

  5. Amin Coja-Oghlan, Andreas Goerdt, André Lanka.
    Strong Refutation Heuristics for Random k-SAT.
    In Proceedings RANDOM 2004, LNCS 3122, 310-321.

  6. Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich.
    Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques.
    In Proceedings FCT 2003, LNCS 2751, 15-26.

  7. Andreas Goerdt, André Lanka.
    Recognizing more Random Unsatisfiable 3-SAT Instances efficiently.
    In Proceedings des LICS 2003 Workshops Typical Case Complexity and Phase Transitions.

  8. Andreas Goerdt, Tomasz Jurdzinski.
    Some Results on Random Unsatisfiable k-SAT Instances and Approximation Algorithms Applied to Random Structures.
    In Proceedings MFCS 2002, LNCS 2420, 280 - 291.

  9. Joel Friedman, Andreas Goerdt.
    Recognizing more Random Unsatisfiable 3-SAT Instances efficiently.
    In Proceedings ICALP 2001, LNCS 2076, 310 - 321.

  10. Andreas Goerdt, Michael Krivelevich.
    Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods.
    In Proceedings STACS 2001, LNCS 2010, 294 - 304.

  11. Andreas Goerdt, Mike Molloy.
    Analysis of Edge Deletion Processes on Faulty Random Regular Graphs.
    In Proceedings LATIN 2000, LNCS 1776, 38 - 47.

  12. Andreas Goerdt.
    Random Regular Graphs with Edge Faults:Expansion through Cores.
    In Proceedings ISAAC 1998, LNCS 1553, 219 - 228.

  13. -
    The Giant Component Threshold for Random Regular Graphs with Edge Faults.
    In Proceedings MFCS 1997, LNCS 1295, 279-288.

  14. Andreas Goerdt, Udo Kamps.
    On the Reasons for Average Superlinear Speedup in Parallel Backtrack Search.
    In Proceedings CSL 1993, LNCS 832, 106 - 127.

  15. Andreas Goerdt.
    A Threshold for Unsatisfiability.
    In Proceedings MFCS 1992, LNCS 629, 264 - 274.

Higher Types

Journals
  1. Andreas Goerdt.
    Characterizing Complexity Classes by Higher Type Primitive Recursive Definitions.
    Theoretical Computer Science 100(1), 1992, 45 - 66.

  2. -
    Characterizing Complexity Classes by General Recursive Definitions in Higher Types.
    Information and Computation 101(2), 1992, 202 - 218.

  3. Werner Damm, Andreas Goerdt.
    An Automata-Theoretical Characterization of the OI-Hierarchy.
    Information and Control 71(1/2), 1986, 1 - 32.

Conferences
  1. Andreas Goerdt, Helmut Seidl.
    Characterizing Complexity Classes by Higher Type Primitive Recursive Definitions, Part II.
    In Aspects and Prospects of Theoretical Computer Science, Proceedings 6th IMYCS 1990, LNCS 464, 148 - 158.

  2. Andreas Goerdt.
    Characterizing Complexity Classes by Higher Type Primitive Recursive Definitions.
    In Proceedings LICS 1989, 364 - 374.

  3. -
    On the Expressive Strength of the Finitely Typed Lambda-Terms.
    In Proceedings MFCS 1988, LNCS 324, 318 - 328.

  4. -
    Hoare Calculi for Higher Type Control Structures and their Completeness in the Sense of Cook.
    In Proceedings MFCS 1988, LNCS 324, 329 - 338.

  5. -
    Characterizing Complexity Classes by General Recursive Definitions in Higher Types.
    In Proceedings CSL 1988, LNCS 385, 99 - 117.

  6. -
    Hoare Logic for Lambda-Terms as Basis of Hoare Logic for Imperative Languages.
    In Proceedings LICS 1987, 293 - 299.

  7. -
    A Hoare Calculus for Functions Defined by Recursion on Higher Types.
    In Proceedings Logic of Programs 1985, LNCS 193, 106 - 117.

Proof Complexity and SAT-Algorithms

Journals
  1. Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan, Uwe Schöning.
    A Deterministic (2-2/(k+1))^n-Algorithm for k-SAT based on Local Search.
    Theoretical Computer Science, 289, 2002, 69 - 83.

  2. Andreas Goerdt.
    Regular Resolution versus Unrestricted Resolution.
    SIAM Journal on Computing 22(4), 1993, 661 - 683.

  3. -
    Davis-Putnam Resolution versus Unrestricted Resolution.
    Annals of Mathematics and Artificial Intelligence 6, 1992, 169 - 184.

  4. -
    N-Resolution versus Unrestricted Resolution.
    Theoretical Computer Science 93(1), 1992, 159 - 167.

Conferences
  1. Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning.
    Deterministic Algorithms for k-SAT based on Covering Codes and Local Search.
    In Proceedings ICALP 2000, LNCS 1853, 236 - 247.

  2. Andreas Goerdt.
    The Cutting Plane Proof System with Bounded Degree of Falsity.
    In Proceedings CSL 1991, LNCS 626, 119 - 133.

  3. -
    Cutting Plane versus Frege Proof Systems.
    In Proceedings CSL 1990, LNCS 533,174 - 194.

  4. -
    Comparing the Complexity of Regular and Unrestricted Resolution.
    In Proceedings GWAI 1990, Informatik Fachberichte 251, 181 - 185.

  5. -
    Unrestricted Resolution versus N-Resolution.
    In Proceedings MFCS 1990, LNCS 452, 300 - 305.

  6. -
    Davis-Putnam Resolution versus Unrestricted Resolution.
    In Proceedings CSL 1989, LNCS 440, 143 - 162.