Zobrazeno 1 - 10
of 81
pro vyhledávání: '"Bernhard Haeupler"'
Autor:
Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d04dd8325c13e3aeee53c3c8ce7af6be
https://doi.org/10.1137/1.9781611977554.ch137
https://doi.org/10.1137/1.9781611977554.ch137
Publikováno v:
STOC
We introduce synchronization strings , which provide a novel way to efficiently deal with synchronization errors , i.e., insertions and deletions. Synchronization errors are strictly more general and much harder to cope with than more commonly consid
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d27fc294d40805d206c28c8cfe325073
https://doi.org/10.1145/3468265
https://doi.org/10.1145/3468265
Publikováno v:
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::eed70b2476427b7c728970907a9d3e52
https://doi.org/10.1145/3519270.3538464
https://doi.org/10.1145/3519270.3538464
Autor:
Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
Publikováno v:
STOC 2022
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9311211e58e7f3f250774f60b8d82889
https://doi.org/10.1145/3519935.3520007
https://doi.org/10.1145/3519935.3520007
Publikováno v:
Proceeding of the ACM Symposium on Theory of Computing (STOC)
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
This paper studies the fundamental task of establishing routing paths in distributed networks. We prove the existence of compact routing tables that store in each network-node few simple forwarding rules tracing out hop-constrained and oblivious rout
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::faafec640d993f11c15d85be962f0377
https://hdl.handle.net/20.500.11850/596822
https://hdl.handle.net/20.500.11850/596822
Publikováno v:
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorithmic power of these new notions and transformations. One application is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9e0e0d3a7963f6f231f576dc452e664e
Autor:
Bernhard Haeupler, Mohsen Ghaffari
Publikováno v:
PODC
PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC '21)
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC '21)
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
We prove that any n-node graph G with diameter D admits shortcuts with congestion O(δ D log n) and dilation O(δ D), where δ is the maximum edge-density of any minor of G. Our proof is simple and constructive with a tildeΘ (δ D)-round1 distribute
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::337a811a082093a83c57958c083a84b4
https://doi.org/10.1145/3465084.3467935
https://doi.org/10.1145/3465084.3467935
Publikováno v:
STOC
STOC: ACM Symposium on Theory of Computing
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)
STOC: ACM Symposium on Theory of Computing
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)
Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::26b25de429665eff8474499d1ad67b9b
https://doi.org/10.1145/3406325.3451081
https://doi.org/10.1145/3406325.3451081
Publikováno v:
SODA: ACM-SIAM Symposium on Discrete Algorithms
SODA
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
SODA
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
This paper studies \emph{linear} and \emph{affine} error-correcting codes for correcting synchronization errors such as insertions and deletions. We call such codes linear/affine insdel codes. Linear codes that can correct even a single deletion are
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::253495953a3f66430cf71bf83cac68a7
Publikováno v:
STOC: ACM Symposium on Theory of Computing
STOC
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
STOC
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
We prove the existence of an oblivious routing scheme that is $\mathrm{poly}(\log n)$-competitive in terms of $(congestion + dilation)$, thus resolving a well-known question in oblivious routing. Concretely, consider an undirected network and a set o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a79b901d4ebe8808136e4c99113c2034