Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)
Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. Faster Cycle Detection in the Congested Clique. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{censorhillel_et_al:LIPIcs.DISC.2024.12, author = {Censor-Hillel, Keren and Even, Tomer and Vassilevska Williams, Virginia}, title = {{Faster Cycle Detection in the Congested Clique}}, booktitle = {38th International Symposium on Distributed Computing (DISC 2024)}, pages = {12:1--12:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-352-2}, ISSN = {1868-8969}, year = {2024}, volume = {319}, editor = {Alistarh, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.12}, URN = {urn:nbn:de:0030-drops-212382}, doi = {10.4230/LIPIcs.DISC.2024.12}, annote = {Keywords: triangle detection, cycle detection, distributed computing, Congested Clique, quantum computing, Fast matrix multiplication, Fast rectangular matrix multiplication} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Dipan Dey and Manoj Gupta. Near Optimal Dual Fault Tolerant Distance Oracle. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 45:1-45:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dey_et_al:LIPIcs.ESA.2024.45, author = {Dey, Dipan and Gupta, Manoj}, title = {{Near Optimal Dual Fault Tolerant Distance Oracle}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {45:1--45:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.45}, URN = {urn:nbn:de:0030-drops-211164}, doi = {10.4230/LIPIcs.ESA.2024.45}, annote = {Keywords: Distance Sensitive Oracle, Dual Fault Distance Oracle} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Dvir Fried, Tsvi Kopelowitz, and Ely Porat. Removing the log Factor from (min,+)-Products on Bounded Range Integer Matrices. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 57:1-57:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fried_et_al:LIPIcs.ESA.2024.57, author = {Fried, Dvir and Kopelowitz, Tsvi and Porat, Ely}, title = {{Removing the log Factor from (min,+)-Products on Bounded Range Integer Matrices}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {57:1--57:6}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.57}, URN = {urn:nbn:de:0030-drops-211283}, doi = {10.4230/LIPIcs.ESA.2024.57}, annote = {Keywords: FMM, (min , +)-product, FFT} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Konrad Majewski, Michał Pilipczuk, and Anna Zych-Pawlewicz. Parameterized Dynamic Data Structure for Split Completion. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 87:1-87:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{majewski_et_al:LIPIcs.ESA.2024.87, author = {Majewski, Konrad and Pilipczuk, Micha{\l} and Zych-Pawlewicz, Anna}, title = {{Parameterized Dynamic Data Structure for Split Completion}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {87:1--87:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.87}, URN = {urn:nbn:de:0030-drops-211587}, doi = {10.4230/LIPIcs.ESA.2024.87}, annote = {Keywords: parameterized complexity, dynamic data structures, split graphs} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Samuel McCauley. Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 88:1-88:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mccauley:LIPIcs.ESA.2024.88, author = {McCauley, Samuel}, title = {{Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {88:1--88:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.88}, URN = {urn:nbn:de:0030-drops-211590}, doi = {10.4230/LIPIcs.ESA.2024.88}, annote = {Keywords: similarity search, locality-sensitive hashing, randomized algorithms, data structures, space efficiency, function inversion} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Ashish Gola, Igor Shinkar, and Harsimran Singh. Matrix Multiplication Reductions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gola_et_al:LIPIcs.APPROX/RANDOM.2024.34, author = {Gola, Ashish and Shinkar, Igor and Singh, Harsimran}, title = {{Matrix Multiplication Reductions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {34:1--34:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.34}, URN = {urn:nbn:de:0030-drops-210274}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.34}, annote = {Keywords: Matrix Multiplication, Reductions, Worst case to average case reductions} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Josh Alman and Yunfeng Guan. Finer-Grained Hardness of Kernel Density Estimation. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 35:1-35:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alman_et_al:LIPIcs.CCC.2024.35, author = {Alman, Josh and Guan, Yunfeng}, title = {{Finer-Grained Hardness of Kernel Density Estimation}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {35:1--35:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.35}, URN = {urn:nbn:de:0030-drops-204311}, doi = {10.4230/LIPIcs.CCC.2024.35}, annote = {Keywords: Kernel Density Estimation, Fine-Grained Complexity, Schur Polynomials} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shiri Chechik and Tianyi Zhang. Faster Algorithms for Dual-Failure Replacement Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chechik_et_al:LIPIcs.ICALP.2024.41, author = {Chechik, Shiri and Zhang, Tianyi}, title = {{Faster Algorithms for Dual-Failure Replacement Paths}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {41:1--41:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.41}, URN = {urn:nbn:de:0030-drops-201849}, doi = {10.4230/LIPIcs.ICALP.2024.41}, annote = {Keywords: graph algorithms, shortest paths, replacement paths} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
MohammadHossein Bateni, Laxman Dhulipala, Kishen N. Gowda, D. Ellis Hershkowitz, Rajesh Jayaram, and Jakub Łącki. It’s Hard to HAC Average Linkage!. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bateni_et_al:LIPIcs.ICALP.2024.18, author = {Bateni, MohammadHossein and Dhulipala, Laxman and Gowda, Kishen N. and Hershkowitz, D. Ellis and Jayaram, Rajesh and {\L}\k{a}cki, Jakub}, title = {{It’s Hard to HAC Average Linkage!}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {18:1--18:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.18}, URN = {urn:nbn:de:0030-drops-201613}, doi = {10.4230/LIPIcs.ICALP.2024.18}, annote = {Keywords: Clustering, Hierarchical Graph Clustering, HAC, Fine-Grained Complexity, Parallel Algorithms, CC} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Elie Abboud and Noga Ron-Zewi. Finer-Grained Reductions in Fine-Grained Hardness of Approximation. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abboud_et_al:LIPIcs.ICALP.2024.7, author = {Abboud, Elie and Ron-Zewi, Noga}, title = {{Finer-Grained Reductions in Fine-Grained Hardness of Approximation}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.7}, URN = {urn:nbn:de:0030-drops-201507}, doi = {10.4230/LIPIcs.ICALP.2024.7}, annote = {Keywords: Fine-grained complexity, conditional lower bound, fine-grained reduction, Approximation algorithms, Analysis of algorithms, Computational geometry, Computational and structural complexity theory} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Josh Alman, Ethan Turok, Hantao Yu, and Hengzhi Zhang. Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alman_et_al:LIPIcs.ITCS.2024.4, author = {Alman, Josh and Turok, Ethan and Yu, Hantao and Zhang, Hengzhi}, title = {{Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {4:1--4:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.4}, URN = {urn:nbn:de:0030-drops-195324}, doi = {10.4230/LIPIcs.ITCS.2024.4}, annote = {Keywords: Fine-grained complexity, Dynamic programming, Least-weight subsequence} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Josh Alman and Jarosław Błasiok. Matrix Multiplication and Number on the Forehead Communication. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{alman_et_al:LIPIcs.CCC.2023.16, author = {Alman, Josh and B{\l}asiok, Jaros{\l}aw}, title = {{Matrix Multiplication and Number on the Forehead Communication}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {16:1--16:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.16}, URN = {urn:nbn:de:0030-drops-182861}, doi = {10.4230/LIPIcs.CCC.2023.16}, annote = {Keywords: Number on the forehead, communication complexity, matrix multiplication} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Amol Aggarwal and Josh Alman. Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{aggarwal_et_al:LIPIcs.CCC.2022.22, author = {Aggarwal, Amol and Alman, Josh}, title = {{Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {22:1--22:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.22}, URN = {urn:nbn:de:0030-drops-165846}, doi = {10.4230/LIPIcs.CCC.2022.22}, annote = {Keywords: polynomial approximation, kernel density estimation, Chebyshev polynomials} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Josh Alman and Dean Hirsch. Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{alman_et_al:LIPIcs.ICALP.2022.9, author = {Alman, Josh and Hirsch, Dean}, title = {{Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {9:1--9:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.9}, URN = {urn:nbn:de:0030-drops-163504}, doi = {10.4230/LIPIcs.ICALP.2022.9}, annote = {Keywords: sensitivity oracles, k-path, dynamic algorithms, parameterized algorithms, set packing, partial cover, exterior algebra, extensor, algebraic algorithms} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Josh Alman and Virginia Vassilevska Williams. OV Graphs Are (Probably) Hard Instances. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 83:1-83:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{alman_et_al:LIPIcs.ITCS.2020.83, author = {Alman, Josh and Vassilevska Williams, Virginia}, title = {{OV Graphs Are (Probably) Hard Instances}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {83:1--83:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.83}, URN = {urn:nbn:de:0030-drops-117686}, doi = {10.4230/LIPIcs.ITCS.2020.83}, annote = {Keywords: Orthogonal Vectors, Fine-Grained Reductions, Cycle Finding} }
Feedback for Dagstuhl Publishing