Fine-Grained Complexity, Logic, and Query Evaluation 2023
2023-09-22..2023-09-28
Berkeley, United States
who it's for
database researchers, algorithms researchers, distributed systems researchers, theoretical computer scientists, query engine engineers, Datalog researchers, data engineers
topics
conjunctive query enumeration; free-connex acyclic queries; triangle hardness reductions; relational linear regression; sum-product queries and variable elimination; MPC joins and load bounds; round-vs-load MPC tradeoffs; incremental view maintenance beyond worst-case; equality saturation for program optimization; algebraic Datalog evaluation with semirings; sparse-recovery for graph distances
| title | author | length |
|---|---|---|
| Accessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: I | Nofar Carmeli | 01h 09m |
Defines when answer enumeration achieves linear preprocessing and constant delay for conjunctive queries: acyclic, no-self-join queries admit a two-pass… | ||
| Accessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: II | Nofar Carmeli | 19m |
Acyclic conjunctive queries that are free-connex admit linear preprocessing and constant-delay enumeration, while acyclic but not free-connex queries are hard… | ||
| Fine Grained Complexity | Andrea Lincoln | 54m |
Motivation and concrete claims: 3SUM conjecture states 3SUM requires n^2−o(1) on n integers, orthogonal vectors resists n2−o(1) algorithms for d≈log^2 n, and… | ||
| Introduction to Relational Algorithms | Mahmoud Abo Khamis | 01h 05m |
Defines relational linear regression that computes the covariance matrix Σ, vector c and scalar s directly from input tables S, P, C without materializing the… | ||
| Intermediate Relational Algorithm Design | Kirk Pruhs | 44m |
Relational-algorithms assume inputs stay in relational form and claim most useful operations reduce to sum-product queries; the talk shows concrete reductions… | ||
| Massively Parallel Evaluation of Relational Queries I | Xiao Hu, Paris Koutris | 47m |
Massively parallel relational evaluation uses the BSP/MPC model with p servers, r rounds and maximum load L; concrete one‑round algorithms use randomized… | ||
| Massively Parallel Evaluation of Relational Queries II | Xiao Hu, Paris Koutris | 39m |
Shows a precise round-vs-load tradeoff: for path queries diameter k the load falls from N/p^{1/4} with one round toward N/p as rounds increase, and achieving… | ||
| Distributed Graph Techniques in the MPC Model | Quanquan C. Liu | 46m |
Defines an MPC graph model with M machines, space per machine S, and measures rounds and total near‑linear space, then shows two concrete techniques. Round… | ||
| Optimizing Relational Programs I | Remy Wang | 41m |
Tool builds a compact tree automaton that encodes many equivalent programs by merging states for equal subexpressions, grows it by applying rewrite rules until… | ||
| Optimizing Relational Programs II | Remy Wang | 36m |
Proposes concrete methods to evaluate recursive Datalog by mapping relations to vectors/matrices over closed semirings and computing fixpoints with algebraic… | ||
| Fine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems | Karl Bringmann | 52m |
Graphs reachability and shortest-paths reduce to specific matrix products: transitive closure is equivalent to Boolean matrix multiplication and APSP to… | ||
| Incremental View Maintenance: Beyond Worst-Case Analysis I | Xiao Hu | 38m |
Focuses on achieving constant-delay enumeration for conjunctive queries by replacing join materialization with layered semi-joins and projections, storing… | ||
| Incremental View Maintenance: Beyond Worst-Case Analysis II | Xiao Hu | 26m |
Defines a join-tree-based enclosureness that measures effective lifespans in a generalized join tree and claims any free-connex conjunctive query can be… | ||
| nothing matches | ||