Katherine J. Lai

I am currently working at DNAnexus while on leave from the PhD program at Cornell. My PhD advisor is Prof. Carla Gomes, whom I have worked with on combinatorial optimization problems as they arise in computational sustainability applications, particularly in wildlife corridor design. I was previously an undergraduate and then an M.Eng. student (as part of a 5-year program) at MIT working on problems in theoretical computer science. My Master's advisor was Prof. Erik Demaine. My research interests include but are not limited to graph algorithms, combinatorial optimization, approximation algorithms, and other cool algorithms in general.

I TA-ed for 6.854J/18.415J: Advanced Algorithms Fall 2007 and for 6.046: Design and Analysis of Algorithms Spring 2008.

Old 6.046 Handouts: Feel free to use them if you find them useful.


  1. Katherine J. Lai, Carla P. Gomes, Michael K. Schwartz, Kevin S. McKelvey, David E. Calkin, and Claire A. Montgomery. The Steiner Multigraph Problem: Wildlife Corridor Design for Multiple Species. In Proceedings of the Twenty-Fifth Conference on Artificial Intelligence, Special Track on Computational Sustainability and AI. (AAAI-11) 2011. Full version here.
  2. Bistra Dilkina, Katherine J. Lai, and Carla P. Gomes, Upgrading Shortest Paths in Networks. In the Proceedings of the 8th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2011), 2011, pages 76-91.
  3. Katherine J. Lai, Complexity of Union-Split-Find Problems. M.Eng. thesis, Department of Electrical Engineering and Computer Science, MIT, 2008.
  4. Timothy G. Abbott, Katherine J. Lai, Michael R. Lieberman, Eric C. Price, Browser-Based Attacks on Tor, In the Proceedings of the 7th International Symposium on Privacy Enhancing Technologies (PET 2007), Ottawa, Canada, 2007, pages 184-199.


Contact information

Other Stuff

I used to and/or currently spend time on the following MIT and Cornell organizations/activities in some manner or another: