Worst-case and average-case hardness of hypercycle and database problems

DOI10.4230/LIPICS.ICALP.2025.81MaRDI QIDQ7363167zbMATH OpenFDO

Authors Cheng-Hao Fu, Andrea Lincoln, Rene Reyes

Publication date 29 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.81

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• Average-case fine-grained hardness
• Consequences of Faster Alignment of Sequences
• Finding tight Hamilton cycles in random hypergraphs faster
• On tight cycles in hypergraphs
• Proofs of Work from worst-case assumptions
• The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
• Tight cycles in hypergraphs
• Tight hardness for shortest cycles and paths in sparse graphs

This page was built for publication: Worst-case and average-case hardness of hypercycle and database problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7363167)