Mikkel Thorup
Professor
- 2023
- Published
A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing
Houen, J. B. T. & Thorup, Mikkel, 2023, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. Etessami, K., Feige, U. & Puppis, G. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 76. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 261).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Goranci, G., Henzinger, M., Nanongkai, D., Saranurak, T., Thorup, Mikkel & Wulff-Nilsen, Christian, 2023, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Bansal, N. & Nagarajan, V. (eds.). Society for Industrial and Applied Mathematics, p. 70-86Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Locally Uniform Hashing
Bercea, I. O., Beretta, Lorenzo, Klausen, Jonas Østergaard, Houen, J. B. T. & Thorup, Mikkel, 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society Press, p. 1440-1470Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Optimal Decremental Connectivity in Non-Sparse Graphs
Aamand, A., Karczmarz, A., Łącki, J., Parotsidis, N., Rasmussen, Peter Michael Reichstein & Thorup, Mikkel, 2023, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. Etessami, K., Feige, U. & Puppis, G. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-17 6. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 261).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
Kacham, P., Pagh, R., Thorup, Mikkel & Woodruff, D. P., 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society Press, p. 1515-1550 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2022
- Published
Understanding the Moments of Tabulation Hashing via Chaoses
Houen, J. B. T. & Thorup, Mikkel, Jul 2022, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. Bojanczyk, M., Merelli, E. & Woodruff, D. P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-19 74. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 229).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Dijkstra’s Single Source Shortest Path Algorithm
Thorup, Mikkel, 2022, Edsger Wybe Dijkstra: His Life,Work, and Legacy. Apt, K. R. & Hoare, T. (eds.). ACM, p. 21-26Research output: Chapter in Book/Report/Conference proceeding › Book chapter › Research › peer-review
- Published
Edge sampling and graph parameter estimation via vertex neighborhood accesses
Tetek, Jakub & Thorup, Mikkel, 2022, STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Leonardi, S. & Gupta, A. (eds.). Association for Computing Machinery, Inc., p. 1116-1129 14 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor
Cohen-Addad, V., Das, D., Kipouridis, Evangelos, Parotsidis, N. & Thorup, Mikkel, 2022, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 1-12Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Improved Utility Analysis of Private CountSketch
Pagh, Rasmus & Thorup, Mikkel, 2022, Advances in Neural Information Processing Systems 35 (NeurIPS 2022). NeurIPS Proceedings, 13 p. (Advances in Neural Information Processing Systems, Vol. 35).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Reconstructing the Tree of Life (Fitting Distances by Tree Metrics) (Invited Paper)
Thorup, Mikkel, 2022, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Springer, p. 3:1--3:2 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 227).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research
- 2021
- Published
Load balancing with dynamic set of balls and bins
Aamand, Anders, Knudsen, J. B. T. & Thorup, Mikkel, 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, Inc, p. 1262-1275 (Proceedings of the Annual ACM Symposium on Theory of Computing).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2020
- Published
Confirmation sampling for exact nearest neighbor search
Christiani, T., Pagh, R. & Thorup, Mikkel, 2020, Similarity Search and Applications - 13th International Conference, SISAP 2020, Proceedings. Satoh, S., Vadicamo, L., Carrara, F., Zimek, A., Bartolini, I., Aumüller, M., Jonsson, B. P. & Pagh, R. (eds.). Springer, p. 97-110 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12440 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Fast hashing with strong concentration bounds
Aamand, Anders, Knudsen, J. B. T., Knudsen, M. B. T., Rasmussen, Peter Michael Reichstein & Thorup, Mikkel, 2020, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G. & Chuzhoy, J. (eds.). Association for Computing Machinery, p. 1265-1278 (Proceedings of the Annual ACM Symposium on Theory of Computing).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Faster algorithms for edge connectivity via random 2-out contractions
Ghaffari, M., Nowicki, K. & Thorup, Mikkel, 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). Association for Computing Machinery, p. 1260-1279 20 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Three-in-a-tree in near linear time
Lai, K. Y., Lu, H. I. & Thorup, Mikkel, 2020, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G. & Chuzhoy, J. (eds.). Association for Computing Machinery, p. 1279-1292 (Proceedings of the Annual ACM Symposium on Theory of Computing).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2019
- Published
Non-empty Bins with Simple Tabulation Hashing
Aamand, Anders & Thorup, Mikkel, 2 Jan 2019, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Chan, T. M. (ed.). Society for Industrial and Applied Mathematics, p. 2498-2512Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research
- Published
Dynamic ordered sets with approximate queries, approximate heaps and soft heaps
Thorup, Mikkel, Zamir, O. & Zwick, U., 2019, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Chatzigiannakis, I., Baier, C., Leonardi, S. & Flocchini, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 13 p. 95. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 132).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Hardness of bichromatic closest pair with Jaccard similarity
Pagh, R., Stausholm, N. M. & Thorup, Mikkel, 2019, 27th Annual European Symposium on Algorithms, ESA 2019. Bender, M. A., Svensson, O. & Herman, G. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 13 p. 74. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 144).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Random k-out subgraph leaves only O(n/k) inter-component edges
Holm, Jacob, King, V., Thorup, Mikkel, Zamir, O. & Zwick, U., 2019, Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE, 14 p. 8948658Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2018
- Published
Power of d choices with simple tabulation
Aamand, Anders, Knudsen, M. B. T. & Thorup, Mikkel, 1 Jul 2018, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. Kaklamanis, C., Marx, D., Chatzigiannakis, I. & Sannella, D. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 14 p. 5. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 107).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Consistent Hashing with bounded loads
Mirrokni, V., Thorup, Mikkel & Zadimoghaddam, M., 2018, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Czumaj, A. (ed.). Society for Industrial and Applied Mathematics, p. 587-604 18 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Dynamic bridge-finding in Õ(log2 n) amortized time
Holm, Jacob, Rotenberg, E. & Thorup, Mikkel, 2018, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Czumaj, A. (ed.). Society for Industrial and Applied Mathematics, p. 35-52 18 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Fast fencing
Abrahamsen, Mikkel, Adamaszek, A., Bringmann, K., Cohen-Addad, V., Mehr, M., Rotenberg, E., Roytman, A. & Thorup, Mikkel, 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, p. 564-573Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
The entropy of backwards analysis
Knudsen, M. B. T. & Thorup, Mikkel, 2018, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Czumaj, A. (ed.). Society for Industrial and Applied Mathematics, p. 867-880 14 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Wireless coverage prediction via parametric shortest paths
Applegate, D., Archer, A., Johnson, D. S., Nikolova, E., Thorup, Mikkel & Yang, G., 2018, Proceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Mobihoc '18 . ACM, p. 221-230Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2017
- Published
Fast and powerful hashing using tabulation
Thorup, Mikkel, 2017, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Chatzigiannakis, I., Indyk, P., Kuhn, F. & Muscholl, A. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2 p. 4. (Leibniz International Proceedings in Informatics, Vol. 80).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research
- Published
Fast similarity sketching
Dahlgaard, S., Knudsen, M. B. T. & Thorup, Mikkel, 2017, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 663-671 9 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Practical hash functions for similarity estimation and dimensionality reduction
Dahlgaard, S., Knudsen, M. B. T. & Thorup, Mikkel, 2017, Neural Information Processing Systems 2017. Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S. & Garnett, R. (eds.). NIPS Proceedings, 11 p. (Advances in Neural Information Processing Systems, Vol. 30).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2016
- Published
Bottleneck paths and trees and deterministic graphical games
Chechik, S., Kaplan, H., Thorup, Mikkel, Zamir, O. & Zwick, U., 2016, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Ollinger, N. & Vollmer, H. (eds.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, p. 1-13 13 p. 27. (Leibniz International Proceedings in Informatics, Vol. 47).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Fast and powerful hashing using tabulation
Thorup, Mikkel, 2016, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Lal, A., Akshay, S., Saurabh, S. & Sen, S. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2 p. 1. (Leibniz International Proceedings in Informatics, Vol. 65).Research output: Chapter in Book/Report/Conference proceeding › Conference abstract in proceedings › Research › peer-review
- Published
Faster worst case deterministic dynamic connectivity
Kejlberg-Rasmussen, C., Kopelowitz, T., Pettie, S. & Thorup, Mikkel, 2016, 24th Annual European Symposium on Algorithms (ESA 2016). Sankowski, P. & Zaroliagis, C. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 53:1-53:15 15 p. 53. (Leibniz International Proceedings in Informatics, Vol. 57).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Finding the maximum subset with bounded convex curvature
Abrahamsen, Mikkel & Thorup, Mikkel, 2016, 32nd International Symposium on Computational Geometry (SoCG 2016). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 17 p. 4. (Leibniz International Proceedings in Informatics, Vol. 51).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Heavy hitters via cluster-preserving clustering
Larsen, K. G., Nelson, J., Nguyen, H. L. & Thorup, Mikkel, 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science. IEEE, p. 61-70 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Incremental exact min-cut in poly-logarithmic amortized update time
Goranci, G., Henzinger, M. & Thorup, Mikkel, 2016, 24th Annual European Symposium on Algorithms (ESA 2016). Sankowski, P. & Zaroliagis, C. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 17 p. 46. (Leibniz International Proceedings in Informatics, Vol. 57).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
The power of two choices with simple tabulation
Dahlgaard, S., Knudsen, M. B. T., Rotenberg, E. & Thorup, Mikkel, 2016, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Krauthgamer, R. (ed.). Society for Industrial and Applied Mathematics, p. 1631-1642 12 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2015
- Published
Adjacency labeling schemes and induced-universal graphs
Alstrup, Stephen, Kaplan, H., Thorup, Mikkel & Zwick, U., 2015, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015: STOC '15. Association for Computing Machinery, p. 625-634 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Construction and impromptu repair of an MST in a distributed network with o(m) communication
King, V., Kutten, S. & Thorup, Mikkel, 2015, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 71-80 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Deterministic global minimum cut of a simple graph in near-linear time
Kawarabayashi, K. & Thorup, Mikkel, 2015, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing: STOC '15. Association for Computing Machinery, p. 665-674 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
From independence to expansion and back again
Christiani, T. L., Pagh, R. & Thorup, Mikkel, 2015, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing: STOC '15. Association for Computing Machinery, p. 813-820 8 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Hashing for statistics over k-partitions
Dahlgaard, S., Knudsen, M. B. T., Rotenberg, E. & Thorup, Mikkel, 2015, Proceedings. 56th Annual Symposium on Foundations of Computer Science. IEEE, p. 1292-1310 19 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Planar reachability in linear space and constant time
Holm, Jacob, Rotenberg, E. & Thorup, Mikkel, 2015, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 370-389 20 p. (Symposium on Foundations of Computer Science. Annual Proceedings).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Sample(x)=(a*x< =t) is a distinguisher with probability 1/8
Thorup, Mikkel, 2015, Proceedings. 56th Annual Symposium on Foundations of Computer Science. IEEE, p. 1277-1291 15 p. (Symposium on Foundations of Computer Science. Annual Proceedings).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2014
- Published
Approximately minwise independence with twisted tabulation
Dahlgaard, S. & Thorup, Mikkel, 2014, Algorithm Theory – SWAT 2014: 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings. Ravi, R. & Gørtz, I. L. (eds.). Springer, p. 134-145 12 p. (Lecture notes in computer science, Vol. 8503).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Coloring 3-colorable graphs with o(n 1/5) colors
Kawarabayashi, K. & Thorup, Mikkel, 2014, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Mayr, E. W. & Portier, N. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 458-469 12 p. (Leibniz International Proceedings in Informatics, Vol. 25).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Dynamic integer sets with optimal rank, select, and predecessor search
Patrascu, M. & Thorup, Mikkel, 2014, FOCS 2014: 55th Annual Symposium on Foundations of Computer Science. IEEE, p. 166-175 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2013
- Published
Bottom-k and priority sampling, set similarity and subset sums with minimal independence
Thorup, Mikkel, 2013, STOC '13: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing. Association for Computing Machinery, p. 371-380 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
More compact oracles for approximate distances in undirected planar graphs
Kawarabayashi, K., Sommer, C. & Thorup, Mikkel, 2013, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Khanna, S. (ed.). Association for Computing Machinery, p. 550-563 14 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Nearest neighbor classification using bottom-k sketches
Dahlgaard, S., Igel, Christian & Thorup, Mikkel, 2013, 2013 IEEE International Conference on Big Data: proceedings. IEEE, p. 28-34 7 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
RAM-efficient external memory sorting
Arge, L. & Thorup, Mikkel, 2013, Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings. Cai, L., Cheng, S-W. & Lam, T-W. (eds.). Springer, p. 491-501 11 p. (Lecture notes in computer science, Vol. 8283).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
ID: 34257574
Most downloads
-
2501
downloads
Coloring 3-colorable graphs with o(n 1/5) colors
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Published -
132
downloads
Incremental exact min-cut in poly-logarithmic amortized update time
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Published -
104
downloads
Bottleneck paths and trees and deterministic graphical games
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Published