:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Bringmann, Karl, Carmeli, Nofar, Mengel, Stefan
Format:	Preprint
Published:	2022
Subjects:	Databases Computational Complexity
Online Access:	https://arxiv.org/abs/2201.02401
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Lower Bounds for Conjunctive Query Evaluation
by: Mengel, Stefan
Published: (2025)

Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
by: Bringmann, Karl, et al.
Published: (2022)

Direct Access for Answers to Conjunctive Queries with Aggregation
by: Eldar, Idan, et al.
Published: (2023)

Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
by: Carmeli, Nofar, et al.
Published: (2025)

Direct Access for Conjunctive Queries with Negations
by: Capelli, Florent, et al.
Published: (2023)

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

Let's Play Tag: Linear Time Evaluation of Conjunctive Queries under TGD Constraints
by: Carmeli, Nofar, et al.
Published: (2026)

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)

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

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)

Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy
by: Berkholz, Christoph, et al.
Published: (2025)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
by: Dinur, Itai, et al.
Published: (2021)

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)

Optimally Rewriting Formulas and Database Queries: A Confluence of Term Rewriting, Structural Decomposition, and Complexity
by: Chen, Hubie, 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)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
by: Bringmann, Karl, 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)

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
by: Bringmann, Karl, et al.
Published: (2023)

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

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
by: Alrabiah, Omar, et al.
Published: (2024)

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
by: Kamath, Pritish, et al.
Published: (2026)

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

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
by: Alman, Josh, et al.
Published: (2025)

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
by: Gupta, Rishav, et al.
Published: (2026)

Tight Bounds for Quantum Phase Estimation and Related Problems
by: Mande, Nikhil S., et al.
Published: (2023)

Quantum Lovász Local Lemma: Shearer's Bound is Tight
by: He, Kun, et al.
Published: (2018)

From Time to Space: The Impact of Linearity in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2026)

The Power of Negation in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2025)

Sum of Squares Circuits
by: Loconte, Lorenzo, et al.
Published: (2024)

Learning Tree Pattern Transformations
by: Neider, Daniel, et al.
Published: (2024)

Matching walks that are minimal with respect to edge inclusion
by: Marsault, Victor
Published: (2024)

Direct Product Theorems for Randomized Query Complexity
by: Ben-David, Shalev, et al.
Published: (2025)

The Complexity of Resilience for Digraph Queries
by: Bodirsky, Manuel, et al.
Published: (2026)