Algorithms

  • Postal addressShow on map

    Rued Langgaards Vej 7, 4B corridor, RLV

    2300 Copenhagen

    Denmark

Search results

  • 2017

    Theory and Applications of Hashing (Dagstuhl Seminar 17181)

    Dietzfelbinger, M., Mitzenmacher, M., Pagh, R. & Woodruff, D., 2017, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. (Dagstuhl Reports; No. 5, Vol. 7).

    Research output: Book / Anthology / Report › Report › Research

    Open Access
  • 2016

    A Cache-Optimal Alternative to the Unidirectional Hierarchization Algorithm

    Hupp, P. & Jacob, R., 17 Mar 2016, Sparse Grids and Applications - Stuttgart 2014. Springer, p. 103-132 (Lecture Notes in Computational Science and Engineering, Vol. 109).

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
    File

  • Approximate furthest neighbor with application to annulus query

    Pagh, R., Silvestri, F., Sivertsen, J. V. T. & Skala, M., 22 Jul 2016, In: Information Systems.

    Research output: Journal Article or Conference Article in Journal › Conference article › Research › peer-review

    Open Access

  • Approximate unsupervised summary optimisation for selections of ROUGE

    Schluter, N. E. & Martínez Alonso, H., 2016, Proceedings of the 23rd French Conference on Natural Language Processing (Traitement Automatique des Langues Naturelles): Actes de la conférence conjointe JEP-TALN-RECITAL 2016, volume 2 : TALN. Paris, France: Association Francophone pour la Communication Parlée (AFCP) et Association pour le Traitement Automatique des Langues (ATALA), p. 349-354

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access

  • A structural query system for Han characters

    Skala, M., Jan 2016, In: International Journal of Asian Language Processing. 23, 2, p. 127-159

    Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

    Open Access

  • Bit-Vector Search Filtering with Application to a Kanji Dictionary

    Skala, M., 2016, Similarity Search and Applications: 9th International Conference, SISAP 2016, Tokyo, Japan, October 24-26, 2016. Springer, p. 138-150 (Lecture Notes in Computer Science, Vol. 9939).

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
    File

  • COMPUTER-IMPLEMENTED METHOD OF PERFORMING A SEARCH USING SIGNATURES

    Pagh, R. (Inventor), 22 Dec 2016, IPC No. G06F17/30, Patent No. US2016371331 (A1) ― 2016-12-22, Priority date 19 Jun 2015, Priority No. DKPA201570376 20150619

    Research output: Patent

  • Counting Zeros in Random Walks on the Integers and Analysis of Optimal Dual-Pivot Quicksort

    Aumüller, M., Dietzfelbinger, M., Heuberger, C., Krenn, D. & Prodinger, H., 4 Jul 2016, Proceedings of the 27th Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms. Jagiellonian University in Krakow, 13 p.

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access

  • Cuckoo hashing

    Pagh, R., 2016, Encyclopedia of Algorithms: 2nd edition. 2 ed. Springer

    Research output: Conference Article in Proceeding or Book/Report chapter › Encyclopedia chapter › Research › peer-review

  • Efficiently Correcting Matrix Products

    Gąsieniec, L., Levcopoulos, C., Lingas, A., Pagh, R. & Tokuyama, T., 22 Aug 2016, In: Algorithmica. p. 1-16

    Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

    Open Access
    File

  • Fast Bayesian Non-Negative Matrix Factorisation and Tri-Factorisation

    Brouwer, T., Frellsen, J. & Liò, P., 9 Dec 2016.

    Research output: Contribution to conference - NOT published in proceeding or journal › Paper › Research › peer-review

    Open Access

  • Global communication schemes for the numerical solution of high-dimensional PDEs

    Hupp, P., Heene, M., Jacob, R. & Pflüger, D., Feb 2016, In: Parallel Computing. 52, p. 78-105

    Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

    File

  • How Good Is Multi-Pivot Quicksort?

    Aumüller, M., Dietzfelbinger, M. & Klaue, P., 1 Nov 2016, In: ACM Transactions on Algorithms. 13, 1, 8.

    Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

    Open Access
    File

  • Locality-sensitive Hashing without False Negatives

    Pagh, R., 2016, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, p. 1-9

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

  • Network-Oblivious Algorithms

    Bilardi, G., Pietracaprina, A., Pucci, G., Scquizzato, M. & Silvestri, F., Mar 2016, In: Journal of the ACM. 63, 1, 36 p., 3.

    Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

    Open Access
    File

  • On the Complexity of Inner Product Similarity Join

    Ahle, T. D., Pagh, R., Razenshteyn, I. & Silvestri, F., 2016, PODS '16 Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Association for Computing Machinery, p. 151-164

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access

  • Scalability and Total Recall with Fast CoveringLSH

    Pham, N. D. & Pagh, R., 2016, Proceedings of the 25th ACM International on Conference on Information and Knowledge Management: CIKM '16. Association for Computing Machinery, p. 1109-1118

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
    File

  • Timeability in Extensive-Form Games

    Jakobsen, S. K., Sørensen, T. B. & Conitzer, V., 2016, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. Sudan, M. (ed.). 7 ed. Association for Computing Machinery, p. 191-199 9 p.

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
  • 2015

    Approximate Furthest Neighbor in High Dimensions

    Pagh, R., Silvestri, F., Sivertsen, J. V. T. & Skala, M., 2015, Similarity Search and Applications: 8th International Conference, SISAP 2015, Glasgow, UK, October 12–14, 2015, Proceedings. Springer, p. 3-14 (Lecture Notes in Computer Science, Vol. 9371).

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
    File

  • Approximate Range Emptiness in Constant Time and Optimal Space

    Goswami, M., Jørgensen, A. G., Larsen, K. G. & Pagh, R., 2015, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, p. 769-775

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

  • Approximate Well-supported Nash Equilibria Below Two-thirds

    Fearnley, J., Goldberg, P. W., Savani, R. & Sørensen, T. B., 2015, In: Algorithmica. 76, 2, p. 297-319 23 p.

    Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

    Open Access

  • Computation of Stackelberg Equilibria of Finite Sequential Games

    Bosanski, B., Branzei, S., Hansen, K. A., Miltersen, P. B. & Sørensen, T. B., 9 Dec 2015, LNCS 9470 - Web and Internet Economics: 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings. Markakis, E. & Schäfer, G. (eds.). Springer, p. 201-215 (Lecture Notes in Computer Science).

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
    File

  • Exact Graph Coloring Using Inclusion-Exclusion

    Björklund, A. & Husfeldt, T., 13 Feb 2015, Encyclopedia of Algorithms. Ming-Yang, K. (ed.). Springer, p. 1-2 2 p.

    Research output: Conference Article in Proceeding or Book/Report chapter › Encyclopedia chapter › Research › peer-review

  • Experimental Evaluation of Multi-Round Matrix Multiplication on MapReduce

    Ceccarello, M. & Silvestri, F., 5 Jan 2015, Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX). Brandes, U. & Eppstein, D. (eds.). Society for Industrial and Applied Mathematics, p. 119-132

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

  • Fast Output-sensitive Matrix Multiplication

    Jacob, R. & Stöckel, M., 14 Sept 2015, Algorithms - ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings. Springer, p. 766-778 12 p. (Lecture Notes in Computer Science, Vol. 9294).

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
    File

  • From Independence to Expansion and Back Again

    Christiani, T. L., Pagh, R. & Thorup, M., 2015, STOC '15 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing. Association for Computing Machinery, p. 813-820

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

  • Graph Colouring Algorithms

    Husfeldt, T., May 2015, Topics in Chromatic Graph Theory. Beineke, L. W. & Wilson, R. J. (eds.). Cambridge University Press, p. 277-303 (Encyclopedia of Mathematics and Its Applications; No. 156).

    Research output: Conference Article in Proceeding or Book/Report chapter › Book chapter › Research › peer-review

  • I/O-Efficient Similarity Join

    Pagh, R., Pham, N. D., Silvestri, F. & Stöckel, M., 14 Sept 2015, Algorithms - ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings. Springer, p. 941-952 12 p. (Lecture Notes in Computer Science, Vol. 9294).

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
    File

  • Large-Scale Similarity Joins With Guarantees

    Pagh, R., 2015, 18th International Conference on Database Theory (ICDT 2015). Vol. 31. p. 15-24 (Leibniz International Proceedings in Informatics).

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
    File

  • M3: Matrix Multiplication on MapReduce

    Silvestri, F. & Ceccarello, M., 2015

    Research output: Other contribution › Research

  • Monstret i Turings bibliotek

    Translated title of the contribution: The Monster in the Library of TuringHusfeldt, T., 2015, In: Filosofisk Tidskrift. 4

    Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

  • Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence

    Knudsen, M. B. T. & Stöckel, M., 2015, Algorithms – ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings. Springer, Vol. 9294. p. 828-839 (Lecture Notes in Computer Science).

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
    File

  • Randomized Primitives for Big Data Processing

    Stöckel, M., 2015, IT-Universitetet i København. 155 p.

    Research output: Theses › PhD thesis

    Open Access
    File

  • The Input/Output Complexity of Sparse Matrix Multiplication

    Stöckel, M. & Pagh, R., 2015, Algorithms - ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings. Springer, Vol. 8737. p. 750-761 (Lecture Notes in Computer Science).

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
    File

  • The Parity of Set Systems under Random Restrictions with Applications to Exponential Time Problems

    Björklund, A., Dell, H. & Husfeldt, T., 2015, Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015, (6-10 July 2015, Kyoto, Japan). Springer, p. 231-242 12 p. (Lecture Notes in Computer Science, Vol. 9134).

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

    Open Access
    File

  • Triangle Counting in Dynamic Graph Streams

    Bulteau, L., Froese, V., Pagh, R. & Kutzkov, K., 23 Jul 2015, In: Algorithmica.

    Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

    Open Access
    File

  • Valhemligheten bör inte vara valfri

    Husfeldt, T., 25 May 2015, In: Dagens Samhälle.

    Research output: Journal Article or Conference Article in Journal › Contribution to newspaper - Newspaper article

  • 2014

    Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I

    Esparza, J., Fraigniaud, P. (Editor), Husfeldt, T. (Editor) & Koutsoupias, E. (Editor), 2014, Springer. 1086 p. (Lecture Notes in Computer Science).

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

  • Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II

    Esparza, J. (Editor), Fraigniaud, P., Husfeldt, T. & Koutsoupias, E., 2014, Springer. 619 p. (Lecture Notes in Computer Science).

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

  • Beat the Cheater: Computing Game-Theoretic Strategies for When to Kick a Gambler out of a Casino

    Sørensen, T. B., Dalis, M., Korzhyk, D., Conitzer, V. & Letchford, J., Aug 2014, Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. AAAI Press, Vol. 1. p. 798-804 7 p.

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

  • Cache-oblivious Hashing

    Pagh, R., Wei, Z., Yi, K. & Zhang, Q., Aug 2014, In: Algorithmica. 69, 4

    Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

  • Consistent subset sampling

    Kutzkov, K. & Pagh, R., 2014, In: Lecture Notes in Computer Science. 8503, p. 294-305

    Research output: Journal Article or Conference Article in Journal › Conference article › Research › peer-review

  • Cycle-Maximal Graphs of Fixed Girth

    Skala, M., 2014.

    Research output: Contribution to conference - NOT published in proceeding or journal › Conference abstract for conference › Research

  • Den personlige virkelighed

    Translated title of the contribution: Personal realityHusfeldt, T., 4 Jul 2014, In: Weekendavisen. 27, 2 p.

    Research output: Journal Article or Conference Article in Journal › Contribution to newspaper - Newspaper article

  • Efficient estimation for high similarities using odd sketches

    Mitzenmacher, M., Pagh, R. & Pham, N. D., 2014, Proceedings of the 23rd international conference on World wide web: WWW '14. Association for Computing Machinery, p. 109-118 10 p.

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

  • Efficient Representation for Online Suffix Tree Construction

    Larsson, N. J., Fuglsang, K. & Karlsson, K., 2014, Experimental Algorithms: 13th International Symposium, SEA 2014. Gudmundsson, J. & Katajainen, J. (eds.). Springer, p. 400-411 12 p. (Lecture Notes in Computer Science, Vol. 8504).

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

  • Exponential Time Complexity of the Permanent and the Tutte Polynomial

    Dell, H., Husfeldt, T., Marx, D., Taslaman, N. S. & Wahlén, M., 2014, In: A C M Transactions on Algorithms. 10, 4, p. 21:1-21:32 32 p., 21.

    Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

  • Generating k-independent variables in constant time

    Christiani, T. L. & Pagh, R., 2014, Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on. IEEE, p. 196-205

    Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

  • Indexed Geometric Jumbled Pattern Matching

    Durocher, S., Fraser, R., Gagie, T., Mondal, D., Skala, M. & Thankachan, S., 2014, In: Lecture Notes in Computer Science. 8486, p. 110-119 10 p.

    Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

  • Integer Set Compression and Statistical Modeling

    Larsson, N. J., 2014

    Research output: Other contribution › Net publication - Internet publication › Research