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
2019 | Conference Paper | IST-REx-ID: 11826 | 
B. Ancona, M. H. Henzinger, L. Roditty, V. V. Williams, and N. Wein, “Algorithms and hardness for diameter in dynamic graphs,” in 46th International Colloquium on Automata, Languages, and Programming, Patras, Greece, 2019, vol. 132.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2019 | Conference Paper | IST-REx-ID: 6528 |
K. Z. Pietrzak, “Simple verifiable delay functions,” in 10th Innovations in Theoretical Computer Science Conference, San Diego, CA, United States, 2019, vol. 124.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2019 | Conference Paper | IST-REx-ID: 6725 |
V. Kolmogorov, “Testing the complexity of a valued CSP language,” in 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 2019, vol. 132, p. 77:1-77:12.
[Published Version]
View
| Files available
| DOI
| arXiv
2019 | Conference Paper | IST-REx-ID: 7401 |
R. Fulek and J. Kyncl, “Z_2-Genus of graphs and minimum rank of partial symmetric matrices,” in 35th International Symposium on Computational Geometry (SoCG 2019), Portland, OR, United States, 2019, vol. 129.
[Published Version]
View
| Files available
| DOI
| arXiv
2019 | Conference Paper | IST-REx-ID: 6556 |
K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in 35th International Symposium on Computational Geometry, Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20.
[Published Version]
View
| Files available
| DOI
| arXiv
2019 | Conference Paper | IST-REx-ID: 6647 |
R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” in 35th International Symposium on Computational Geometry, Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.
[Published Version]
View
| Files available
| DOI
| arXiv
2018 | Conference Paper | IST-REx-ID: 11828 |
G. Goranci, M. H. Henzinger, and P. Peng, “Dynamic effective resistances and approximate schur complement on separable graphs,” in 26th Annual European Symposium on Algorithms, Helsinki, Finland, 2018, vol. 112.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Conference Paper | IST-REx-ID: 11827 |
G. Goranci, M. H. Henzinger, and D. Leniowski, “A tree structure for dynamic facility location,” in 26th Annual European Symposium on Algorithms, Helsinki, Finland, 2018, vol. 112.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Conference Paper | IST-REx-ID: 11911 |
S. Biedermann, M. H. Henzinger, C. Schulz, and B. Schuster, “Memetic graph clustering,” in 17th International Symposium on Experimental Algorithms, L’Aquila, Italy, 2018, vol. 103.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Conference Paper | IST-REx-ID: 7407 |
K. Z. Pietrzak, “Proofs of catalytic space,” in 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), San Diego, CA, United States, 2018, vol. 124, p. 59:1-59:25.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2018 | Conference Paper | IST-REx-ID: 6005 |
G. Avni, S. Guha, and O. Kupferman, “Timed network games with clocks,” presented at the MFCS: Mathematical Foundations of Computer Science, Liverpool, United Kingdom, 2018, vol. 117.
[Published Version]
View
| Files available
| DOI
2017 | Conference Paper | IST-REx-ID: 11829 |
M. H. Henzinger, A. Lincoln, S. Neumann, and V. Vassilevska Williams, “Conditional hardness for sensitivity problems,” in 8th Innovations in Theoretical Computer Science Conference, Berkley, CA, United States, 2017, vol. 67.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Conference Paper | IST-REx-ID: 11833 |
G. Goranci, M. H. Henzinger, and P. Peng, “The power of vertex sparsifiers in dynamic graph algorithms,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Conference Paper | IST-REx-ID: 11832 |
M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Conference Paper | IST-REx-ID: 11831 |
G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Conference Paper | IST-REx-ID: 950 |
G. Avni, T. A. Henzinger, and V. K. Chonev, “Infinite-duration bidding games,” presented at the CONCUR: Concurrency Theory, Berlin, Germany, 2017, vol. 85.
[Published Version]
View
| Files available
| DOI
| arXiv
2016 | Conference Paper | IST-REx-ID: 11836 |
Y. K. Cheung, G. Goranci, and M. H. Henzinger, “Graph minors for preserving terminal distances approximately - lower and upper bounds,” in 43rd International Colloquium on Automata, Languages, and Programming, Rome, Italy, 2016, vol. 55.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2016 | Conference Paper | IST-REx-ID: 11834 |
G. Goranci, M. H. Henzinger, and M. Thorup, “Incremental exact min-cut in poly-logarithmic amortized update time,” in 24th Annual European Symposium on Algorithms, Aarhus, Denmark, 2016, vol. 57.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2016 | Conference Paper | IST-REx-ID: 11835 |
M. H. Henzinger and S. Neumann, “Incremental and fully dynamic subgraph connectivity for emergency planning,” in 24th Annual European Symposium on Algorithms, Aarhus, Denmark, 2016, vol. 57.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2015 | Conference Paper | IST-REx-ID: 11837 |
S. Bhattacharya, W. Dvorák, M. H. Henzinger, and Martin Starnberger, “Welfare maximization with friends-of-friends network externalities,” in 32nd International Symposium on Theoretical Aspects of Computer Science, Garching, Germany, 2015, vol. 30, pp. 90–102.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2010 | Conference Paper | IST-REx-ID: 11838 |
P. Dütting, M. H. Henzinger, and I. Weber, “Sponsored search, market equilibria, and the Hungarian Method,” in 27th International Symposium on Theoretical Aspects of Computer Science, Nancy, France, 2010, vol. 5, pp. 287–298.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
| arXiv
2009 | Conference Paper | IST-REx-ID: 11912 |
Eda Baykan, M. H. Henzinger, S. F. Keller, S. de Castelberg, and M. Kinzler, “A comparison of techniques for sampling web pages,” in 26th International Symposium on Theoretical Aspects of Computer Science, Freiburg, Germany, 2009, vol. 3, pp. 13–30.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv