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.

• Recitation 1 (Homework expectations, Recurrences)
• Recitation 5 (Quiz 1 Review)
• Recitation 6 (Greedy Algs: Fractional Knapsack, File Merging)
• Recitation 7 (Shortest paths, DFS)
• Recitation 9 (Convex Hull)
• Recitation 10 (Applications of FFT)
• Recitation 11 (Matching)
• Recitation 12 (Reductions)

Publications

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.

Education

• Ph.D. candidate, Computer Science, Cornell, 2008-present.
• M.Eng., Electrical Engineering and Computer Science, MIT, 2008.
• B.S., Electrical Engineering and Computer Science, MIT, 2007.
• B.S., Mathematics, MIT, 2007.

Contact information

• Email: klai at cs cornell edu
• http://web.mit.edu/k_lai/www

Other Stuff

• SIPB, the Student Information Processing Board, which is devoted to improving computing at MIT.
• HMMT, the Harvard-MIT Math Tournament, a high school math tournament run entirely by Harvard and MIT students and gets more than 600 contestants each year. Seeing them descend on either Harvard or MIT (we switch locations each year) is always awe-inspiring.
• LSC, the Lecture Series Committee, which likes to project 35mm films and use the proceeds to bring interesting lectures to MIT. I held the position of Chairman for LSC for a year and was forever scarred (and probably bettered) by the experience.
• Random Hall, my undergraduate dormitory. I served as its Vice President/Treasurer (and got to handle many quarters) and was employed as its Desk Captain, where I oversaw the operation of the front desk. The more interesting part of the latter position was in the technical aspect of writing useful scripts.
• Expanding Your Horizons, a conference for 7th-9th grade girls where we hold workshops to show them cool stuff in math and science.
• Theory Discussion Group, Fall 2009 and Spring 2010. I co-organized the weekly Cornell theoretical computer science discussion group with Anna Blasiak.
• I also spend some of my spare time on nature photography, mostly in the Ithaca area.