Publications

Brodal, G. S. & Fagerberg, R. (2002). Cache Oblivious Distribution Sweeping. In P. Widmayer, S. Eidenbenz, F. Triguero, R. Morales, R. Conejo & M. Hennessy (Eds.), Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings (pp. 426-438). Springer. Lecture Notes in Computer Science Vol. 2380 https://doi.org/10.1007/3-540-45465-9_37

Brodal, G. S. & Mampentzidis, K. (2017). Cache oblivious algorithms for computing the triplet distance between trees. In K. Pruhs & C. Sohler (Eds.), 25th European Symposium on Algorithms, ESA 2017 (Vol. 87, pp. 21:1--21:14). [21] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics Vol. 87 https://doi.org/10.4230/LIPIcs.ESA.2017.21

Brodal, G. S., Fagerberg, R. & Moruz, G. (2005). Cache-Aware and Cache-Oblivious Adaptive Sorting. In L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi & M. Yung (Eds.), Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. Proceedings (pp. 576-588). Springer. Lecture Notes in Computer Science Vol. 3580 https://doi.org/10.1007/11523468_47

Brodal, G. S., Fagerberg, R., Meyer, U. & Zeh, N. (2004). Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths. In T. Hagerup & J. Katajainen (Eds.), Algorithm Theory - SWAT 2004: 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004. Proceedings (pp. 480-492). Springer. Lecture Notes in Computer Science Vol. 3111 https://doi.org/10.1007/978-3-540-27810-8_41

Arge, L., Brodal, G. S., Fagerberg, R. & Laustsen, M. (2005). Cache-Oblivious Planar Orthogonal Range Searching and Counting. In Proceedings of the twenty-first annual symposium on Computational geometry (pp. 160-169). Association for Computing Machinery. https://doi.org/10.1145/1064092.1064119

Brodal, G. S., Fagerberg, R. & Jacob, R. (2002). Cache-Oblivious Search Trees via Binary Trees of Small Height. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (pp. 39-48). Association for Computing Machinery.

Brodal, G. S. & Fagerberg, R. (2006). Cache-oblivious String Dictionaries. In SODA '06 Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (pp. 581-590). Association for Computing Machinery. https://doi.org/10.1145/1109557.1109621

Haxen, M., Raeburn, M., Afshani, P. & Karras, P. (2021). Centerpoint Query Authentication. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management (CIKM '21) (pp. 3083-3087). Association for Computing Machinery. https://doi.org/10.1145/3459637.3482072

Arge, L. A., Larsen, K. G., Mølhave, T. & Walderveen, F. V. (2010). Cleaning Massive Sonar Point Clouds. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. GIS '10 (pp. 152-161). Association for Computing Machinery. https://doi.org/10.1145/1869790.1869815

Green Larsen, K., Mitzenmacher, M. & Tsourakakis, C. (2020). Clustering with a faulty oracle. In Y. Huang, I. King, T-Y. Liu & M. van Steen (Eds.), WWW '20: Proceedings of The Web Conference 2020 (pp. 2831-2834). Association for Computing Machinery. https://doi.org/10.1145/3366423.3380045

Damgård, I., Larsen, K. G. & Nielsen, J. B. (2019). Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing. In A. Boldyreva & D. Micciancio (Eds.), Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings (Vol. II, pp. 61-84). Springer. Lecture Notes in Computer Science Vol. 11693 https://doi.org/10.1007/978-3-030-26951-7_3

Brodal, G. S. & Pinotti, M. C. (1998). Comparator networks for binary heap construction. In S. Arnborg & L. Ivansson (Eds.), Algorithm Theory — SWAT'98: 6th Scandinavian Workshop on Algorithm Theory Stockholm, Sweden, July 8–10, 1998 Proceedings (pp. 158-168). Springer. Lecture Notes in Computer Science Vol. 1432 https://doi.org/10.1007/BFb0054364

Brodal, G. S., Fagerberg, R., Östlin, A., Pedersen, C. N. S. & Rao, S. S. (2003). Computing Refined Buneman Trees in Cubic Time. In G. Benson & R. Page (Eds.), Algorithms in Bioinformatics: Third International Workshop, WABI 2003, Budapest, Hungary, September 15-20, 2003. Proceedings (pp. 259-270). Springer. Lecture Notes in Computer Science Vol. 2812 https://doi.org/10.1007/978-3-540-39763-2_20

Stissing, M., Mailund, T., Pedersen, C. N. S., Brodal, G. S. & Fagerberg, R. (2007). Computing the All-Pairs Quartet Distance on a Set of Evolutionary Trees. In Proceedings of the 5th Asia-Pacific Bioinformatics Conference (APBC) (pp. 91-100)

Brodal, G. S., Fagerberg, R., Pedersen, C. N. S., Eades, P. (Ed.) & Takaoka, T. (Ed.) (2001). Computing the Quartet Distance Between Evolutionary Trees in Time O(n log² n). In Proceedings of Algorithms and Computation : 12th International Symposium, ISAAC 2001 (2223 of Lecture Notes in Computer Science ed., Vol. 2223/2001, pp. 731-742). Springer.

Stissing, M., Pedersen, C. N. S., Mailund, T. & Brodal, G. S. (2007). Computing the Quartet Distance between Evolutionary Trees of Bounded Degree. In Proceedings of the 5th Asia-Pacific Bioinformatics Conference (APBC) (pp. 101-110)

Afshani, P., Sheng, C., Tao, Y. & Wilkinson, B. T. (2014). Concurrent range reporting in two-dimensional space. In C. Chekuri (Ed.), Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms: SODA 2014; Portland, OR; United States; 5 January 2014 through 7 January 2014 (pp. 983-994). Association for Computing Machinery. http://www.scopus.com/inward/record.url?scp=84902105500&partnerID=8YFLogxK

Larsen, K. G. (2019). Constructive Discrepancy Minimization with Hereditary L2 Guarantees. In R. Niedermeier & C. Paul (Eds.), 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) [48] Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. Leibniz International Proceedings in Informatics Vol. 126 https://doi.org/10.4230/LIPIcs.STACS.2019.48

Larsen, K. G., Pagh, R. & Tetek, J. (2021). CountSketches, Feature Hashing and the Median of Three. In M. Meila & T. Zhang (Eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event (pp. 6011-6020). Proceedings of Machine Learning Research Vol. 139 http://proceedings.mlr.press/v139/larsen21a.html

Afshani, P., Bender, M. A., Farach-Colton, M., Fineman, J. T., Goswami, M. & Tsai, M. T. (2017). Cross-Referenced dictionaries and the limits of write optimization. In P. N. Klein (Ed.), 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 (pp. 1523-1532). Association for Computing Machinery.

Larsen, K. G., Weinstein, O. & Yu, H. (2018). Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. In M. Henzinger, D. Kempe & I. Diakonikolas (Eds.), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 978-989). Association for Computing Machinery. A C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings No. 2018 https://doi.org/10.1145/3188745.3188790

Brodal, G. S., Sioutas, S., Tsichlas, K. & Zaroliagis, C. (2010). D²-tree: A new overlay with deterministic bounds. In O. Cheong , K-Y. Chwa & K. Park (Eds.), Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju, Korea, December 15-17, 2010, Proceedings, Part II (pp. 1-12). Springer VS. Lecture Notes in Computer Science Vol. 6507 https://doi.org/10.1007/978-3-642-17514-5_1

Afshani, P. & Nielsen, J. A. S. (2016). Data Structure Lower Bounds for Document Indexing Problems. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani & D. Sangiorgi (Eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (Vol. 55, pp. 93:1-93:15). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. Leibniz International Proceedings in Informatics Vol. 55 https://doi.org/10.4230/LIPIcs.ICALP.2016.93

Eenberg, K., Larsen, K. G. & Yu, H. (2017). DecreaseKeys are expensive for external memory priority queues. In STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Vol. Part F128415, pp. 1081-1093). Association for Computing Machinery. https://doi.org/10.1145/3055399.3055437

Afshani, P., Chan, T. M. & Tsakalidis, K. (2014). Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM. In J. Esparza , P. Fraigniaud, T. Husfeldt & E. Koutsoupias (Eds.), Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I (pp. 77-88 ). Springer VS. Lecture Notes in Computer Science Vol. 8572 https://doi.org/10.1007/978-3-662-43948-7_7

Brodal, G. S., Georgiadis, L., Hansen, K. A. & Katriel, I. (2007). Dynamic Matchings in Convex Bipartite Graphs. In L. Kucera & A. Kucera (Eds.), Proc. 32nd International Symposium on Mathematical Foundations of Computer Science (pp. 406-417). Springer. Lecture Notes in Computer Science Vol. 4708 https://doi.org/10.1007/978-3-540-74456-6_37

Brodal, G. S. & Jacob, R. (2002). Dynamic Planar Convex Hull. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science: (pp. 617-626). IEEE Press. https://doi.org/10.1109/SFCS.2002.1181875

Brodal, G. S. & Jakob, R. (2000). Dynamic Planar Convex Hull with Optimal Query Time and O(log n · log log n ) Update Time. In Algorithm Theory - SWAT 2000: 7th Scandinavian Workshop on Algorithm Theory Bergen, Norway, July 5–7, 2000 Proceedings (pp. 181-186). Springer. Lecture Notes in Computer Science Vol. 1851 https://doi.org/10.1007/3-540-44985-X_7

Brodal, G. S. & Fagerberg, R. (1999). Dynamic Representations of Sparse Graphs. In F. Dehne, J-R. Sack, A. Gupta & R. Tamassia (Eds.), Algorithms and Data Structures: 6th International Workshop, WADS’99 Vancouver, Canada, August 11–14, 1999 Proceedings (pp. 773-782). Springer. Lecture Notes in Computer Science Vol. 1663 https://doi.org/10.1007/3-540-48447-7_34

Belazzougui, D., Brodal, G. S. & Nielsen, J. A. S. (2014). Expected linear time sorting for word size Ω(log² n log log n). In R. Ravi & I. L. Gørtz (Eds.), Algorithm Theory – SWAT 2014: 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings (pp. 26-37). Springer VS. Lecture Notes in Computer Science Vol. 8503 https://doi.org/10.1007/978-3-319-08404-6_3

Arge, L., Brodal, G. S. & Satti, S. R. (2008). External Memory Planar Point Location with Logarithmic Updates. In M. Teilaud (Ed.), Proceedings of the twenty-fourth annual symposium on Computational geometry (pp. 139-147). Association for Computing Machinery. https://doi.org/10.1145/1377676.1377699

Brodal, G. S. (2016). External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates. In N. Ollinger & H. Vollmer (Eds.), 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) (Vol. 47, pp. 23:1-23:14). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. Leibniz International Proceedings in Informatics https://doi.org/10.4230/LIPIcs.STACS.2016.23

de Berg, M., Tsirogiannis, C. & Wilkinson, B. (2015). Fast Computation of Categorical Richness on Raster Data Sets and Related Problems. In Proceedings. Workshop on Massive Data Algorithmics (MASSIVE) (pp. 86-107)

Afshani, P. (2014). Fast Computation of Output-Sensitive Maxima in a Word RAM. In C. Chekuri (Ed.), Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms: SODA 2014; Portland, OR; United States; 5 January 2014 through 7 January 2014 (pp. 1414-1423). Association for Computing Machinery. http://www.scopus.com/inward/record.url?scp=84902105500&partnerID=8YFLogxK

de Berg, M., Tsirogiannis, C. & Wilkinson, B. T. (2015). Fast computation of categorical richness on raster data sets and related problems. In GIS '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems [18] https://doi.org/10.1145/2820783.2820825

Brodal, G. S. (1995). Fast meldable priority queues. In S. G. Akl, F. Dehne, J-R. Sack & N. Santoro (Eds.), Algorithms and Data Structures: 4th International Workshop, WADS '95 Kingston, Canada, August 16–18, 1995 Proceedings (pp. 282-290). Springer. Lecture Notes in Computer Science Vol. 955 https://doi.org/10.1007/3-540-60220-8_70

Brodal, G. S., Kaligosi, K., Katriel, I. & Kutz, M. (2006). Faster Algorithms for Computing Longest Common Increasing Subsequences. In M. Lewenstein & G. Valiente (Eds.), Combinatorial Pattern Matching (pp. 330-341). Springer. Lecture Notes in Computer Science Vol. 4009 https://doi.org/10.1007/11780441_30

Larsen, K. G. & Williams, R. (2017). Faster Online Matrix-Vector Multiplication. In P. N. Klein (Ed.), Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. PRDA17, pp. 2182-2189). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974782

Brodal, G. S., Lyngsø, R. B., Pedersen, C. N. S. & Stoye, J. (1999). Finding Maximal Pairs with Bounded Gap. In M. Crochemore & M. Paterson (Eds.), Combinatorial Pattern Matching: 10th Annual Symposium, CPM 99 Warwick University, UK, July 22–24, 1999 Proceedings (pp. 134-149). Springer. Lecture Notes in Computer Science Vol. 1645 https://doi.org/10.1007/3-540-48452-3_11

Brodal, G. S. & Pedersen, C. N. S. (2000). Finding Maximal Quasiperiodicities in Strings. In R. Giancarlo & D. Sankoff (Eds.), Combinatorial Pattern Matching: 11th Annual Symposium, CPM 2000 Montreal, Canada, June 21–23, 2000 Proceedings (pp. 397-411). Springer. Lecture Notes in Computer Science Vol. 1848 https://doi.org/10.1007/3-540-45123-4_33

Brodal, G. S. (1998). Finger search trees with constant insertion time. In Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms (pp. 540-549). Society for Industrial and Applied Mathematics.

Afshani, P., Fagerberg, R., Hammer, D., Jacob, R., Kostitsyna, I., Meyer, U., Penschuck, M. & Sitchinava, N. (2019). Fragile complexity of comparison-based algorithms. In M. A. Bender, O. Svensson & G. Herman (Eds.), 27th Annual European Symposium on Algorithms, ESA 2019 [2] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 144 https://doi.org/10.4230/LIPIcs.ESA.2019.2

Larsen, K. G., Nelson, J., Nguyen, H. L. & Thorup, M. (2016). Heavy hitters via cluster-preserving clustering. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 61-70). IEEE. https://doi.org/10.1109/FOCS.2016.16

Larsen, K. G. (2012). Higher Cell Probe Lower Bounds for Evaluating Polynomials. In FOCS'12: IEEE 53rd Annual Symposium on Foundations of Computer Science (pp. 293 - 301 ). IEEE Computer Society Press. https://doi.org/10.1109/FOCS.2012.21

Arge, L., Afshani, P. & Larsen, K. G. (2012). Higher-dimensional Orthogonal Range Reporting and Rectangle Stabbing in the Pointer Machine Model. In Proceedings of the 2012 Symposuim on Computational Geometry (pp. 323-338). Association for Computing Machinery. https://doi.org/10.1145/2261250.2261299

Baum, C., Damgård, I. B., Larsen, K. G. & Nielsen, M. (2016). How to prove knowledge of small secrets. In J. Katz & M. Robshaw (Eds.), Annual Cryptology Conference : CRYPTO 2016: Advances in Cryptology – CRYPTO 2016 (Vol. 9816, pp. 478-498). Springer VS. Lecture Notes in Computer Science Vol. 9816 https://doi.org/10.1007/978-3-662-53015-3_17

Kejlberg-Rasmussen, C., Tao, Y., Tsakalidis, K., Tsichlas, K. & Yoon, J. (2013). I/O-Efficient Planar Range Skyline and Attrition Priority Queues. In R. Hull & W. Fan (Eds.), Proceedings of the 32nd symposium on Principles of database systems , PODS '13 (pp. 103-114 ). Association for Computing Machinery. A C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings https://doi.org/10.1145/2463664.2465225

Agarwal, P. K., Arge, L. A., Brodal, G. S. & Vitter, J. S. (1999). I/O-efficient dynamic point location in monotone planar subdivisions. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms (pp. 11-20). Association for Computing Machinery.

Afshani, P. & Sitchinava, N. (2014). I/O-efficient range minima queries. In R. Ravi & I. L. Gørtz (Eds.), Algorithm Theory – SWAT 2014: 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings (pp. 1-12). Springer VS. Lecture Notes in Computer Science Vol. 8503 https://doi.org/10.1007/978-3-319-08404-6_1

Brodal, G. S., Arge, L. & Georgiadis, L. (2006). Improved Dynamic Planar Point Location. In Proceedings of the 47th Annual Symposium on Foundations of Computer Science (pp. 305-314). IEEE. https://doi.org/10.1109/FOCS.2006.40

Displaying results 51 to 100 out of 311