AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for decision problems in P (Gao, Impagliazzo, Kolokolova, Williams, TALG 2019) as well as the classic class MaxSNP and MaxSNP-completeness for NP optimization problems (Papadimitriou, Yannakakis, JCSS 1991), we define polynomial-time analogues MaxSP and MinSP, which contain many optimization problems in P, including Maximum Inner Product, general forms of nearest neighbor search and optimization variants of the k-XOR problem.

Our main result shows that (a sparse variant of) Maximum Inner Product is complete for MaxSP under fine-grained reductions. This completeness implies some interesting consequences for hardness of approximation, and gives mild algorithmic improvements for all problems in the class.

This is joint work with Karl Bringmann, Nick Fischer and Marvin Künnemann

Roohani Sharma

+49 681 9325 0

Zoom

527 278 8807

public

For people outside D1 interested in listening to this talk, please contact Roohani Sharma at rsharma@mpi-inf.mpg.de for the password.