Efficient Enumeration Algorithms via Circuits

on YouTube ↗44m

" summary

Presents concrete algorithms that enumerate satisfying assignments of structured set-circuits (d-DNNF variants) with linear preprocessing and output-linear delay (constant delay when answers have bounded size), plus a conversion route from Boolean d-DNNFs if smoothed; supports incremental relabeling updates in logarithmic time (some update claims currently conditional on a revised proof); applies to MSO on trees, document-spanner regex captures with preprocessing and delay polynomial in the automaton, and to unambiguous annotated grammars (cubic preprocessing).

AI-written summary · about

" chapters (8)

1. 0:00Introduction to the topic
2. 2:48Enumeration and complexity
3. 5:29Knowledge compilation
4. 7:07Set circuit formalism
5. 12:17Main enumeration results
6. 15:30Proof and algorithmic details
7. 28:21Applications and extensions
8. 37:16Future work and discussion

" related talks

• 32mCircuits for Querying Trees: A Little SurveyPierre Bourhis · Logic and Algebra for Query Evaluation 2023
• 41mOptimizing Relational Programs IRemy Wang · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 01h 24mIntroduction to Constraint Logic ProgrammingSergii Dymchenko · LambdaConf 2015
• 01h 08mAlgebraic Structures in Logic and Query Evaluation 4Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: INofar Carmeli · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 01h 02mAlgebraic Structures in Logic and Query Evaluation 3Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 36mOptimizing Relational Programs IIRemy Wang · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 19mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: IINofar Carmeli · Fine-Grained Complexity, Logic, and Query Evaluation 2023