Fast Algorithms for a Reactive Network Layer

Project Period: 2023-03-01 – 2024-09-30
Funder: FWF
Principal Investigator
Grant Number
P33775
Funder
FWF

18 Publications

2024 | Published | Conference Paper | IST-REx-ID: 14769 | OA
Experimental evaluation of fully dynamic k-means via coresets
M. Henzinger, D. Saulpic, L. Sidl, in:, 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Society for Industrial & Applied Mathematics, 2024, pp. 220–233.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 15008 | OA
Electrical flows for polylogarithmic competitive oblivious routing
G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan, in:, 15th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[Published Version] View | Files available | DOI | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 15093 | OA
Dynamically maintaining the persistent homology of time series
S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, L. Ost, in:, D.P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, 2024, pp. 243–295.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
2024 | Epub ahead of print | Journal Article | IST-REx-ID: 15121 | OA
Multiplicative auction algorithm for approximate maximum weight bipartite matching
D.W. Zheng, M. Henzinger, Mathematical Programming (2024).
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 15253 | OA
A unifying framework for differentially private sums under continual observation
M. Henzinger, J. Upadhyay, S. Upadhyay, in:, Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 995–1018.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 18115 | OA
Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond
K. Axiotis, V. Cohen-Addad, M. Henzinger, S. Jerome, V. Mirrokni, D. Saulpic, D.P. Woodruff, M. Wunder, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 2086–2107.
[Published Version] View | Download Published Version (ext.) | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 18116 | OA
Making old things new: A unified algorithm for differentially private clustering
M.D. La Tour, M. Henzinger, D. Saulpic, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 12046–12086.
[Published Version] View | Download Published Version (ext.) | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 18156 | OA
Private counting of distinct elements in the turnstile model and extensions
M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, International Conference on Approximation Algorithms for Combinatorial Optimization Problems , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[Published Version] View | Files available | DOI | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 18308 | OA
Fully dynamic k-means coreset in near-optimal update time
M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[Published Version] View | Files available | DOI | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 18503
Deterministic near-linear time minimum cut in weighted graphs
M. Henzinger, J. Li, S. Rao, D. Wang, in:, 35th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 3089–3139.
[Preprint] View | DOI | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 18557 | OA
Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges
A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[Published Version] View | Files available | DOI | arXiv
 
2023 | Published | Conference Paper | IST-REx-ID: 13236 | OA
Multiplicative auction algorithm for approximate maximum weight bipartite matching
D.W. Zheng, M. Henzinger, in:, International Conference on Integer Programming and Combinatorial Optimization, Springer Nature, 2023, pp. 453–465.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
2023 | Published | Journal Article | IST-REx-ID: 14043 | OA
A combinatorial cut-toggling algorithm for solving Laplacian linear systems
M. Henzinger, B. Jin, R. Peng, D.P. Williamson, Algorithmica 85 (2023) 2680–3716.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
2023 | Published | Conference Paper | IST-REx-ID: 14085 | OA
Efficient data structures for incremental exact and approximate maximum flow
G. Goranci, M. Henzinger, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
[Published Version] View | Files available | DOI
 
2023 | Published | Conference Paper | IST-REx-ID: 14086 | OA
Faster submodular maximization for several classes of matroids
M. Henzinger, P. Liu, J. Vondrák, D.W. Zheng, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
[Published Version] View | Files available | DOI | arXiv
 
2023 | Published | Conference Paper | IST-REx-ID: 14462 | OA
Constant matters: Fine-grained error bound on differentially private continual observation
H. Fichtenberger, M. Henzinger, J. Upadhyay, in:, Proceedings of the 40th International Conference on Machine Learning, ML Research Press, 2023, pp. 10072–10092.
[Published Version] View | Download Published Version (ext.)
 
2023 | Published | Journal Article | IST-REx-ID: 14558
Deterministic near-optimal approximation algorithms for dynamic set cover
S. Bhattacharya, M. Henzinger, D. Nanongkai, X. Wu, SIAM Journal on Computing 52 (2023) 1132–1192.
View | DOI
 
2023 | Published | Conference Paper | IST-REx-ID: 15364 | OA
Simple, scalable and effective clustering via one-dimensional projections
M. Charikar, L. Hu, M. Henzinger, M. Vötsch, E. Waingarten, in:, 37th Conference on Neural Information Processing Systems, 2023.
[Published Version] View | Files available | arXiv
 

Search

Filter Publications

Display / Sort

Export / Embed