Please note that ISTA Research Explorer no longer supports Internet Explorer versions 8 or 9 (or earlier).
We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox.
62 Publications
2024 | Conference Paper | IST-REx-ID: 15008 | 
Goranci G, Henzinger MH, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science Conference, LIPIcs, vol. 287, 55.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Conference Paper | IST-REx-ID: 15007 |
Alpos O, Amores-Sesar I, Cachin C, Yeo MX. 2024. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 12.
[Published Version]
View
| Files available
| DOI
| arXiv
2023 | Conference Paper | IST-REx-ID: 12760 |
Henzinger MH, Neumann S, Räcke H, Schmid S. 2023. Dynamic maintenance of monotone dynamic programs and applications. 40th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 254, 36.
[Published Version]
View
| Files available
| DOI
| arXiv
2023 | Conference Paper | IST-REx-ID: 14085 |
Goranci G, Henzinger MH. 2023. Efficient data structures for incremental exact and approximate maximum flow. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 69.
[Published Version]
View
| Files available
| DOI
2023 | Conference Paper | IST-REx-ID: 14084 |
Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 72.
[Published Version]
View
| Files available
| DOI
| arXiv
2023 | Conference Paper | IST-REx-ID: 14083 |
Resch N, Yuan C, Zhang Y. 2023. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 99.
[Published Version]
View
| Files available
| DOI
| arXiv
2023 | Conference Paper | IST-REx-ID: 14485 |
Aksenov V, Anoprenko M, Fedorov A, Spear M. 2023. Brief announcement: BatchBoost: Universal batching for concurrent data structures. 37th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 281, 35.
[Published Version]
View
| Files available
| DOI
2023 | Conference Paper | IST-REx-ID: 14516 |
Beaver D, Kelkar M, Lewi K, Nikolaenko V, Sonnino A, Chalkias K, Kokoris Kogias E, Naurois LD, Roy A. 2023. STROBE: Streaming Threshold Random Beacons. 5th Conference on Advances in Financial Technologies. AFT: Conference on Advances in Financial Technologies, LIPIcs, vol. 282, 7.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2022 | Conference Paper | IST-REx-ID: 11184 |
Alistarh D-A, Gelashvili R, Rybicki J. 2022. Fast graphical population protocols. 25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 14.
[Published Version]
View
| Files available
| DOI
| arXiv
2022 | Conference Paper | IST-REx-ID: 11183 |
Nikabadi A, Korhonen J. 2022. Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters. 25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 15.
[Published Version]
View
| Files available
| DOI
2022 | Conference Paper | IST-REx-ID: 11428 |
Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. 2022. A cautionary tale: Burning the medial axis is unstable. 38th International Symposium on Computational Geometry. SoCG: Symposium on Computational GeometryLIPIcs vol. 224, 66:1-66:9.
[Published Version]
View
| Files available
| DOI
2022 | Conference Paper | IST-REx-ID: 11812 |
Hanauer K, Henzinger MH, Hua QC. 2022. Fully dynamic four-vertex subgraph counting. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 18.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2022 | Conference Paper | IST-REx-ID: 12102 |
Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic D. 2022. Algorithms and hardness results for computing cores of Markov chains. 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTC: Foundations of Software Technology and Theoretical Computer Science vol. 250, 29.
[Published Version]
View
| Files available
| DOI
2022 | Conference Paper | IST-REx-ID: 12101 |
Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. 2022. Complexity of spatial games. 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTC: Foundations of Software Technology and Theoretical Computer Science vol. 250, 11:1-11:14.
[Published Version]
View
| Files available
| DOI
2022 | Conference Paper | IST-REx-ID: 12508 |
Henzinger TA, Lehtinen K, Totzke P. 2022. History-deterministic timed automata. 33rd International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 243, 14:1-14:21.
[Published Version]
View
| Files available
| DOI
2022 | Conference Paper | IST-REx-ID: 12509 |
Avni G, Henzinger TA. 2022. An updated survey of bidding games on graphs. 47th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer ScienceLeibniz International Proceedings in Informatics (LIPIcs) vol. 241, 3:1-3:6.
[Published Version]
View
| Files available
| DOI
2022 | Conference Paper | IST-REx-ID: 12775 |
Grover K, Kretinsky J, Meggendorfer T, Weininger M. 2022. Anytime guarantees for reachability in uncountable Markov decision processes. 33rd International Conference on Concurrency Theory . CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 243, 11.
[Published Version]
View
| Files available
| DOI
| arXiv
2021 | Conference Paper | IST-REx-ID: 10052 |
Jecker IR, Mazzocchi N, Wolf P. 2021. Decomposing permutation automata. 32nd International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 203, 18.
[Published Version]
View
| Files available
| DOI
| arXiv
2021 | Conference Paper | IST-REx-ID: 10054 |
Chatterjee K, Henzinger MH, Kale SS, Svozil A. 2021. Faster algorithms for bounded liveness in graphs and game graphs. 48th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 198, 124.
[Published Version]
View
| Files available
| DOI
2021 | Conference Paper | IST-REx-ID: 10072 |
Harris DG, Iliopoulos F, Kolmogorov V. 2021. A new notion of commutativity for the algorithmic Lovász Local Lemma. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX/RANDOM: Approximation Algorithms for Combinatorial Optimization Problems/ Randomization and Computation, LIPIcs, vol. 207, 31.
[Published Version]
View
| Files available
| DOI
| arXiv
2021 | Conference Paper | IST-REx-ID: 10075 |
Guha S, Jecker IR, Lehtinen K, Zimmermann M. 2021. A bit of nondeterminism makes pushdown automata expressive and succinct. 46th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 202, 53.
[Published Version]
View
| Files available
| DOI
| arXiv
2021 | Conference Paper | IST-REx-ID: 10218 |
Alistarh D-A, Gelashvili R, Rybicki J. 2021. Brief announcement: Fast graphical population protocols. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 43.
[Published Version]
View
| Files available
| DOI
| arXiv
2021 | Conference Paper | IST-REx-ID: 10217 |
Alistarh D-A, Gelashvili R, Nadiradze G. 2021. Lower bounds for shared-memory leader election under bounded write contention. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 4.
[Published Version]
View
| Files available
| DOI
2021 | Conference Paper | IST-REx-ID: 10216 |
Chatterjee B, Peri S, Sa M. 2021. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 52.
[Published Version]
View
| Files available
| DOI
| arXiv
2021 | Conference Paper | IST-REx-ID: 10219 |
Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. 2021. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 58.
[Published Version]
View
| Files available
| DOI
| arXiv
2021 | Conference Paper | IST-REx-ID: 10630 |
Arrighi E, Fernau H, Hoffmann S, Holzer M, Jecker IR, De Oliveira Oliveira M, Wolf P. 2021. On the complexity of intersection non-emptiness for star-free language classes. 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 213, 34.
[Published Version]
View
| Files available
| DOI
| arXiv
2021 | Conference Paper | IST-REx-ID: 10629 |
Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2021. Quantitative verification on product graphs of small treewidth. 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 213, 42.
[Published Version]
View
| Files available
| DOI
2021 | Conference Paper | IST-REx-ID: 11814 |
Fichtenberger H, Henzinger MH, Ost W. 2021. Differentially private algorithms for graphs under continual observation. 29th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 204, 42.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2021 | Conference Paper | IST-REx-ID: 9345 |
Edelsbrunner H, Heiss T, Kurlin V, Smith P, Wintraecken M. 2021. The density fingerprint of a periodic point set. 37th International Symposium on Computational Geometry (SoCG 2021). SoCG: Symposium on Computational Geometry, LIPIcs, vol. 189, 32:1-32:16.
[Published Version]
View
| Files available
| DOI
2021 | Conference Paper | IST-REx-ID: 10055 |
Jecker IR. 2021. A Ramsey theorem for finite monoids. 38th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 187, 44.
[Published Version]
View
| Files available
| DOI
| WoS
2021 | Conference Paper | IST-REx-ID: 9441 |
Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. 37th International Symposium on Computational Geometry (SoCG 2021). SoCG: Symposium on Computational GeometryLeibniz International Proceedings in Informatics (LIPIcs), LIPIcs, vol. 189, 17:1-17:16.
[Published Version]
View
| Files available
| DOI
2020 | Conference Paper | IST-REx-ID: 11818 |
Henzinger MH, Kale S. 2020. Fully-dynamic coresets. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 57.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Conference Paper | IST-REx-ID: 11816 |
Henzinger MH, Shahbaz K, Paul R, Schulz C. 2020. Dynamic matching algorithms in practice. 8th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 58.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Conference Paper | IST-REx-ID: 11824 |
Henzinger MH, Neumann S, Wiese A. 2020. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 51.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Conference Paper | IST-REx-ID: 11822 |
Hanauer K, Henzinger MH, Schulz C. 2020. Faster fully dynamic transitive closure in practice. 18th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 160, 14.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Conference Paper | IST-REx-ID: 11825 |
Henzinger MH, Peng P. 2020. Constant-time dynamic (Δ+1)-coloring. 37th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 154, 53.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Conference Paper | IST-REx-ID: 11819 |
Henzinger MH, Noe A, Schulz C, Strash D. 2020. Finding all global minimum cuts in practice. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 59.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Conference Paper | IST-REx-ID: 7348 |
Ferrere T, Henzinger TA, Kragl B. 2020. Monitoring event frequencies. 28th EACSL Annual Conference on Computer Science Logic. CSL: Computer Science Logic, LIPIcs, vol. 152, 20.
[Published Version]
View
| Files available
| DOI
| arXiv
2020 | Conference Paper | IST-REx-ID: 8725 |
Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2020. The splay-list: A distribution-adaptive concurrent skip-list. 34th International Symposium on Distributed Computing. DISC: Symposium on Distributed ComputingLIPIcs vol. 179, 3:1-3:18.
[Published Version]
View
| Files available
| DOI
| arXiv
2020 | Conference Paper | IST-REx-ID: 7952 |
Boissonnat J-D, Wintraecken M. 2020. The topological correctness of PL-approximations of isomanifolds. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 20:1-20:18.
[Published Version]
View
| Files available
| DOI
2019 | Conference Paper | IST-REx-ID: 11826 |
Ancona B, Henzinger MH, Roditty L, Williams VV, Wein N. 2019. Algorithms and hardness for diameter in dynamic graphs. 46th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 132, 13.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2019 | Conference Paper | IST-REx-ID: 6528 |
Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in Theoretical Computer Science Conference. ITCS 2019: Innovations in Theoretical Computer Science, LIPIcs, vol. 124, 60.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2019 | Conference Paper | IST-REx-ID: 6725 |
Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th International Colloquium on Automata, Languages and Programming. ICALP 2019: International Colloquim on Automata, Languages and Programming, LIPIcs, vol. 132, 77:1-77:12.
[Published Version]
View
| Files available
| DOI
| arXiv
2019 | Conference Paper | IST-REx-ID: 7401 |
Fulek R, Kyncl J. 2019. Z_2-Genus of graphs and minimum rank of partial symmetric matrices. 35th International Symposium on Computational Geometry (SoCG 2019). SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 39.
[Published Version]
View
| Files available
| DOI
| arXiv
2019 | Conference Paper | IST-REx-ID: 6556 |
Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 44:1-44:20.
[Published Version]
View
| Files available
| DOI
| arXiv
2019 | Conference Paper | IST-REx-ID: 6647 |
Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.
[Published Version]
View
| Files available
| DOI
| arXiv
2018 | Conference Paper | IST-REx-ID: 11828 |
Goranci G, Henzinger MH, Peng P. 2018. Dynamic effective resistances and approximate schur complement on separable graphs. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 40.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Conference Paper | IST-REx-ID: 11827 |
Goranci G, Henzinger MH, Leniowski D. 2018. A tree structure for dynamic facility location. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 39.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Conference Paper | IST-REx-ID: 11911 |
Biedermann S, Henzinger MH, Schulz C, Schuster B. 2018. Memetic graph clustering. 17th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 103, 3.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Conference Paper | IST-REx-ID: 7407 |
Pietrzak KZ. 2018. Proofs of catalytic space. 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). ITCS: Innovations in theoretical Computer Science Conference, LIPIcs, vol. 124, 59:1-59:25.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2018 | Conference Paper | IST-REx-ID: 6005 |
Avni G, Guha S, Kupferman O. 2018. Timed network games with clocks. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 117, 23.
[Published Version]
View
| Files available
| DOI
2017 | Conference Paper | IST-REx-ID: 11829 |
Henzinger MH, Lincoln A, Neumann S, Vassilevska Williams V. 2017. Conditional hardness for sensitivity problems. 8th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science Conference, LIPIcs, vol. 67, 26.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Conference Paper | IST-REx-ID: 11833 |
Goranci G, Henzinger MH, Peng P. 2017. The power of vertex sparsifiers in dynamic graph algorithms. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 45.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Conference Paper | IST-REx-ID: 11832 |
Henzinger MH, Leniowski D, Mathieu C. 2017. Dynamic clustering to minimize the sum of radii. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 48.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Conference Paper | IST-REx-ID: 11831 |
Goranci G, Henzinger MH, Peng P. 2017. Improved guarantees for vertex sparsification in planar graphs. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 44.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Conference Paper | IST-REx-ID: 950 |
Avni G, Henzinger TA, Chonev VK. 2017. Infinite-duration bidding games. CONCUR: Concurrency Theory, LIPIcs, vol. 85, 17.
[Published Version]
View
| Files available
| DOI
| arXiv
2016 | Conference Paper | IST-REx-ID: 11836 |
Cheung YK, Goranci G, Henzinger MH. 2016. Graph minors for preserving terminal distances approximately - lower and upper bounds. 43rd International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 55, 131.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2016 | Conference Paper | IST-REx-ID: 11834 |
Goranci G, Henzinger MH, Thorup M. 2016. Incremental exact min-cut in poly-logarithmic amortized update time. 24th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 57, 46.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2016 | Conference Paper | IST-REx-ID: 11835 |
Henzinger MH, Neumann S. 2016. Incremental and fully dynamic subgraph connectivity for emergency planning. 24th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 57, 48.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2015 | Conference Paper | IST-REx-ID: 11837 |
Bhattacharya S, Dvorák W, Henzinger MH, Starnberger Martin. 2015. Welfare maximization with friends-of-friends network externalities. 32nd International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 30, 90–102.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2010 | Conference Paper | IST-REx-ID: 11838 |
Dütting P, Henzinger MH, Weber I. 2010. Sponsored search, market equilibria, and the Hungarian Method. 27th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 5, 287–298.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
| arXiv
2009 | Conference Paper | IST-REx-ID: 11912 |
Baykan Eda, Henzinger MH, Keller SF, de Castelberg S, Kinzler M. 2009. A comparison of techniques for sampling web pages. 26th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 3, 13–30.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv