Henry Lin

Office: 645 Soda Hall

I have graduated from UC Berkeley and am now a research scientist at Columbia University.
I am no longer maintaining this website, please visit my new website at Columbia.

I completed my Ph.D. in 2009 in theoretical computer science at UC Berkeley.
My research was co-advised by Christos Papadimitriou and Satish Rao.
Previously, I graduated with a B.S. from Cornell University in 2003.

Publications and Manuscripts [ Show Details ]

• Network Routing, Network Flow, and Bipartite Matching
  

  Online Bipartite Matching with Augmentations.	[ Slides - INFOCOM 2009 ]
  Linked Decompositions, Internet Routing, and the Power of Choice in Polya Urns.	[ Slides - SODA 2008 ]
  Reducing Directed Max Flow to Undirected Max Flow.	[ Note ]

  
  
• Selfish Routing and Price of Anarchy in Networks
  

  A Stronger Bound on Braess's Paradox.	[ Slides - SODA 2004 ]
  Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability.	[ Slides - ICALP 2005 ]
  On the Price of Anarchy of a Network Creation Game.	[ Note ]

  
  
• Complexity and Cryptography
  On Hardness Amplification of One-Way Functions. [ In TCC 2005. ]
  
• Robust Optimization
  Robust Optimization of Contaminant Sensor Placement for Community Water Systems.
  [ In Mathematical Programming Series B, 2005. ]
  

Additional Information

Reference Links

• People Debate
• Theoretical Computer Science at Berkeley
• Bay Area Theory Symposium (BATS) 2008
• More Links

Standard disclaimer: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.