Henry Lin

Office: 645 Soda Hall

I am a Ph.D. candidate studying theoretical computer science at UC Berkeley.
I started graduate school in Fall 2003, and I am co-advised by Christos Papadimitriou and Satish Rao.

Publications and Manuscripts [ Show Details ]

• Network Routing, Network Flow, and Bipartite Matching
  

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

  
  
• 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.