Logic and Algorithms in Database Theory and AI Boot Camp
2023-08-21..2023-08-24
Berkeley, United States
as the organisers put it
This program studies the interaction between logic and the algorithms that they inspire, with applications to databases, complexity theory, and knowledge representation.
who it's for
database researchers, theoretical computer scientists, database systems engineers, probabilistic modeling researchers, knowledge representation researchers, algorithm designers, provenance and data lineage engineers
topics
worst-case optimal join algorithms; entropic and polymatroid bounds; variable elimination tensor decomposition; instance optimal query evaluation; probabilistic circuits decomposability; structured decomposability and vtrees; semiring provenance polynomials; compiling Bayesian networks to circuits; fine-grained complexity hypotheses; PANDA heavy/light partitioning; factorized query representations; reductions from orthogonal vectors to graphs
| title | author | length |
|---|---|---|
| Query Optimization and Evaluation 1: Output Size Bounds and Information Theory | Hung Ngo | 57m |
Covers how to turn degree statistics into provable output-size upper bounds using information theory and linear programming, then links those bounds to… | ||
| Query Optimization and Evaluation 2: Worst-Case Optimal Join Algorithms | Hung Ngo | 01h 05m |
Three classes of worst‑case approaches appear: JAAT, VAAT, IAAT (join‑at‑a‑time, variable‑at‑a‑time, inequality‑at‑a‑time). The paper proves VAAT meets the… | ||
| Query Optimization and Evaluation 3: Variable Elimination and Tensor Decomposition | Hung Ngo | 01h 03m |
Introduces a concrete plan: represent aggregation as sum-product queries, build a compact intermediate (factorized/tensor) representation via variable… | ||
| Query Optimization and Evaluation 4: Instance Optimality | Mahmoud Abo Khamis | 01h 10m |
Covers instance optimality for query evaluation with concrete claims, tools and limits: defines comparison and gap/box certificates, reduces joins to a… | ||
| Logic and Probabilistic Circuits 1 | Guy Van den Broeck | 01h 05m |
Main claim: represent probability models as layered computation graphs so many queries become provably efficient when the circuit enforces decomposability… | ||
| Logic and Probabilistic Circuits 2 | YooJung Choi | 01h 03m |
Probabilistic circuits use decomposability and smoothness to push integrals down to leaves and compute marginals by dynamic programming in linear time, with… | ||
| Logic and Probabilistic Circuits 3 | YooJung Choi | 01h 00m |
Defines SDD-style circuits with structured decomposability and a stronger partition (strong) determinism, proves that computing P(formula) requires compiling… | ||
| Logic and Probabilistic Circuits 4 | Guy Van den Broeck | 01h 01m |
Computing a log of a probabilistic circuit requires log requires determinism because otherwise output loses determinism and the problem becomes NP‑hard; the… | ||
| Algebraic Structures in Logic and Query Evaluation 1 | Val Tannen | 01h 06m |
Semiring-based provenance treats input tuple labels as algebraic tokens and computes provenance polynomials that record exact derivations and multiplicities… | ||
| Algebraic Structures in Logic and Query Evaluation 2 | Val Tannen | 01h 05m |
Semiring-based provenance unifies many prior notions by mapping complex annotations in a semiring of polynomials down to simpler forms via surjective… | ||
| Fine-Grained Complexity 1 | Virginia Vassilevska Williams | 01h 00m |
Fine-grained complexity pins concrete running-time hypotheses (SETH: no 2^{n(1−ε)} SAT, 3SUM: no n^{2−o(1)}, APSP: no n^{3−o(1)}) and proves many practical… | ||
| Fine-Grained Complexity 2 | Nicole Wein | 01h 03m |
Shows a concrete reduction from orthogonal vectors to diameter that makes a 3/2‑approximation barrier precise: build vertices for sets and universe elements… | ||
| Algebraic Structures in Logic and Query Evaluation 3 | Dan Suciu | 01h 02m |
Extends Datalog from sets to partially ordered pre-semirings and shows how monotone rules map to a semiring semantics via the immediate consequence operator… | ||
| Algebraic Structures in Logic and Query Evaluation 4 | Dan Suciu | 01h 08m |
Explains that datalog evaluation over semirings reduces to grounded systems of polynomial equations whose solutions are provenance power series, shows simple… | ||
| Fine-Grained Complexity 3 | Virginia Vassilevska Williams | 01h 07m |
Shows simple reductions that turn OV/3OV/OMv assumptions into tight dynamic lower bounds: single-source reachability, SCC count and diameter each get nd =… | ||
| Fine-Grained Complexity 4 | Yinzhan Xu | 58m |
Covers fine grained hardness for k‑clique detection and listing, gives the fastest known upper bounds using fast matrix multiplication (assume ω = 2 so… | ||
| Incremental View Maintenance 1 | Dan Olteanu | 01h 08m |
Presents a concrete maintenance strategy for triangle queries that splits each relation into heavy/light partitions, materializes a few pairwise joins as… | ||
| Incremental View Maintenance 2 | Dan Olteanu | 01h 05m |
Shows which conjunctive queries admit true constant-time single-tuple updates and constant enumeration delay: q-hierarchical queries do, and queries that… | ||
| Sampling in Query Evaluation 1 | Marcelo Arenas | 01h 06m |
Shows that counting join answers is #P-complete and uniform random generation in general collapses complexity (polynomial-time uniform generation implies NP =… | ||
| Sampling in Query Evaluation 2 | Marcelo Arenas | 01h 06m |
Describes a concrete sampling pipeline for joins that uses the Horvitz-Thompson estimator on join trees: sample tuples down the tree, accept with probabilities… | ||
| nothing matches | ||