The Taub Faculty of Computer Science Events and Talks

The class P attempts to capture the efficiently solvable computational tasks. It is full of practically relevant problems, with varied and fascinating combinatorial structure. In this talk, I will give an overview of a rapidly growing body of work that seeks a better understanding of the structure within P. Inspired by NP-hardness, the main tool in this approach are combinatorial reductions. Combining these reductions with a small set of plausible conjectures, we obtain tight lower bounds on the time complexity of many of the most important problems in P. Short Bio: Amir is a Computer Science Ph.D. student in the Theory group at Stanford University. His dissertation is on understanding the computational complexity of basic and fundamental problems. He also works on topics such as Graph Sparsification and Distributed Computing in which he has won Best Student Paper awards at STOC 2016 and DISC 2016. Previously, he obtained an M.Sc. degree at the Technion, and a B.Sc. degree in the "Etgar" program at the University of Haifa.