Fine-Grained Complexity and Algorithm Design Boot Camp 2015
2015-08-31..2015-09-04
Berkeley, United States
[Connections Between Algorithm Design and Complexity Theory, Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms, Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015), Proof Complexity and Meta-Mathematics 2023, Interactive Complexity 2018, Boolean Devices 2018]
| title | author | length |
|---|---|---|
| Satisfiability Algorithms I | Mohan Paturi | 01h 07m |
Shows that combinatorial facts about K-CNF drive both algorithms and lower bounds: the satisfiability decoding lemma proves any K-CNF has at most 2^{n(1-1/K)}… | ||
| Satisfiability Algorithms II | Mohan Paturi | 56m |
Proves nonconstructive lower bounds showing most degree‑2 GF(2) polynomials need size 2^{n−o(n)} for depth‑3 circuits when bottom fan‑in k = o(log n)… | ||
| Sparsification Lemma and ETH | Mohan Paturi | 55m |
Describes a concrete tool: the sparsification lemma that rewrites any k‑CNF, in 2^{εn} time, as a disjunction of linearly many linear‑size k‑CNFs while… | ||
| Exponential-Time Algorithms | Thore Husfeldt | 58m |
Survey of concrete exponential algorithms: branching recurrences give an Independent Set solver around 1.39^n and a simple 3‑coloring tweak knocks runtime to… | ||
| Computational Complexity of Polynomial Time Problems: Introduction | Virginia Vassilevska Williams | 01h 07m |
Overview of fine-grained complexity that pins down why many polynomial-time problems resist improvement: conjectures named are ETH/SETH, 3SUM, orthogonal… | ||
| Boolean Hardness to Randomization | Russell Impagliazzo | 01h 08m |
Shows a blueprint that converts a worst‑case hard Boolean function into a pseudorandom generator g so that any small circuit that distinguishes g’s outputs… | ||
| Circuit Analysis Algorithms | Ryan Williams | 01h 09m |
Session argues a concrete algorithm–lower-bound duality and gives a worked algorithm that beats brute force for several circuit classes: constant-depth ACC… | ||
| Recent Advances in FPT and Exact Algorithms for NP-Complete Problems | Dániel Marx | 01h 03m |
Dániel Marx, Hungarian Academy of Sciences
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/daniel-marx-2015-09-01 | ||
| Hardness for Graph Problems - Reductions Based on APSP and SETH | Virginia Vassilevska Williams | 59m |
Dense-case claim: APSP-equivalent to radius/median/eccentricities via fine-grained, sometimes adaptive reductions that build min-plus (distance) products and… | ||
| Derandomization to Boolean Circuit Lower Bounds | Russell Impagliazzo | 01h 02m |
Main claim: any general derandomization of probabilistic algorithms forces nontrivial nonuniform lower bounds, and conversely strong circuit lower bounds yield… | ||
| Circuit Complexity and Connections I | Ryan Williams | 58m |
Argues that small improvements in circuit algorithms yield provable lower bounds: a deterministic SAT speedup of roughly 2^n / n^10 already implies NEXP is not… | ||
| Parameterized Reductions | Dániel Marx | 01h 05m |
Dániel Marx, Hungarian Academy of Sciences
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/daniel-marx-2015-09-02 | ||
| The Easy Witness Lemma | Russell Impagliazzo | 01h 04m |
Shows that a weakening of Natural Proofs — a quasi‑natural property (constructive, nonempty but only occasionally large) — is essentially equivalent to circuit… | ||
| Circuit Complexity and Connections II | Ryan Williams | 01h 01m |
Shows concrete equivalences: faster algorithms for restricted circuit SAT give explicit circuit lower bounds, and conversely lower bounds yield derandomization… | ||
| Hardness for Sequence Problems - LCS and Frechet Distance | Virginia Vassilevska Williams | 55m |
Reduction from Orthogonal Vectors produces two sequences X,Y of length N·poly(d) (construction time N·poly(d)) so LCS, edit distance, DTW and Fréchet are… | ||
| Consequences of ETH: Tight Bounds for Various Problems | Dániel Marx, Ramamohan Paturi | 01h 10m |
Dániel Marx, Hungarian Academy of Sciences
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/daniel-marx-2015-09-03 | ||
| Proof of NEXP Not in ACC | Ryan Williams | 01h 10m |
Proves that showing a faster ACC-SAT algorithm yields circuit lower bounds: a subexponential-time SAT routine for constant-depth mod-m circuits implies some… | ||
| Hardness for Dynamic Problems; Conclusion and Future Research | Virginia Vassilevska Williams | 01h 00m |
Shows concrete reductions: maps an orthogonal vectors instance (n vectors in d dimensions) to a dynamic single‑source reachability instance with about n·d… | ||
| Connections Between Hardness and Randomness in the Algebraic Setting | Russell Impagliazzo | 01h 02m |
Shows that derandomizing low-formal-degree PIT is essentially equivalent to proving algebraic circuit lower bounds: a polynomial-size, low-degree algebraic… | ||
| Consequences of SETH: Tight Bounds for Some More Problems | Dániel Marx | 49m |
Dániel Marx, Hungarian Academy of Sciences
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/daniel-marx-2015-09-04 | ||
| nothing matches | ||