Cover Image

Lower Bounds for Conjunctive Query Evaluation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Mengel, Stefan
Format:	Preprint
Published:	2025
Subjects:	Databases Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tight Fine-Grained Bounds for Direct Access on Join Queries
by: Bringmann, Karl, et al.
Published: (2022)

Diversity of Answers to Conjunctive Queries
by: Merkl, Timo Camillo, et al.
Published: (2023)

Towards Parameterized Hardness on Maintaining Conjunctive Queries
by: Wang, Qichen
Published: (2026)

Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
by: Khamis, Mahmoud Abo, et al.
Published: (2026)

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
by: Focke, Jacob, et al.
Published: (2021)

Parameterised Complexity of Consistent Query Answering via Graph Representations
by: Hankala, Teemu, et al.
Published: (2024)

Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability
by: Chen, Hubie, et al.
Published: (2023)

PFCS: Prime Factorization Cache System for Deterministic Data Relationship Discovery
by: Le, Duy
Published: (2025)

Circuits and Formulas for Datalog over Semirings
by: Fan, Austen Z., et al.
Published: (2025)

The Complexity of Finding Missing Answer Repairs
by: Comer, Jesse, et al.
Published: (2026)

Query Lower Bounds for Correlation Clustering under Memory Constraints
by: Garg, Sumegha, et al.
Published: (2026)

Optimally Rewriting Formulas and Database Queries: A Confluence of Term Rewriting, Structural Decomposition, and Complexity
by: Chen, Hubie, et al.
Published: (2024)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)

Quantum Query-Space Lower Bounds Using Branching Programs
by: Bera, Debajyoti, et al.
Published: (2024)

A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity
by: Mengel, Stefan, et al.
Published: (2024)

Fine-Grained Complexity of Regular Path Queries
by: Casel, Katrin, et al.
Published: (2021)

Output-sensitive Conjunctive Query Evaluation
by: Deep, Shaleen, et al.
Published: (2024)

Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases
by: Karmakar, Pratik, et al.
Published: (2024)

Fast Matrix Multiplication meets the Submodular Width
by: Abo-Khamis, Mahmoud, et al.
Published: (2024)

A characterization of efficiently compilable constraint languages
by: Berkholz, Christoph, et al.
Published: (2023)

An extended Knowledge Compilation Map for Conditional Preference Statements-based and Generalized Additive Utilities-based Languages
by: Fargier, Hélène, et al.
Published: (2021)

Capturing P: On the Expressive Power and Efficient Evaluation of Boolean Retrieval
by: Aavani, Amir
Published: (2026)

Structural Indexing of Relational Databases for the Evaluation of Free-Connex Acyclic Conjunctive Queries
by: Riveros, Cristian, et al.
Published: (2026)

Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries
by: Khamis, Mahmoud Abo, et al.
Published: (2025)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

Local Enumeration and Majority Lower Bounds
by: Gurumukhani, Mohit, et al.
Published: (2024)

Lower Bounds for Approximate Sign Rank
by: Bindua, Riju, et al.
Published: (2026)

Spectral Lower Bounds for Local Search
by: Brânzei, Simina, et al.
Published: (2024)

Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins
by: Deeds, Kyle, et al.
Published: (2025)

The Weisfeiler-Leman Dimension of Conjunctive Queries
by: Göbel, Andreas, et al.
Published: (2023)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
by: Kothari, Pravesh K., et al.
Published: (2024)

IPS Lower Bounds for Formulas and Sum of ROABPs
by: Chatterjee, Prerona, et al.
Published: (2025)

A Quadratic Lower Bound for Noncommutative Circuits
by: Shastri, Pratik
Published: (2026)

Lower Bounds for Set-Multilinear Branching Programs
by: Chatterjee, Prerona, et al.
Published: (2023)

Lower Bounds from Succinct Hitting Sets
by: Chatterjee, Prerona, et al.
Published: (2023)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
by: Byramji, Farzan, et al.
Published: (2025)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
by: Gajulapalli, Karthik, et al.
Published: (2025)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
by: Carmosino, Marco, et al.
Published: (2026)

Top-Down Lower Bounds for Depth-Four Circuits
by: Göös, Mika, et al.
Published: (2023)

Tight Lower Bounds for Block-Structured Integer Programs
by: Hunkenschröder, Christoph, et al.
Published: (2024)