Connections Between Algorithm Design and Complexity Theory
2015-09-28..2015-10-01
Berkeley, United States
[Fine-Grained Complexity and Algorithm Design Boot Camp 2015, Boolean Devices 2018, Interactive Complexity 2018, Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms, Neo-Classical Methods in Discrete Analysis 2013, Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015)]
| title | author | length |
|---|---|---|
| Human Computation | Manuel Blum | 55m |
Defines formal “humanly computable” algorithms with tight time budgets: preprocessing up to two hours, generation ≤60s (preferably 30s), and step costs… | ||
| Explicit Two-Source Extractors and Resilient Functions | David Zuckerman | 45m |
Constructs an explicit two-source extractor that works for polylogarithmic min-entropy by combining a seeded non-malleable extractor (cycle over seeds to get… | ||
| On the Power of Gradually Increasing Independence | Parikshit Gopalan | 46m |
An iterative PRG method breaks a hard global test into stages that reduce dimension (n → √n → …) and increases independence at each stage so that a k-wise… | ||
| Anti-Concentration for Polynomials of Independent Random Variables | Raghu Meka | 17m |
Gives an explicit anti‑concentration bound: for a degree‑d real polynomial whose rank = number of disjoint degree‑d monomials equals r, the mass on any single… | ||
| Lower Bounds by Birkhoff Interpolation | Pascal Koiran | 17m |
Shows explicit univariate lower bounds for representing polynomials as sums of powers of linear forms, proving linear-size barriers under natural exponent… | ||
| Sublinear Space Complexity | Osamu Watanabe | 11m |
Examines reachability in graphs under tight memory budgets and claims concrete tradeoffs rather than vague promises: it gives a polynomial‑time algorithm for… | ||
| Local Reductions | Emanuele Viola | 43m |
Proves a concrete reduction from a time-t computation to 3SAT formulas of quasi-linear size whose clause for index i is computable by a function depending on… | ||
| Getting Harder All the Time? | Omer Reingold | 18m |
Survey of two concrete research directions: one studies proof-of-work style puzzles that are only moderately hard — intended bounds here are explicit upper and… | ||
| Derandomization via Robust Algebraic Circuit Lower Bounds | Michael Forbes | 17m |
Shows that depth-3 powering formulas imply a deterministic black-box identity test by turning a known exponential lower bound for the monomial x1 x2 ... xn… | ||
| Graph Automorphism and Circuit Size | Eric Allender | 17m |
Shows Graph Automorphism in ZPP relative to the KT/ MKT oracle by reducing rigid-instance isomorphism to a KT-complexity gap: encode T random permutations into… | ||
| On the Existence of Optimal Algorithms | Boaz Barak | 50m |
Proposes sum of squares as a candidate “universal” algorithmic template: optimize over degree-d pseudo-distributions (convex, solvable in n^d time) that… | ||
| A Compression Algorithm for AC^0[p] Circuits Using Certifying Polynomials | Srikanth Srinivasan | 49m |
Algorithm compresses Boolean truth tables that have small AC^0[p] circuits into circuits of size about 2^n / m where m = exp(Ω(n / polylog n)) for constant… | ||
| Approaches to Bounding the Exponent of Matrix Multiplication | Chris Umans | 54m |
Survey of specific progress and a new direction: Strassen’s 2x2 decomposition gives seven multiplications (ω ≤ 2.81), repeated tensor powers and the… | ||
| QBF Satisfiability Algorithms and Connections with Circuit Lower Bounds | Rahul Santhanam | 46m |
Gives a concrete algorithmic tradeoff: for QBF with k quantifier blocks over CNFs or small formulas the procedure achieves savings Ω(n^{1/(k+1)}) by splitting… | ||
| Satisfiability Algorithms for Small Depth Circuits with Symmetric Gates | Suguru Tamaki | 42m |
Deterministic algorithm counts satisfying assignments for AC0 circuits that have a subpolynomial number t(n) of weighted symmetric gates with maximum gate… | ||
| Probabilistic Polynomials and Hamming Nearest Neighbors | Joshua Alman | 35m |
Claims an offline algorithm for n batch Hamming nearest neighbors that is truly subquadratic when d = c log n: time n^{2 - 1/O(c log^2 c)} for constant c, by… | ||
| Generalizations of the Gate Elimination Method | Alexander Kulikov | 18m |
Proves a circuit lower bound route: starting from the classic gate elimination idea, constructs a XOR-layered and sometimes cyclic circuit normal form, then… | ||
| Addition is Exponentially Harder than Counting for Shallow Monotone Circuits | Igor Oliveira | 15m |
Defines U_d_n as d n‑bit numbers whose sum is at least 2^n, a monotone function represented by a single threshold gate. Proves any depth-d monotone majority… | ||
| Satisfiability Algorithms Based on Concentrated Shrinkage | Ruiwen Chen | 17m |
Shows how concentrated shrinkage and a greedy restriction that repeatedly fixes the most frequent variable turn worstcase formula lower bound analyses into… | ||
| nothing matches | ||