Amir Abboud, Weizmann Institute of Science

Abstract

The talk will overview challenges in the fine-grained complexity of approximation in P and what we know about them so far. A large number of conditional lower bounds have been established in the last decade under a small number of core conjectures. Whether similar lower bounds hold for the approximate versions of these problems is often a meaningful open question. It is natural to seek “gap versions” of the core conjectures, as well as “gap amplification” techniques that relate a conjecture to its gap version. The talk will discuss the extent to which this has been accomplished for each conjecture.