Workshops

Fall 2015

Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms

Nov 2, 2015 to Nov 6, 2015

Return to event »

Click on the titles of individual talks for abstract, slides and archived video (available approximately one week after the conclusion of the workshop).

Please note that this schedule is subject to change. All events take place in the Calvin Lab Auditorium.

Monday, November 2nd, 2015
9:00 am–9:20 am		Coffee and Check-In
9:20 am–9:30 am		Opening Remarks
9:30 am–10:30 am		Fine-Grained Complexity of Exact Algorithms Fedor Fomin, University of Bergen
10:30 am–11:00 am		Break
11:00 am–11:30 am		More Needles in the Hay Might Make it Harder to Find One? Andreas Björklund, Lund University
11:30 am–12:00 pm		Parameterized and Promised Streaming MohammadTaghi Hajiaghayi, University of Maryland
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility Stefan Schneider, UC San Diego
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		Lower Bound Results for Hard Problems Related to Finite Automata Henning Fernau, University of Trier
4:00 pm–4:30 pm		New Unconditional Lower Bounds for Algorithms and Enumeration Problems Serge Gaspers, University of New South Wales
4:30 pm–5:30 pm		Reception

Tuesday, November 3rd, 2015
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Fine-Grained Counting Complexity I Holger Dell, Universität des Saarlandes
10:30 am–11:00 am		Break
11:00 am–11:30 am		Dense Subset Sum May Be the Hardest Jesper Nederlof, Eindhoven University of Technology
11:30 am–12:00 pm		Parameterized Inapproximability of Max k-Subset Intersection under ETH Bingkai Lin, University of Tokyo
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Lower Bound Issues in Computational Social Choice Rolf Niedermeier, TU Berlin
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		Lower Bounds on the Running Time for Scheduling and Packing Problems Klaus Jansen, Department of Computer Science, University of Kiel
4:00 pm–4:30 pm		On the Subexponential Time Complexity of the CSP Iyad Kanj, DePaul University

Wednesday, November 4th, 2015
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Exact Algorithms from FPT Algorithms Daniel Lokshtanov, University of Bergen
10:30 am–11:00 am		Break
11:00 am–11:30 am		Optimal Running Times for Exact and Approximation Algorithms Guy Kortsarz, Rutgers Camden
11:30 am–12:00 pm		Spotting Trees with Few Leaves Łukasz Kowalik, University of Warsaw
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Fine-Grained Counting Complexity II Radu-Cristian Curticapean, Universität des Saarlandes
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		Subexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds Marcin Pilipczuk, University of Warsaw
4:00 pm–4:30 pm		Lower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems Michał Pilipczuk , University of Warsaw

Thursday, November 5th, 2015
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Lossy Kernelization Saket Saurabh, IMSc + UIB
10:30 am–11:00 am		Break
11:00 am–11:30 am		Color Coding-Related Techniques Meirav Zehavi, Tel Aviv University
11:30 am–12:00 pm		Lower Bounds on the Space Complexity of Dynamic Programming Peter Rossmanith, RWTH Aachen
12:00 pm–2:00 pm		Lunch
2:00 pm–2:30 pm		Constructive Algorithm for Matroid Pathwidth Eunjung Kim, CNRS/Paris Dauphine University
2:30 pm–3:00 pm		Engineering Motif Search for Large Graphs Petteri Kaski, Aalto University
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse Michael Lampis, Universite Paris Dauphine

Friday, November 6th, 2015
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		The Square Root Phenomenon in Planar Graphs -- Survey and New Results Dániel Marx, Hungarian Academy of Sciences (MTA SZTAKI)
10:30 am–11:00 am		Break
11:00 am–11:30 am		Improved Deterministic Algorithms for Sparse Max-SAT Rahul Santhanam, University of Edinburgh
11:30 am–12:00 pm		Towards General and Tight Hardness Results for Graph Problems Christian Komusiewicz, Technische Universität Berlin
12:00 pm–2:00 pm		Lunch
2:00 pm–2:30 pm		An Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space Yijia Chen, Fudan University
2:30 pm–3:00 pm		Lower Bounds for Problems Parameterized by Clique-width Petr Golovach, University of Bergen
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		Faster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC^0[p] Suguru Tamaki, Kyoto University
4:00 pm–4:30 pm		From Channel Assignment to Subgraph Isomorphism Arkadiusz Socała, University of Warsaw