Mikkel Thorup
Professor
- 2023
- Published
A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing
Houen, Jakob Bæk Tejs & 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 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
- 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
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
- Published
Locally Uniform Hashing
Bercea, I. O., Beretta, Lorenzo, Klausen, Jonas Østergaard, Houen, Jakob Bæk Tejs & 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
- 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 - iResearch output: Contribution to journal › Editorial › Research
- 2022
- Published
Understanding the Moments of Tabulation Hashing via Chaoses
Houen, Jakob Bæk Tejs & 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
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-4001Research output: Contribution to journal › Conference article › Research › peer-review
- Published
On sums of monotone random integer variables
Aamand, Anders, Alon, N., Houen, Jakob Bæk Tejs & Thorup, Mikkel, 2022, In: Electronic Communications in Probability. 27, p. 1-8 64.Research output: Contribution to journal › Journal article › 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
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-304Research output: Contribution to journal › Journal article › Research › peer-review
- 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
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
- Published
Fast hashing with strong concentration bounds
Aamand, Anders, Houen, Jakob Bæk Tejs, 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
- 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
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-137Research output: Contribution to journal › Journal article › Research › peer-review
- 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
- 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
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-100Research output: Contribution to journal › Journal article › 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
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
- 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
- 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-2526Research output: Contribution to journal › Journal article › 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, Jul 2017, In: Communications of the ACM. 60, 7, p. 94-101 8 p.Research output: Contribution to journal › Journal article › Research › peer-review
- 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
- 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
On the k-independence required by linear probing and minwise independence
Pǎtraşcu, M. & Thorup, Mikkel, 2016, In: ACM Transactions on Algorithms. 12, 1, 27 p., 8.Research output: Contribution to journal › Journal article › 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
RAM-efficient external memory sorting
Arge, L. & Thorup, Mikkel, 2015, In: Algorithmica. 73, 4, p. 623-636 14 p.Research output: Contribution to journal › Journal article › 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
Algorithms and estimators for summarization of unaggregated data streams
Cohen, E., Duffield, N., Kaplan, H., Lund, C. & Thorup, Mikkel, 2014, In: Journal of Computer and System Sciences. 80, 7, p. 1214-1244 31 p.Research output: Contribution to journal › Journal article › Research › peer-review
- 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
- Published
Union-find with constant time deletions
Alstrup, Stephen, Thorup, Mikkel, Gørtz, I. L., Rauhe, T. & Zwick, U., 2014, In: A C M Transactions on Algorithms. 11, 1, 28 p., 6.Research output: Contribution to journal › Journal article › 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
Funding successful research
Thorup, Mikkel, 2013, In: Communications of the A C M. 56, 3, p. 38-39 2 p.Research output: Contribution to journal › Comment/debate › Research
Intra-domain traffic engineering with shortest path routing protocols
Altin, A., Fortz, B., Thorup, Mikkel & Ümit, H., 2013, In: Annals of Operations Research. 204, 1, p. 56-95 40 p.Research output: Contribution to journal › Journal article › Research › peer-review
- Published
Mihai Pätrascu: obituary and open problems
Thorup, Mikkel, 2013, In: SIGACT News. 44, 1, p. 110-114 5 p.Research output: Contribution to journal › Journal article › Research
- 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
- Published
Simple tabulation, fast expanders, double tabulation, and high independence
Thorup, Mikkel, 2013, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 90-99 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Twisted tabulation hashing
Thorup, Mikkel & Patrascu, M., 2013, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Khanna, S. (ed.). Association for Computing Machinery, p. 209-228 20 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2012
- Published
A new infinity of distance oracles for sparse graphs
Patrascu, M., Roditty, L. & Thorup, Mikkel, 2012, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 738-747 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Combinatorial coloring of 3-colorable graphs
Kawarabayashi, K. & Thorup, Mikkel, 2012, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE, p. 68-75 8 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
Thorup, Mikkel & Zhang, Y., 2012, In: S I A M Journal on Computing. 41, 2, p. 293-331 39 p.Research output: Contribution to journal › Journal article › Research › peer-review
- Published
The power of simple tabulation hashing
Patracu, M. & Thorup, Mikkel, 2012, In: Association for Computing Machinery. Journal. 59, 3, 50 p., 14.Research output: Contribution to journal › Journal article › Research › peer-review
- 2011
Don't rush into a union: take time to find your roots
Patrascu, M. & Thorup, Mikkel, 2011, Proceedings of the forty-third annual ACM symposium on Theory of computing. Association for Computing Machinery, p. 559-567 9 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Efficient stream sampling for variance-optimal estimation of subset sums
Cohen, E., Duffield, N., Kaplan, H., Lund, C. & Thorup, Mikkel, 2011, In: S I A M Journal on Computing. 40, 5, p. 1402-1431 30 p.Research output: Contribution to journal › Journal article › Research › peer-review
The minimum k-way cut of bounded size is fixed-parameter tractable
Kawarabayashi, K. & Thorup, Mikkel, 2011, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Ostrovsky, R. (ed.). IEEE, p. 160-169 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
The power of simple tabulation hashing
Patrascu, M. & Thorup, Mikkel, 2011, Proceedings of the 43rd annual ACM symposium on Theory of computing. Association for Computing Machinery, p. 1-10 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Timeouts with time-reversed linear probing
Thorup, Mikkel, 2011, 2011 Proceedings IEEE INFOCOM. IEEE, p. 166-170 5 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2010
Changing base without losing space
Dodis, Y., Patracu, M. & Thorup, Mikkel, 2010, Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC). ACM, p. 593-602 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
Madani, O., Thorup, Mikkel & Zwick, U., 2010, In: ACM Transactions on Algorithms. 6, 2Research output: Contribution to journal › Journal article › Research › peer-review
On the k-Independence Required by Linear Probing and Minwise Independence
Pǎtraşcu, M. & Thorup, Mikkel, 2010, Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), Part I, LNCS 6198. Springer, p. 715-726 12 p. (Lecture notes in computer science, Vol. 6198).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Regular Expression Matching with Multi-Strings and Intervals
Bille, P. & Thorup, Mikkel, 2010, SODA. SIAM, p. 1297-1308 12 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Tabulation Based 5-Universal Hashing and Linear Probing
Thorup, Mikkel & Zhang, Y., 2010, Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, p. 62-76 15 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2009
Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets
Cohen, E., Duffield, N. G., Kaplan, H., Lund, C. & Thorup, Mikkel, 2009, In: Proceedings of Very Large Databases (VLDB) Endowment. 2, 1, p. 431-442 12 p.Research output: Contribution to journal › Journal article › Research › peer-review
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
Madani, O., Thorup, Mikkel & Zwick, U., 2009, Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, p. 958-967 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Faster Regular Expression Matching
Bille, P. & Thorup, Mikkel, 2009, Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 5555. Springer, p. 171-182 12 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Higher Lower Bounds for Near-Neighbor and Further Rich Problems
Patracu, M. & Thorup, Mikkel, 2009, In: sicomp. 39, 2, p. 730-741 12 p.Research output: Contribution to journal › Journal article › Research › peer-review
Intra-domain traffic engineering with shortest path routing protocols
Altin, A., Fortz, B., Thorup, Mikkel & Ümit, H., 2009, In: 4OR. 7, 4, p. 301-335 35 p.Research output: Contribution to journal › Journal article › Research › peer-review
Maximum overhang
Paterson, M., Peres, Y., Thorup, Mikkel, Winkler, P. & Zwick, U., 2009, In: American Mathematical Monthly. 116, 9, p. 763-787 25 p.Research output: Contribution to journal › Journal article › Research › peer-review
Stream sampling for variance-optimal estimation of subset sums
Cohen, E., Duffield, N., Kaplan, H., Lund, C. & Thorup, Mikkel, 2009, Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, p. 1255-1264 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
String hashing for linear probing
Thorup, Mikkel, 2009, Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, p. 655-664 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2008
Compact name-independent routing with minimum stretch
Abraham, I., Gavoille, C., Malkhi, D., Nisan, N. & Thorup, Mikkel, 2008, In: ACM Transactions on Algorithms. 4, 3, p. Article 37Research output: Contribution to journal › Journal article › Research › peer-review
Confident estimation for multistage measurement sampling and aggregation
Cohen, E., Duffield, N., Lund, C. & Thorup, Mikkel, 2008, Proceedings the ACM IFIP Conference on Measurement and Modeling of Computer Systems (SIGMETRICS/Performance). ACM, p. 109-120 12 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Maximum overhang
Paterson, M., Peres, Y., Thorup, Mikkel, Winkler, P. & Zwick, U., 2008, Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, p. 756-765 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
ID: 34257574
Most downloads
-
2497
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 -
129
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 -
102
downloads
Bottleneck paths and trees and deterministic graphical games
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Published