About
During the last decade, it has been recognized that the complexity assumption known as the (Strong) Exponential Time Hypothesis on satisfiability can explain the complexity of a large number of computational problems in a tight way, showing the optimality of known algorithms. This connection has transformed the field of parameterized complexity by refining the question of which problems are fixed-parameter tractable to a fine-grained optimality program that tries to determine the best possible running time for all problems. Recent results show that such an understanding is possible for a wide range of problems, but there are still no tight bounds in many cases. This indicates that further work is needed on understanding the complexity assumptions related to satisfiability, transferring these lower bounds to various specific problem domains, and obtaining matching algorithmic upper bounds. The goal of the workshop is to bring together researchers from satisfiability, classical computational complexity, parameterized complexity and algorithm design to present recent results in these areas and initiate a discussion on connections between the complexity of satisfiability and the fine-grained complexity of other problems, and their implications for algorithm design.
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), Nikhil Bansal (TU Eindhoven), Paul Beame (University of Washington), Andreas Björklund (Lund University), Greg Bodwin (Stanford University), Karl Bringmann (ETH Zürich), Yixin Cao (Hong Kong Polytechnic University), Marco Carmosino (UC San Diego), Brynmor Chapman (Stanford University), Yijia Chen (Fudan University), Radu Curticapean (Universität des Saarlandes), Holger Dell (Universität des Saarlandes), Uri Feige (Weizmann Institute), Michael Fellows (Charles Darwin University), Henning Fernau (Universität Trier), Fedor Fomin (University of Bergen), Anna Gál (UT Austin), Nicola Galesi (Sapienza University Rome), Serge Gaspers (University of New South Wales), Petr Golovach (University of Bergen), Gregory Gutin (Royal Holloway, University of London), Johan Hastad (KTH), MohammadTaghi Hajiaghayi (University of Maryland), Monika Henzinger (University of Vienna), Thore Husfeldt (IT University of Copenhagen), Russell Impagliazzo (UCSD), Klaus Jansen (Universität Kiel), Valentine Kabanets (Simon Fraser University), Iyad Kanj (DePaul University), Petteri Kaski (Aalto University), Eunjung Kim (CNRS/Paris Dauphine University), Mikko Koivisto (University of Helsinki), Antonina Kolokolova (Memorial University of Newfoundland), Christian Komusiewicz (Technische Universität Berlin), Guy Kortsarz (Rutgers University), Lukasz Kowalik (University of Warsaw), Sebastian Krinninger (University of Vienna), Michael Lampis (Université Paris Dauphine), Chin Ho Lee (Northeastern University), Binkai Lin (University of Tokyo), Daniel Lokshtanov (University of Bergen), Dániel Marx (Hungarian Academy of Sciences), Ivan Mikhailin (UC San Diego), Jesper Nederlof (Eindhoven University of Technology), Rolf Niedermeier (Technische Universität Berlin), Vangelis Paschos (Université Paris Dauphine), Mohan Paturi (UC San Diego), Geevarghese Philip (Chennai Mathematical Institute), Michal Pilipczuk (University of Warsaw), Marcin Pilipczuk (University of Warsaw), Aaron Potechin (Massachusetts Institute of Technology), Frances Rosamond (Charles Darwin University), Peter Rossmanith (RWTH Aachen), Barna Saha (University of Massachusetts Amherst), Rahul Santhanam (University of Edinburgh), Saket Saurabh (Institute of Mathematical Sciences), Tasos Sidiropoulos (Ohio State University), Arkadiusz Socala (University of Warsaw), Srikanth Srinivasan (Indian Institute of Technology Bombay), Suguru Tamaki (Kyoto University), Robert Tarjan (Princeton University), Seeun William Umboh (Eindhoven University of Technology), Virginia Vassilevska Williams (Stanford University), Emanuele Viola (Northeastern University), Ryan Williams (Stanford University), Meirav Zehavi (Technion Israel Institute of Technology)