Milena Mihail

Associate Professor
College of Computing
Georgia Institute of Technology

Ph.D., Computer Science, Harvard University, 1989
Diploma, Electrical Engineering, National technical University of Athens, 1984

Supported by NSF ITR-0220343 and CCF-0539972 		My Picture

Research Interests

Theory: Randomized Algorithms, Markov chain Monte Carlo Method, Spectral Graph Theory.
Networking: Algorithms and Models for the Internet, WWW, Content Distribution Networks, Social Online Communities, and other Complex Networks.

  • Workshop on Complex Networks and their Applications January 2007.
  • The Web Science Initiative at Georgia Tech.

  • Recent program committes: STOC 2007, EC 2007, WAW 2007, SODA 2008, FOCS 2009 (local arrangements).

    • Undergraduate Coordinator:

    I am the Undergraduate Coordinator for the School of Computer Science.
    Please feel free to contact me about undergraduate matters, especially those concerning curriculum.

    Vita, Research Statement, Recent Talks

  • Vita, February 2007
  • Research Statement
  • Complex networks: Connectivity and Functionality, an invited talk given at the NSF Workshop on the Theory of Networked Computation, Berkeley, March 15-16, 2006.
  • Erdos and the Internet , an invited talk given at Paul Erdos Lecture Series 2006 Memphis, March 24-25, 2006.
  • Algorithmic Performance in Complex Networks, a talk given at M.I.T. Algorithms and Complexity Seminar on May 18th, 2006.
  • Models for Social Networks, an informal talk given for the Georgia Tech Web Science Initiative biweekly tea meetings, on February 29, 2008.

    • Selected Articles on Markov Chains, Expanders, Spectra, and Randomization

  • ``Conductance and Convergence of Markov Chains: A Combinatorial treatment of Expanders'', FOCS 89, pp 526-531.
  • ``Polytopes, Permanents, and Graphs with Large Factors'', FOCS 88, pp 412-421, (together with P. Dagum, M. Luby, and U. Vazirani).
  • ``On Coupling and the Approximation of the Permanent'', Information Processing letters, 30-1989, pp 91-95.
  • ``Balanced Matroids'', STOC 92, pp 26-38, (together with T. Feder).
  • ``On the Expansion of Combinatorial Polytopes'', Invited Paper, LNCS Vol. 629, Springer-Verlag, 1992, pp 37-49.
  • ``On the Number of Eulerian Orientations of a Graph'', SODA 92, also Invited in Algorithmica Special Issue on Randomized Algorithms, 1996, 16, pp 402-414, (together with P. Winkler).
  • ``On the Random Walk Method for Protocol Testing'', Comp. Aided verification (CAV) 94, LNCS Vol. 818, 1994, pp 132-141 (together with C.H. Papadimitriou).
  • ``Monte Carlo and Markov Chain Simulation Techniques for network reliability and for Sampling'', Networks, Special issue on Network Reliability, Vol 28, No 3, 1995, pp 117-130, (together with A. Buchsbaum).
  • ``Learning the Fourier Spectrum of Probabilistic Lists and Trees'', SODA 91, pp 291-299, (together with W. Aiello).
  • ``Randomized Algorithms'', Chapter 16.6, Handbook of Discrete and Combinatorial mathematics, Editor J.L. Gross, CCR Press, 1999.

    • Selected Articles on Network Design

  • ``A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems'', STOC 93, pp 708-717, also in Combinatorica 15 (1995), pp 435-454, (together with D. Williamson, M. Goemans, and V. Vazirani). Chosen as paper of impact by the 1993 STOC program committee.
  • ``A Commercial Application of Steiner Network Design: Common Channel Signaling (ITP/INPLANS CCS) Network Topology Analyzer'', SODA 96, pp 548-557, (together with D. Shallcross, N. Dean, and M. Mostrel).
  • ``Covering Problems with Requirements and Costs Evolving Over Time'', RAND-APPROX 99, Berkeley, CA 1999.
  • ``Efficient Access to Optical Bandwidth: Wavelength Routing on Directed Fiber Trees, Rings, and Trees of Rings'', FOCS 95, pp 548-557, (together with C. Kaklamanis, and S. Rao).
  • ``Optimal Wavelength Routing on Directed Fiber Trees'', Theoretical Computer Science 221, 1999, pp 119-137, (together with T. Erlebach, C. Kaklamanis, and P. Persiano).
  • ``WDM Network Economics Sensitivities'', National Fiber Optic Engineers Conference 1997, Vol 1, pp 105-116, (together with K. Bala, R. Cardwell, H. Kobrinski, and O. Wasem).
  • ``Hierarchical Design of WDM Optical networks for ATM Transport'', GLOBECOM 95, pp 2188-2194, (together with K. Bala, and S.V. Jagannath).
  • ``Monte Carlo and Markov Chain Simulation Techniques for network reliability and for Sampling'', Networks, Special issue on Network Reliability, Vol 28, No 3, 1995, pp 117-130, (together with A. Buchsbaum).
  • ``Computing Spanning Trees in NETPAD'', DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol 15 1994, pp 85-98, (together with Keh-Wei Lih and Nate Dean).

    • Selected Articles on Networking and on Large Scale Data       (Click here for the Internet topology data that I work with.)

  • ``Approximating Betweeness Centrality'' in WAW 2007, (together with D.Bader, S. Kintali and K. Madduri).
  • ``Towards Topology Aware Networks'', in INFOCOM 2007, minisymposium, (together with C. Gkansidis, G. Goel and A. Saberi).
  • ``A Local Exchange Markov chain on Graphs with Given Degrees and Application in Connectivity of Peer-to-Peer Networks'', in FOCS 2006, (together with T. Feder, A. Guetz and A. Saberi).
  • ``Random Walks with Lookahead in Power Law Random Graphs'', to appear in Internet Mathematics(2006), (together with A. Saberi and P. Tetali).
  • ``Hybrid Search Schemes for Unstructured Peer-to-Peer Networks'', INFOCOM 2005, (together with C. Gkantsidis and A. Saberi).
  • ``On Certain Connectivity Properties of the Internet Topology'', FOCS 2003, also JCSS special issue on FOCS 2003, (together with C. Papadimitriou and A. Saberi). Click here for related power point presentation.
  • ``On the Random Walk method in Peer-to-Peer Networks'', INFOCOM 04, also in International Journal on Performance Evaluation, (together with C. Gkantsidis and A. Saberi).
  • ``Conductance and Congestion in Power Law Graphs'', SIGMETRICS 2003, (together with C. Gkantsidis and A. Saberi).
  • ``On the Eigenvalue Power-Law'', RANDOM 02, Harvard, MA, 2002 (together with C. Papadimitriou). Click here for power point presentation.
  • ``Spectral Analysis of Inetrnet Topologies'', INFOCOM 03, also to appear in Transactions on Networking, (together with C. Gkantsidis, and E. Zegura). Abstract in Dimacs Workshop on Internet and WWW Measurement, Mapping and Modeling, Feb 13-15 '02, and IPAM Workshop March 18-22 '02 on Large Scale Communication Networks. Click here for power point presentation.
  • ``On Generating Graphs with Prescribed Degree Sequences for Complex Network Modeling Applications'', Position Paper, ARACNE (Approx. and Randomized Algorithms for Communication Networks) 2002, Rome, IT, 2002 (together with N. Vishnoi).
  • ``The Markov Chain Simulation Method for Generating Connected Power Law Random Graphs'', Alenex 2003, (together with C. Gkantsidis, and E. Zegura).
  • ``On the Semantics of Internet Topologies'', submitted, (together with C. Gkantsidis, A. Saberi, and E. Zegura). Abstract in Dimacs Workshop on Internet and WWW Measurement, Mapping and Modeling, Feb 13-15 '02, and IPAM Workshop March 18-22 '02 on Large Scale Communication Networks.
  • ``Caching with Expiration Times'', SODA 02, also in Internet Mathematics, (together with P. Gopalan, H. Karloff, A. Mehta, and N. Vishnoi).
  • ``On the Complexity of the View Selection Problem'', PODS 99, pp 167-173, (together with H. Karloff).

    • Ph.D. Students:

  • Amin Saberi (joint with Vijay Vazirani), PhD in theory June 04. Currently Assistant Professor at Stanford University.
    Thesis Title: "Algorithmic Aspects of Complex Comminication Networks"
  • Christos Gkantsidis, PhD in networking Dec 05.
    Ccurrently at Microsoft Research, Systems and Networking Group, Cambridge, England. Some recent publicity at the Seattle Times.
    Thesis Title: "Algorithmic Performance of Large Scale Distributed Networks: A Spectral Method Approach"
  • Stephen Young, 5th year PhD in mathematics (ACO program), expected 08.
    Thesis Title: "Random Dot Product Graphs: A Flexible Network Model".
  • Giorgos Amanatidis, 4th year, PhD in mathematics (ACO program).
    Working on Graph Theoretic Aspects of Flexible Internet Models.
  • Gagan Goel, 4th year PhD in theory (joint wityh Vijay Vazirani).
    Working on Auction Algorithms and Decentralized Internet Algoririthms.
  • Bradley Green, 3rd year PhD in mathematics (ACO program).
    Working on Graphs Theoretic Aspects of Flexible Internet Models,
    and on Network Formation Games.

    Recent Courses

  • CS8802, Spring 05, Algorithms for Complex Networks.
  • CS1050A, Fall 07, Constructing Proofs.
  • CS7520 Spring 08, Approximation Algorithms.
  • CS4803 Fall 08, WWW: Science, Technology and Applications.

    • Selected Personal Pointers

  • Younger ones: Michel, 02, 04, 07, Lazos 07, similar ones: early 90s, and older ones: Instead of Memorial.
  • Collaze: A Preface, a POEM, another Poem, a course, Arnaud chez lui, chez lui, et chez nous, ladies in hats (I) and (II), NY, did you know?
  • Paeania (a.k.a. Peania or Paiania): snapshots from my desk and my desktop, apparently spanning three millenia. (1)In the antiquity Paeania was a ``demos'' (meaning group of people, same root as ``democracy'') belonging to the larger urban area of Athens. Here are some references: Plato, with some more text. Aristotle, and more text. Pausanias. (2)Here are some pictures taken between 1939 and 1944. (3)Today in Paeania there is major telecommunications and software industry, namely Intracom and the Athens Information Technology Research Center, the Alpha, Antenna and Mega TV channels, the Panathinaikos sports club, and, most recently, the new Athens International Airport. One can also visit the Vorres Museum (which used to have a Web site but apparently not anymore), and an Ornamental Stone Laboratory. Here the Wikipedia information for Paeania. Here is Paeania's own web site (in Greek).

    • 2138 Klaus Building
    266 Ferst Drive
    Georgia Institute of Technology
    Atlanta, Georgia 30332-0765
    Phone: 404-385-0617
    mailto:mihail@cc.gatech.edu