EADS talk by Amir Abboud: Hardness in P

Title

Hardness in P

Abstract

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.

Biography

I am a fifth year PhD student at the Computer Science department at Stanford University. I am fortunate to have Virginia Vassilevska Williams as my advisor.

I have a broad interest in theoretical computer science. Most of my research has focused on the emerging subfield we call "Hardness in P" or "Fine-Grained Complexity" (see more details below).

Previously, I graduated with a B.Sc. from the "Etgar" program at University of Haifa, and with a M.Sc. from Technion.