Alan Frieze

Alan Michael Frieze (* 25. Oktober 1945 in London) ist ein britischer Informatiker. Frieze studierte an der Universität Oxford (Bachelor-Abschluss 1966) und wurde 1975 an der Universität London bei Keith Wolfenden promoviert. 1968/69 forschte er (als Research Officer) bei British Rail und 1969/70 war er Programmierer bei ICL. 1970/71 war er Lecturer am Polytechnic of North London und 1972 bis 1987 lehrte er am Queen Mary College der Universität London. Er ist seit 1987 Professor an der Carnegie Mellon University. Mit Martin Dyer und Ravindran Kannan fand er 1991 einen Polynomialzeitalgorithmus zur Berechnung der Volumina konvexer Körper in allen Dimensionen, wofür alle drei den Fulkerson-Preis erhielten. Zudem wurde die Arbeit bei der Verleihung des Knuth-Preises an Kannan als eine der herausragendsten Entwicklungen von Algorithmen hervorgehoben. Die Laufzeit aller vorher bekannten Algorithmen zur Volumenberechnung wuchsen exponentiell mit der Dimension. Ihr Algorithmus verwendet Markow-Ketten-Monte-Carlo-Algorithmen (MCMC) und ist eine der frühesten und wichtigsten Anwendungen dieser Technik bei Näherungsalgorithmen. Mit Dyer leistete er wichtige Beiträge zur probabilistischen Analyse von Algorithmen in kombinatorischer Optimierung. Mit Kannan fand er eine algorithmische Version des Regularitätslemmas von Endre Szemerédi. In ihrer Arbeit führten sie das schwache Regularitätslemma ein, das ein wichtiges kombinatorisches Werkzeug für verschiedene Algorithmen wurde (Streaming Algorithms, Graph Limits, Sublinear Algorithms). 1991 erhielt er den Fulkerson-Preis mit Dyer und Kannan. 1997 war er Guggenheim Fellow. 2014 wurde er als Plenarsprecher auf dem Internationalen Mathematikerkongress in Seoul ausgewählt (Random structures and algorithms). Er ist Fellow der American Mathematical Society. Er ist seit 1969 mit Carol Frieze (geborene Mayfield) verheiratet, die ebenfalls Informatik an der Carnegie Mellon University lehrt. Mit ihr hat er zwei Kinder.