An interview with Vladimir Trifonov 2005 Danny Lewin best student paper award winner

ABSTRACT

The 2005 Danny Lewin Prize for the best student paper at STOC was awarded to Vladimir Trifonov, of the University of Texas at Austin, for his paper "An O(log n log log n) Space Algorithm for Undirected st-Connectivity" [1]. Hal Gabow recently started the tradition of interviewing the Danny Lewin Prize winner and publishing the interview in SIGACT News. (An interview with the 2003 winner Tom Hayes can be found in the September 2003 issue.) I had the pleasure of (electronically) chatting with Vladimir about his work; a transcript of our conversation follows.

REFERENCES

• 1: Vladimir Trifonov, An O(log n log log n) space algorithm for undirected st-connectivity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060684]

INDEX TERMS

Primary Classification:
  A. General Literature
  A.0 GENERAL
      Subjects: Biographies/autobiographies

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Graph labeling

General Terms:
Algorithms, Theory