Publications

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

Jamalabadi, S., Schwiegelshohn, C. & Schwiegelshohn, U. (2020). Commitment and Slack for Online Load Maximization. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (pp. 339–348). Association for Computing Machinery. https://doi.org/10.1145/3350755.3400271

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

Schmidt, M., Schwiegelshohn, C. & Sohler, C. (2020). Fair Coresets and Streaming Algorithms for Fair k-means. In E. Bampis & N. Megow (Eds.), Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Revised Selected Papers (pp. 232-251). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 11926 LNCS https://doi.org/10.1007/978-3-030-39479-0_16

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

Afshani, P., Killmann, R. & Larsen, K. G. (2022). Hierarchical Categories in Colored Searching. In S. W. Bae & H. Park (Eds.), 33rd International Symposium on Algorithms and Computation, ISAAC 2022 [25] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 248 https://doi.org/10.4230/LIPIcs.ISAAC.2022.25

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

Larsen, K. G. & Nguyen, H. L. (2012). Improved Range Searching Lower Bounds. In Proceedings of the 2012 symposuim on Computational Geometry: Chapel Hill, NC, USA — June 17 - 20, 2012 (pp. 171-178). Association for Computing Machinery. https://doi.org/10.1145/2261250.2261275

Afshani, P. (2012). Improved pointer machine and I/O lower bounds for simplex range reporting and related problems. In Proceedings of the 2012 Symposuim on Computational Geometry, SoCG (pp. 339-346 ). Association for Computing Machinery. https://doi.org/10.1145/2261250.2261301

Afshani, P. & Phillips, J. M. (2019). Independent range sampling, revisited again. In G. Barequet & Y. Wang (Eds.), 35th International Symposium on Computational Geometry, SoCG 2019 [4] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 129 https://doi.org/10.4230/LIPIcs.SoCG.2019.4

Afshani, P., Iacono, J., Jayapaul, V., Karsin, B. & Sitchinava , N. (2022). Locality-of-Reference Optimality of Cache-Oblivious Algorithms. In 3rd Symposium on Algorithmic Principles of Computer Systems, (APOCS) (pp. 31 - 45). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977059.3

Displaying results 201 to 250 out of 340