Algorithms

  • Postal addressShow on map

    4B corridor

    2300 Copenhagen

    Denmark

Search results

  • 2016

    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. (ITU-DS; No. 108).

    Research output: Book / Anthology / Report / Ph.D. thesis › Ph.D. 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 Science+Business Media. 1086 p. (Lecture Notes in Computer Science).

    Research output: Book / Anthology / Report / Ph.D. thesis › 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 Science+Business Media. 619 p. (Lecture Notes in Computer Science).

    Research output: Book / Anthology / Report / Ph.D. thesis › 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

  • Is Min-Wise Hashing Optimal for Summarizing Set Intersection?

    Pagh, R., Stöckel, M. & Woodruff, D., 2014, Proceedings of the 2014 ACM SIGMOD international conference on Management of data. Association for Computing Machinery, p. 109-120

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

  • Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees

    Durocher, S., Shah, R., Skala, M. & Thankachan, S. V., Oct 2014, In: Algorithmica.

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

  • Linear-Space Data Structures for Range Minority Query in Arrays

    Chan, T. M., Durocher, S., Skala, M. & Wilkinson, B. T., 2014, In: Algorithmica. 72, 4, p. 901-913

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

  • Listing Triangles

    Björklund, A., Pagh, R., Vassilevska Williams, V. & Zwick, U., 2014, Automata, Languages, and Programming, 41st International Colloquium, ICALP 2014. Springer, p. 223-234

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

  • MapReduce Triangle Enumeration With Guarantees

    Park, H.-M., Silvestri, F., Kang, U. & Pagh, R., 2014, CIKM '14 Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management . Association for Computing Machinery, p. 1739-1748

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

  • Most Recent Match Queries in On-Line Suffix Trees

    Larsson, N. J., 2014, In: Lecture Notes in Computer Science. 8486, p. 252-261 10 p.

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

  • On the Power of Randomization in Big Data Analytics

    Pham, N. D., 7 Oct 2014, IT University of Copenhagen: IT-Universitetet i København. 117 p. (ITU-DS; No. 105, Vol. 1602-3536).

    Research output: Book / Anthology / Report / Ph.D. thesis › Ph.D. thesis

    Open Access
    File

  • Preface

    Esparza, J., Fraigniaud, P., Husfeldt, T. & Koutsoupias, E., 2014, Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. Springer, Vol. 8572. p. 5-6 2 p. (Lecture Notes in Computer Science, Vol. 8572).

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

  • Robust Nonparametric Simplification of Polygonal Chains

    Durocher, S., Leblanc, A., Morrison, J. & Skala, M., 2014, In: International Journal of Computational Geometry and Applications. 23, 6

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

  • Shortest Two Disjoint Paths in Polynomial Time

    Björklund, A. & Husfeldt, T., 2014, Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. 12 p. (Lecture Notes in Computer Science, Vol. 8572).

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

  • Subgraph Enumeration in Massive Graphs

    Silvestri, F., 11 Sept 2014.

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

    File

  • The CAP Theorem Versus Databases with Relaxed ACID properties

    Frank, L., Pedersen, R. U., Havnø Frank, C. & Larsson, J., Jan 2014, Proceedings of the 8th International Conference on Ubiquitous Information Management and Communication. Association for Computing Machinery, p. 78:1--78:7 7 p. 78

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