About
Despite the widely demonstrated usefulness of the notion of NP-hardness, there are many situations in which it is not applicable. This is the case, for example, when the goal is to show hardness of problems that are known to have polynomial time solutions. For instance, in the context of massive data computation even a quadratic-time algorithm is considered inefficient, but for many interesting problems no sub-quadratic algorithms are known. It would be of great interest to give complexity-theoretic evidence that no such algorithms exist at all. Mimicking NP-hardness, one would want to say that a problem is hard because if it had a sub-quadratic time algorithm, then many other important problems would have such algorithms as well.
To this end, one needs more refined notions of reducibility between problems that preserve a designated running time. Such reductions (for sub-quadratic, sub-cubic and near-linear runtimes) have been found in a number of isolated contexts: between problems in computational geometry, combinatorial pattern matching and problems related to shortest paths in graphs. However, the overarching framework is still mostly missing. The purpose of the workshop is to bring together researchers interested in these questions, in order to share their insights and develop a future research agenda. One of the outcomes of the workshop will be a list of key open problems in the field.
All talks will be recorded. Enquiries may be sent to the organizers at this address.
Chairs/Organizers
Invited Participants
Amir Abboud (Stanford University), Dimitris Achlioptas (UC Santa Cruz), Josh Alman (Stanford University), Alexandr Andoni (UC Berkeley), Nikhil Bansal (TU Eindhoven), Paul Beame (University of Washington), Greg Bodwin (Stanford University), Karl Bringmann (ETH Zürich), Marco Carmosino (UC San Diego), Timothy Chan (University of Waterloo), Brynmor Chapman (Stanford University), Shiri Chechik (Tel Aviv University), Raphael Clifford (University of Bristol), Radu Curticapean (Universität des Saarlandes), Marek Cygan (University of Warsaw), Holger Dell (Universität des Saarlandes), Erik Demaine (Massachusetts Institute of Technology), Jeff Erickson (University of Illinois, Urbana-Champaign), Fedor Fomin (University of Bergen), Nicola Galesi (Sapienza University Rome), Fabrizio Grandoni (IDSIA, University of Lugano), Johan Hastad (KTH), Sariel Har-Peled (University of Illinois, Urbana-Champaign), Monika Henzinger (University of Vienna), Thore Husfeldt (IT University of Copenhagen), Russell Impagliazzo (UCSD), Piotr Indyk (Massachusetts Institute of Technology), Marvin Künnemann (Max Planck Institut für Informatik), Valentine Kabanets (Simon Fraser University), Petteri Kaski (Aalto University), Eunjung Kim (CNRS/Paris Dauphine University), Valerie King (University of Victoria), Mikko Koivisto (University of Helsinki), Antonina Kolokolova (Memorial University of Newfoundland), Tsvi Kopelowitz (University of Michigan), Sebastian Krinninger (University of Vienna), Kasper Larsen (Aarhus University), Chin Ho Lee (Northeastern University), Moshe Lewenstein (Bar-Ilan University), Jingcheng Liu (UC Berkeley), Aleksander Mądry (MIT), Dániel Marx (Hungarian Academy of Sciences), Ivan Mikhailin (UC San Diego), Danupon Nanongkai (KTH Royal Institute of Technology), Jesper Nederlof (Eindhoven University of Technology), Ramamohan Paturi (UC San Diego), Seth Pettie (University of Michigan), Marcin Pilipczuk (University of Warsaw), Toniann Pitassi (University of Toronto), Aaron Potechin (Massachusetts Institute of Technology), Vijaya Ramachandran (University of Texas, Austin), Liam Roditty (Bar-Ilan University), Aviad Rubinstein (UC Berkeley), Manuel Sabin (UC Berkeley), Barna Saha (University of Massachusetts Amherst), Rahul Santhanam (University of Edinburgh), Srikanth Srinivasan (Indian Institute of Technology Bombay), Robert Tarjan (Princeton University), Mikkel Thorup (University of Copenhagen), Seeun William Umboh (Eindhoven University of Technology), Virginia Vassilevska Williams (Stanford University), Emanuele Viola (Northeastern University), Oren Weinmann (University of Haifa), Ryan Williams (Stanford University), David Woodruff (IBM Almaden)