Mikkel Thorup

Mikkel Thorup

Professor

Member of:

    ORCID: 0000-0001-5237-1709

    Publication year:
    All
    1 - 50 out of 241Page size: 50
    1. 2024
    2. 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, 2024, In: Journal of the ACM. 71, 2, 41 p., 10.

      Research output: Contribution to journal › Journal article › Research › peer-review

    3. Published

      Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

      Jin, W., Sun, X. & Thorup, Mikkel, 2024, p. 2999-3026. 28 p.

      Research output: Contribution to conference › Paper › Research › peer-review

    4. 2023
    5. 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

    6. Published

      How to Cut Corners and Get Bounded Convex Curvature

      Abrahamsen, Mikkel & Thorup, Mikkel, 2023, In: Discrete and Computational Geometry. 69, p. 1195–1231,

      Research output: Contribution to journal › Journal article › Research › peer-review

    7. 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-1470

      Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

    8. Published

      Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)

      Boyle, E., Cohen-Addad, V., Kolla, A. & Thorup, Mikkel, 2023, In: SIAM Journal on Computing. 52, 6, p. FOCS18 - i

      Research output: Contribution to journal › Editorial › Research

    9. 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-86

      Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

    10. 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

    11. Published

      Fully Dynamic Connectivity in O (log n((log log n)2 Amortized Expected Time

      Huang, S., Huang, D., Kopelowitz, T., Pettie, S. & Thorup, Mikkel, 2023, In: TheoretiCS. 2, p. 1-56 6.

      Research output: Contribution to journal › Journal article › Research › peer-review

    12. 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

    13. 2022
    14. Published

      No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing

      Aamand, A., Das, D., Kipouridis, Evangelos, Knudsen, J. B. T., Rasmussen, Peter Michael Reichstein & Thorup, Mikkel, 2022, In: Proceedings of the VLDB Endowment. 15, 13, p. 3989-4001

      Research output: Contribution to journal › Conference article › Research › peer-review

    15. Published

      On sums of monotone random integer variables

      Aamand, Anders, Alon, N., Houen, J. B. T. & Thorup, Mikkel, 2022, In: Electronic Communications in Probability. 27, p. 1-8 64.

      Research output: Contribution to journal › Journal article › Research › peer-review

    16. 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-12

      Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

    17. 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

    18. 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

    19. 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

    20. 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-26

      Research output: Chapter in Book/Report/Conference proceeding › Book chapter › Research › peer-review

    21. 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

    22. 2021
    23. 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

    24. Published

      Compact cactus representations of all non-trivial min-cuts

      Lo, O. H. S., Schmidt, J. M. & Thorup, Mikkel, 2021, In: Discrete Applied Mathematics. 303, p. 296-304

      Research output: Contribution to journal › Journal article › Research › peer-review

    25. 2020
    26. Published

      Disks in Curves of Bounded Convex Curvature

      Aamand, Anders, Abrahamsen, Mikkel & Thorup, Mikkel, 2020, In: American Mathematical Monthly. 127, 7, p. 579-593 15 p.

      Research output: Contribution to journal › Journal article › Research › peer-review

    27. 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

    28. Published

      No Repetition: Fast Streaming with Highly Concentrated Hashing

      Aamand, Anders, Das, D., Kipouridis, Evangelos, Knudsen, J. B. T., Rasmussen, Peter Michael Reichstein & Thorup, Mikkel, 2020, arXiv.org, 10 p.

      Research output: Working paper › Research

    29. 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

    30. 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

    31. 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

    32. 2019
    33. 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-2512

      Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research

    34. Published

      Adjacency Labeling Schemes and Induced-Universal Graphs

      Alstrup, Stephen, Kaplan, H., Thorup, Mikkel & Zwick, U., 2019, In: SIAM Journal on Discrete Mathematics. 33, 1, p. 116-137

      Research output: Contribution to journal › Journal article › Research › peer-review

    35. 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. 8948658

      Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

    36. Published

      Deterministic Edge Connectivity in Near-Linear Time

      Kawarabayashi, K. & Thorup, Mikkel, 2019, In: Journal of the ACM. 66, 1, p. 1-50 4.

      Research output: Contribution to journal › Journal article › Research › peer-review

    37. Published

      Heavy hitters via cluster-preserving clustering

      Larsen, K. G., Nelson, J., Nguyễn, H. L. & Thorup, Mikkel, 2019, In: Communications of the ACM. 62, 8, p. 95-100

      Research output: Contribution to journal › Journal article › Research › peer-review

    38. 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

    39. 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

    40. 2018
    41. 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

    42. 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-573

      Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

    43. 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-230

      Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

    44. Published

      Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time

      Goranci, G., Henzinger, M. & Thorup, Mikkel, 2018, In: ACM Transactions on Algorithms. 14, 2, 17.

      Research output: Contribution to journal › Journal article › Research › peer-review

    45. 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

    46. 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

    47. 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

    48. Published

      Proceedings, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)

      Thorup, Mikkel (ed.), 2018, IEEE. 996 p.

      Research output: Book/Report › Book › Research › peer-review

    49. Published

      Sample(x)=(a*x <=t) is a distinguisher with probability 1/8

      Thorup, Mikkel, 2018, In: SIAM Journal on Computing. 47, 6, p. 2510-2526

      Research output: Contribution to journal › Journal article › Research › peer-review

    50. 2017
    51. 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

    52. 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

    53. Published

      Coloring 3-colorable graphs with less than n1/5 colors

      Kawarabayashi, K. & Thorup, Mikkel, Mar 2017, In: Journal of the ACM. 64, 1, 23 p., 4.

      Research output: Contribution to journal › Journal article › Research › peer-review

    54. Published

      Fast and powerful hashing using tabulation

      Thorup, Mikkel, Jul 2017, In: Communications of the ACM. 60, 7, p. 94-101 8 p.

      Research output: Contribution to journal › Journal article › Research › peer-review

    55. 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

    56. 2016
    57. 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

    58. 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

    59. 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

    Previous 1 2 3 4 5 Next

    ID: 34257574