Popular conjectures imply strong lower bounds for dynamic problems

DOI10.1109/FOCS.2014.53MaRDI QIDQ6947218zbMATH OpenFDO

Authors Amir Abboud, Virginia Vassilevska Williams

Publication date 5 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2014.53

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX) Information and communication theory, circuits (94-XX)

Cited in

(31)

• On Wagner's k-tree algorithm over integers
• Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
• Lower bounds for semi-adaptive data structures via corruption
• Towards optimal set-disjointness and set-intersection data structures
• On the fine-grained complexity of parity problems
• Asymptotic and computational complexity of algorithms and program performance
• Hardness of dynamic core and truss decompositions
• Better decremental and fully dynamic sensitivity oracles for subgraph connectivity
• Fully dynamic strongly connected components in planar digraphs
• Fine-grained complexity in a world without cryptography
• A k-swap local search for makespan scheduling
• Dynamic geometric connectivity in the plane with constant query time
• On the complexity of algorithms with predictions for dynamic graph problems
• Conditional lower bounds for dynamic geometric measure problems
• Conditional lower bounds for dynamic geometric measure problems
• Elastic-degenerate string comparison
• Dynamic matching with better-than-2 approximation in polylogarithmic update time
• The complexity of non-stationary reinforcement learning
• Fine-grained cryptanalysis: tight conditional bounds for dense \(k\)-SUM and \(k\)-XOR
• Any-k algorithms for enumerating ranked answers to conjunctive queries
• Conjunctive queries with comparisons
• Fine-grained complexity of regular path queries
• Fine-grained hardness for edit distance to a fixed sequence
• Faster algorithms for bounded liveness in graphs and game graphs
• From donkeys to kings in tournaments
• Connectivity oracles for predictable vertex failures
• A dichotomy theorem for linear time homomorphism orbit counting in bounded degeneracy graphs
• Faster combinatorial k-clique algorithms
• Faster dynamic 2-edge connectivity in directed graphs
• (Multivariate) k-SUM as barrier to succinct computation
• On incremental approximate shortest paths in directed graphs

This page was built for publication: Popular conjectures imply strong lower bounds for dynamic problems

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