The problem of maximum flow is a well-known optimization problem in graph theory with wide-ranging applications and a source of exciting open problems. Despite the presence of many different algorithms for computing max-flow, as well as fast approximation algorithms, nobody has yet achieved an algorithm with linear run-time. This problem is conjectured to be impossible, but frustratingly, nobody has yet proved a lower bound better than the trivial lower bound of Omega(E). I will use the little-used method of exponential reduction from NP-hard problems to find a non-trivial lower bound for maximum flow.

I worked with Dr. Misha Chertkov at LANL for two summers where we worked on methods for computing matrix permanents. I did a UROP with Prof. Shah in which I studied new methods for interpreting customer data from the Ford motor company. I worked with Prof. Jean-Phillippe Bouchaud at a finance company in Paris where I studied applications of LQR methods to portfolio optimization.