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)
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 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 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} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Josh Alman. Limits on the Universal Method for Matrix Multiplication. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 12:1-12:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{alman:LIPIcs.CCC.2019.12, author = {Alman, Josh}, title = {{Limits on the Universal Method for Matrix Multiplication}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {12:1--12:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.12}, URN = {urn:nbn:de:0030-drops-108347}, doi = {10.4230/LIPIcs.CCC.2019.12}, annote = {Keywords: Matrix Multiplication, Laser Method, Slice Rank} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Zeev Dvir and Allen Liu. Fourier and Circulant Matrices Are Not Rigid. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dvir_et_al:LIPIcs.CCC.2019.17, author = {Dvir, Zeev and Liu, Allen}, title = {{Fourier and Circulant Matrices Are Not Rigid}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {17:1--17:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.17}, URN = {urn:nbn:de:0030-drops-108390}, doi = {10.4230/LIPIcs.CCC.2019.17}, annote = {Keywords: Rigidity, Fourier matrix, Circulant matrix} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Lijie Chen and R. Ryan Williams. Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 19:1-19:43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.CCC.2019.19, author = {Chen, Lijie and Williams, R. Ryan}, title = {{Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {19:1--19:43}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.19}, URN = {urn:nbn:de:0030-drops-108419}, doi = {10.4230/LIPIcs.CCC.2019.19}, annote = {Keywords: PCP of Proximity, Circuit Lower Bounds, Derandomization, Threshold Circuits, ReLU} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.CCC.2019.30, author = {Chen, Lijie and McKay, Dylan M. and Murray, Cody D. and Williams, R. Ryan}, title = {{Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {30:1--30:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.30}, URN = {urn:nbn:de:0030-drops-108525}, doi = {10.4230/LIPIcs.CCC.2019.30}, annote = {Keywords: Karp-Lipton Theorems, Circuit Lower Bounds, Derandomization, Hardness Magnification} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Josh Alman. An Illuminating Algorithm for the Light Bulb Problem. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 2:1-2:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{alman:OASIcs.SOSA.2019.2, author = {Alman, Josh}, title = {{An Illuminating Algorithm for the Light Bulb Problem}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {2:1--2:11}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.2}, URN = {urn:nbn:de:0030-drops-100289}, doi = {10.4230/OASIcs.SOSA.2019.2}, annote = {Keywords: Light Bulb Problem, Polynomial Method, Finding Correlations} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Josh Alman and Virginia Vassilevska Williams. Further Limitations of the Known Approaches for Matrix Multiplication. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{alman_et_al:LIPIcs.ITCS.2018.25, author = {Alman, Josh and Vassilevska Williams, Virginia}, title = {{Further Limitations of the Known Approaches for Matrix Multiplication}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {25:1--25:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.25}, URN = {urn:nbn:de:0030-drops-83609}, doi = {10.4230/LIPIcs.ITCS.2018.25}, annote = {Keywords: matrix multiplication, lower bound, monomial degeneration, structural tensor of addition mod p} }