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)
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)
Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Barriers for Fast Matrix Multiplication from Irreversibility. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{christandl_et_al:LIPIcs.CCC.2019.26, author = {Christandl, Matthias and Vrana, P\'{e}ter and Zuiddam, Jeroen}, title = {{Barriers for Fast Matrix Multiplication from Irreversibility}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {26:1--26:17}, 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.26}, URN = {urn:nbn:de:0030-drops-108487}, doi = {10.4230/LIPIcs.CCC.2019.26}, annote = {Keywords: Matrix multiplication exponent, barriers, laser method} }
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, 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: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Karl Bringmann, Nick Fischer, and Marvin Künnemann. A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 31:1-31:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bringmann_et_al:LIPIcs.CCC.2019.31, author = {Bringmann, Karl and Fischer, Nick and K\"{u}nnemann, Marvin}, title = {{A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {31:1--31:27}, 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.31}, URN = {urn:nbn:de:0030-drops-108533}, doi = {10.4230/LIPIcs.CCC.2019.31}, annote = {Keywords: Fine-grained Complexity, Hardness in P, Hyperclique Conjecture, Constrained Triangle Detection} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan. Parity Helps to Compute Majority. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{oliveira_et_al:LIPIcs.CCC.2019.23, author = {Oliveira, Igor Carboni and Santhanam, Rahul and Srinivasan, Srikanth}, title = {{Parity Helps to Compute Majority}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {23:1--23:17}, 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.23}, URN = {urn:nbn:de:0030-drops-108453}, doi = {10.4230/LIPIcs.CCC.2019.23}, annote = {Keywords: Computational Complexity, Boolean Circuits, Lower Bounds, Parity, Majority} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
William M. Hoza. Typically-Correct Derandomization for Small Time and Space. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 9:1-9:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hoza:LIPIcs.CCC.2019.9, author = {Hoza, William M.}, title = {{Typically-Correct Derandomization for Small Time and Space}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {9:1--9:39}, 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.9}, URN = {urn:nbn:de:0030-drops-108317}, doi = {10.4230/LIPIcs.CCC.2019.9}, annote = {Keywords: Derandomization, pseudorandomness, space complexity} }
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: 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} }
Feedback for Dagstuhl Publishing