TY - GEN
T1 - Super-Logarithmic Lower Bounds for Dynamic Graph Problems
AU - Larsen, Kasper Green
AU - Yu, Huacheng
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - In this work, we prove a Õ(lg3/2 n) unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions. This is the first super-logarithmic lower bound for any natural graph problem. In proving the lower bound, we also make novel contributions to the state-of-the-art data structure lower bound techniques that we hope may lead to further progress in proving lower bounds.
AB - In this work, we prove a Õ(lg3/2 n) unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions. This is the first super-logarithmic lower bound for any natural graph problem. In proving the lower bound, we also make novel contributions to the state-of-the-art data structure lower bound techniques that we hope may lead to further progress in proving lower bounds.
KW - cell-probe model
KW - data structure lower bounds
KW - dynamic graph algorithms
KW - dynamic reachability
UR - http://www.scopus.com/inward/record.url?scp=85182392607&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85182392607&partnerID=8YFLogxK
U2 - 10.1109/FOCS57990.2023.00096
DO - 10.1109/FOCS57990.2023.00096
M3 - Conference contribution
AN - SCOPUS:85182392607
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 1589
EP - 1604
BT - Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PB - IEEE Computer Society
T2 - 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Y2 - 6 November 2023 through 9 November 2023
ER -