Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)
Kasper Green Larsen, Maciej Obremski, and Mark Simkin. Distributed Shuffling in Adversarial Environments. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 10:1-10:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{larsen_et_al:LIPIcs.ITC.2023.10, author = {Larsen, Kasper Green and Obremski, Maciej and Simkin, Mark}, title = {{Distributed Shuffling in Adversarial Environments}}, booktitle = {4th Conference on Information-Theoretic Cryptography (ITC 2023)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-271-6}, ISSN = {1868-8969}, year = {2023}, volume = {267}, editor = {Chung, Kai-Min}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.10}, URN = {urn:nbn:de:0030-drops-183385}, doi = {10.4230/LIPIcs.ITC.2023.10}, annote = {Keywords: Distributed Computing, Shuffling} }
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Meng He and Zhen Liu. Exact and Approximate Range Mode Query Data Structures in Practice. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 19:1-19:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{he_et_al:LIPIcs.SEA.2023.19, author = {He, Meng and Liu, Zhen}, title = {{Exact and Approximate Range Mode Query Data Structures in Practice}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {19:1--19:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.19}, URN = {urn:nbn:de:0030-drops-183693}, doi = {10.4230/LIPIcs.SEA.2023.19}, annote = {Keywords: range mode query, exact range mode query, approximate range mode query} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Ora Nova Fandina, Mikael Møller Høgsgaard, and Kasper Green Larsen. Barriers for Faster Dimensionality Reduction. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 31:1-31:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{novafandina_et_al:LIPIcs.STACS.2023.31, author = {Nova Fandina, Ora and M{\o}ller H{\o}gsgaard, Mikael and Green Larsen, Kasper}, title = {{Barriers for Faster Dimensionality Reduction}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {31:1--31:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.31}, URN = {urn:nbn:de:0030-drops-176838}, doi = {10.4230/LIPIcs.STACS.2023.31}, annote = {Keywords: Dimensional reduction, Lower bound, Linear Circuits} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Peyman Afshani, Rasmus Killmann, and Kasper Green Larsen. Hierarchical Categories in Colored Searching. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 25:1-25:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{afshani_et_al:LIPIcs.ISAAC.2022.25, author = {Afshani, Peyman and Killmann, Rasmus and Larsen, Kasper Green}, title = {{Hierarchical Categories in Colored Searching}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {25:1--25:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.25}, URN = {urn:nbn:de:0030-drops-173100}, doi = {10.4230/LIPIcs.ISAAC.2022.25}, annote = {Keywords: Categorical Data, Computational Geometry} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Yair Bartal, Ora Nova Fandina, and Kasper Green Larsen. Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 13:1-13:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bartal_et_al:LIPIcs.SoCG.2022.13, author = {Bartal, Yair and Fandina, Ora Nova and Larsen, Kasper Green}, title = {{Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {13:1--13:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.13}, URN = {urn:nbn:de:0030-drops-160219}, doi = {10.4230/LIPIcs.SoCG.2022.13}, annote = {Keywords: average distortion, practical dimensionality reduction, JL transform} }
Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
Ivan Bjerre Damgård, Kasper Green Larsen, and Sophia Yakoubov. Broadcast Secret-Sharing, Bounds and Applications. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 10:1-10:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{damgard_et_al:LIPIcs.ITC.2021.10, author = {Damg\r{a}rd, Ivan Bjerre and Larsen, Kasper Green and Yakoubov, Sophia}, title = {{Broadcast Secret-Sharing, Bounds and Applications}}, booktitle = {2nd Conference on Information-Theoretic Cryptography (ITC 2021)}, pages = {10:1--10:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-197-9}, ISSN = {1868-8969}, year = {2021}, volume = {199}, editor = {Tessaro, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.10}, URN = {urn:nbn:de:0030-drops-143299}, doi = {10.4230/LIPIcs.ITC.2021.10}, annote = {Keywords: Secret-Sharing, Ad-hoc Threshold Encryption} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, and Kasper Green Larsen. Lower Bounds for Multiplication via Network Coding. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 10:1-10:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{afshani_et_al:LIPIcs.ICALP.2019.10, author = {Afshani, Peyman and Freksen, Casper Benjamin and Kamma, Lior and Larsen, Kasper Green}, title = {{Lower Bounds for Multiplication via Network Coding}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {10:1--10:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.10}, URN = {urn:nbn:de:0030-drops-105861}, doi = {10.4230/LIPIcs.ICALP.2019.10}, annote = {Keywords: Circuit Complexity, Circuit Lower Bounds, Multiplication, Network Coding, Fine-Grained Complexity} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Kasper Green Larsen. Constructive Discrepancy Minimization with Hereditary L2 Guarantees. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 48:1-48:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{larsen:LIPIcs.STACS.2019.48, author = {Larsen, Kasper Green}, title = {{Constructive Discrepancy Minimization with Hereditary L2 Guarantees}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {48:1--48:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.48}, URN = {urn:nbn:de:0030-drops-102878}, doi = {10.4230/LIPIcs.STACS.2019.48}, annote = {Keywords: Discrepancy, Hereditary Discrepancy, Combinatorics, Computational Geometry} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Raphaël Clifford, Allan Grønlund, Kasper Green Larsen, and Tatiana Starikovskaya. Upper and Lower Bounds for Dynamic Data Structures on Strings. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 22:1-22:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{clifford_et_al:LIPIcs.STACS.2018.22, author = {Clifford, Rapha\"{e}l and Gr{\o}nlund, Allan and Larsen, Kasper Green and Starikovskaya, Tatiana}, title = {{Upper and Lower Bounds for Dynamic Data Structures on Strings}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {22:1--22:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.22}, URN = {urn:nbn:de:0030-drops-85088}, doi = {10.4230/LIPIcs.STACS.2018.22}, annote = {Keywords: exact pattern matching with wildcards, hamming distance, inner product, conditional lower bounds} }
Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Casper Benjamin Freksen and Kasper Green Larsen. On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 32:1-32:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{freksen_et_al:LIPIcs.ISAAC.2017.32, author = {Freksen, Casper Benjamin and Larsen, Kasper Green}, title = {{On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {32:1--32:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.32}, URN = {urn:nbn:de:0030-drops-82540}, doi = {10.4230/LIPIcs.ISAAC.2017.32}, annote = {Keywords: dimensionality reduction, Johnson-Lindenstrauss, Toeplitz matrices} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Kasper Green Larsen and Jelani Nelson. The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 82:1-82:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{larsen_et_al:LIPIcs.ICALP.2016.82, author = {Larsen, Kasper Green and Nelson, Jelani}, title = {{The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {82:1--82:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.82}, URN = {urn:nbn:de:0030-drops-62032}, doi = {10.4230/LIPIcs.ICALP.2016.82}, annote = {Keywords: dimensionality reduction, lower bounds, Johnson-Lindenstrauss} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Allan Grønlund and Kasper Green Larsen. Towards Tight Lower Bounds for Range Reporting on the RAM. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 92:1-92:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{gronlund_et_al:LIPIcs.ICALP.2016.92, author = {Gr{\o}nlund, Allan and Larsen, Kasper Green}, title = {{Towards Tight Lower Bounds for Range Reporting on the RAM}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {92:1--92:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.92}, URN = {urn:nbn:de:0030-drops-61936}, doi = {10.4230/LIPIcs.ICALP.2016.92}, annote = {Keywords: Data Structures, Lower Bounds, Cell Probe Model, Range Reporting} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, and Bryan T. Wilkinson. Linear-Space Data Structures for Range Mode Query in Arrays. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 290-301, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
@InProceedings{chan_et_al:LIPIcs.STACS.2012.290, author = {Chan, Timothy M. and Durocher, Stephane and Larsen, Kasper Green and Morrison, Jason and Wilkinson, Bryan T.}, title = {{Linear-Space Data Structures for Range Mode Query in Arrays}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {290--301}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.290}, URN = {urn:nbn:de:0030-drops-34254}, doi = {10.4230/LIPIcs.STACS.2012.290}, annote = {Keywords: mode, range query, data structure, linear space, array} }
Feedback for Dagstuhl Publishing