Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
2015-11-06
Berkeley, United States
[Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015), Fine-Grained Complexity and Algorithm Design Boot Camp 2015, Interactive Complexity 2018, Connections Between Algorithm Design and Complexity Theory, ITCS 2023, Rigorous Evidence for Information-Computation Trade-offs]
| title | author | length |
|---|---|---|
| Fine-Grained Complexity of Exact Algorithms | Fedor Fomin | 57m |
Shows an ETH-based lower bound: G→H cannot be solved in |H|^{o(|G|)} time (unless ETH fails) via a reduction from 3‑coloring that groups R original vertices… | ||
| More Needles in the Hay Might Make it Harder to Find One? | Andreas Björklund | 24m |
Shows that few solutions can speed some NP-hard cases: directed Hamiltonian cycle maps cycles to parity of xyz vertex partitions and lists y-parts in expected… | ||
| Parameterized and Promised Streaming | MohammadTaghi Hajiaghayi | 37m |
Promised streaming assumes a bound K on the solution and gets space F(K)·polylog N instead of poly(N). Concrete results: a matching-based insertion algorithm… | ||
| Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reduc | Stefan Schneider | 59m |
Introduces a non-deterministic strong ETH variant and proves concrete non-reducibility: max flow and min-cost max flow admit linear-time nondeterministic and… | ||
| Lower Bound Results for Hard Problems Related to Finite Automata | Henning Fernau | 30m |
Shows ETH-based lower bounds for universality, inequivalence and intersection-nonemptiness on NFAs/DFAs by encoding SAT and 3-coloring into unary/bounded… | ||
| New Unconditional Lower Bounds for Algorithms and Enumeration Problems | Serge Gaspers | 31m |
Shows a matching lower bound for Scott and Sorkin’s max-2-CSP branching algorithm by building explicit graphs that force the LP/measure-and-conquer branching… | ||
| Fine-Grained Counting Complexity I | Holger Dell | 01h 02m |
Shows a concrete chain: counting 3D‑matching reduces to counting k‑matchings in bipartite graphs via a tiny gadget whose counts cancel mod p, recovers exact… | ||
| Dense Subset Sum May Be the Hardest | Jesper Nederlof | 33m |
Jesper Nederlof, Eindhoven University of Technology
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time… | ||
| Parameterized Inapproximability of Max k-Subset Intersection under ETH | Bingkai Lin | 30m |
Proves an FPT gap-producing reduction from k‑Clique to Max k‑Subset Intersection that maps a k input to a bipartite H with s = k^2 so that a k‑clique yields s… | ||
| Lower Bound Issues in Computational Social Choice | Rolf Niedermeier | 58m |
Gives concrete complexity boundaries: lobbying on voter-by-issue matrices is FPT via Lenstra-style ILP when parameterized by the maximum number of ones per… | ||
| Lower Bounds on the Running Time for Scheduling and Packing Problems | Klaus Jansen | 26m |
ETH-based reductions give concrete running-time barriers: a linear reduction from 3-SAT to Subset Sum produces 8m items and rules out 2^{o(n)} algorithms under… | ||
| On the Subexponential Time Complexity of the CSP | Iyad Kanj | 27m |
Detailed thresholds link structural parameters to sub-exponential solvability: if the number of tuples o(n) or the primal treewidth is sublinear then CSP is… | ||
| Exact Algorithms from FPT Algorithms | Daniel Lokshtanov | 01h 01m |
Shows a concrete way to turn any parameterized or local‑search algorithm running in C^k time into a faster exact algorithm for the full instance: pick a random… | ||
| Spotting Trees with Few Leaves | Łukasz Kowalik | 29m |
Claims an algebraic algorithm that generalizes Björklund algebraic method to detect a k-vertex tree with exactly l leaves, running in time that beats the old… | ||
| Fine-Grained Counting Complexity II | Radu-Cristian Curticapean | 01h 02m |
Classifies subgraph counting by the pattern class: if maximum matching size is bounded the problem is polynomial, otherwise counting is #W[1]-hard; proves… | ||
| Subexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds | Marcin Pilipczuk | 29m |
Survey states that many graph completion problems (split, chordal, proper-interval, several others) admit subexponential FPT algorithms by enumerating a… | ||
| Lower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems | Michał Pilipczuk | 33m |
Shows concrete conditional lower bounds for graph completion problems by tracing reductions from Gap 3SAT through Gap Max Cut and Optimum Linear Arrangement… | ||
| Lossy Kernelization | Saket Saurabh | 01h 04m |
Defines alpha-approximate kernel (polynomial-time reduction plus a solution lifting algorithm that turns any C-approximate solution of the reduced instance… | ||
| Color Coding-Related Techniques | Meirav Zehavi | 29m |
Gives a concise comparison of three concrete algorithmic tools: color coding (randomized k-colorings plus 2^k dynamic programming entries), divide and color… | ||
| Lower Bounds on the Space Complexity of Dynamic Programming | Peter Rossmanith | 38m |
Proves a formal space lower bound for dynamic programming on tree decompositions by switching to a one-way read-only input Turing model and constructing ~k·3^k… | ||
| Constructive Algorithm for Matroid Pathwidth | Eunjung Kim | 31m |
Provides a cubic-time algorithm that decides whether a represented matroid (n vectors over a fixed finite field) has pathwidth ≤ k and actually outputs a… | ||
| Engineering Motif Search for Large Graphs | Petteri Kaski | 31m |
Petteri Kaski, Aalto University
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time… | ||
| Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse | Michael Lampis | 33m |
Michael Lampis, Université Paris Dauphine
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time… | ||
| The Square Root Phenomenon in Planar Graphs -- Survey and New Results | Dániel Marx | 01h 06m |
Dániel Marx, Hungarian Academy of Sciences
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time… | ||
| Improved Deterministic Algorithms for Sparse Max-SAT | Rahul Santhanam | 29m |
Deterministic algorithms give explicit savings for sparse Max-SAT: savings Ω(n/c) (polynomial space) and savings n/√c (exponential space) for formulas with m =… | ||
| Towards General and Tight Hardness Results for Graph Problems | Christian Komusiewicz | 23m |
Shows specific reductions and constructions that give tight exponential lower bounds: a reduce from vertex cover on subcubic graphs using an alpha-sequence… | ||
| An Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space | Yijia Chen | 29m |
Shows a concrete mapping—called the miniaturization isomorphism—that turns a classical problem with size measure μ into a parameterized problem whose parameter… | ||
| Lower Bounds for Problems Parameterized by Clique-width | Petr Golovach | 25m |
Claim: several classic problems (Dominating Set, Independent Set, Hamiltonian Cycle, Feedback Vertex Set) admit no algorithms of form 2^{o(k)}·n^{O(1)} when… | ||
| Faster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC^0[p] | Suguru Tamaki | 31m |
Randomized algorithm solves SysPol_q on degree-k instances in time q^{n (1 - 1/O(q^k))}, giving 0.868765^n for GF(2), and for prime q the counting version… | ||
| From Channel Assignment to Subgraph Isomorphism | Arkadiusz Socała | 17m |
Shows a concrete compression that encodes n bits into k log k via merging permutations, producing channel-assignment instances of size roughly n / log n and… | ||
| nothing matches | ||