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