Adam  Yedidia

Adam Yedidia

Scholar Title

MIT EECS Undergraduate Research and Innovation Scholar

Research Title

Finding Lower Bounds for Flow Using Exponential Reductions




Dana Moshkovitz


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.

Back to Scholars