Copertina

Tight Fine-Grained Bounds for Direct Access on Join Queries

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bringmann, Karl, Carmeli, Nofar, Mengel, Stefan
Natura:	Preprint
Pubblicazione:	2022
Soggetti:	Databases Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Lower Bounds for Conjunctive Query Evaluation
di: Mengel, Stefan
Pubblicazione: (2025)

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

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

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

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

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

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

Towards Parameterized Hardness on Maintaining Conjunctive Queries
di: Wang, Qichen
Pubblicazione: (2026)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
di: Bringmann, Karl, et al.
Pubblicazione: (2024)

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

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

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

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

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

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

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

Learning Tree Pattern Transformations
di: Neider, Daniel, et al.
Pubblicazione: (2024)

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

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

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

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

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