Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, and Chuanqi Zhang. On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 31:1-31:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ITCS.2024.31, author = {Chen, Zhili and Grochow, Joshua A. and Qiao, Youming and Tang, Gang and Zhang, Chuanqi}, title = {{On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {31:1--31: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.31}, URN = {urn:nbn:de:0030-drops-195595}, doi = {10.4230/LIPIcs.ITCS.2024.31}, annote = {Keywords: complexity class, tensor isomorphism, polynomial isomorphism, group isomorphism, local operations and classical communication} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, and Adrian She. On the Algebraic Proof Complexity of Tensor Isomorphism. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 4:1-4:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{galesi_et_al:LIPIcs.CCC.2023.4, author = {Galesi, Nicola and Grochow, Joshua A. and Pitassi, Toniann and She, Adrian}, title = {{On the Algebraic Proof Complexity of Tensor Isomorphism}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {4:1--4:40}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.4}, URN = {urn:nbn:de:0030-drops-182748}, doi = {10.4230/LIPIcs.CCC.2023.4}, annote = {Keywords: Algebraic proof complexity, Tensor Isomorphism, Graph Isomorphism, Polynomial Calculus, Sum-of-Squares, reductions, lower bounds, proof complexity of linear algebra} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, and Chris Umans. Matrix Multiplication via Matrix Groups. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{blasiak_et_al:LIPIcs.ITCS.2023.19, author = {Blasiak, Jonah and Cohn, Henry and Grochow, Joshua A. and Pratt, Kevin and Umans, Chris}, title = {{Matrix Multiplication via Matrix Groups}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {19:1--19:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.19}, URN = {urn:nbn:de:0030-drops-175226}, doi = {10.4230/LIPIcs.ITCS.2023.19}, annote = {Keywords: Fast matrix multiplication, representation theory, matrix groups} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Adrian She and Henry Yuen. Unitary Property Testing Lower Bounds by Polynomials. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 96:1-96:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{she_et_al:LIPIcs.ITCS.2023.96, author = {She, Adrian and Yuen, Henry}, title = {{Unitary Property Testing Lower Bounds by Polynomials}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {96:1--96:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.96}, URN = {urn:nbn:de:0030-drops-175995}, doi = {10.4230/LIPIcs.ITCS.2023.96}, annote = {Keywords: Quantum query complexity, polynomial method, unitary property testing, quantum proofs, invariant theory, quantum recurrence time, entanglement entropy, BQP, QMA, QMA(2)} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse. If VNP Is Hard, Then so Are Equations for It. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kumar_et_al:LIPIcs.STACS.2022.44, author = {Kumar, Mrinal and Ramya, C. and Saptharishi, Ramprasad and Tengse, Anamay}, title = {{If VNP Is Hard, Then so Are Equations for It}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {44:1--44:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.44}, URN = {urn:nbn:de:0030-drops-158547}, doi = {10.4230/LIPIcs.STACS.2022.44}, annote = {Keywords: Computational Complexity, Algebraic Circuits, Algebraic Natural Proofs} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Joshua A. Grochow and Youming Qiao. On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 16:1-16:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{grochow_et_al:LIPIcs.CCC.2021.16, author = {Grochow, Joshua A. and Qiao, Youming}, title = {{On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {16:1--16:38}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.16}, URN = {urn:nbn:de:0030-drops-142905}, doi = {10.4230/LIPIcs.CCC.2021.16}, annote = {Keywords: group isomorphism, search-to-decision reduction, counting-to-decision reduction, nilpotent group isomorphism, p-group isomorphism, tensor isomorphism} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Toniann Pitassi. Algebraic Proof Systems (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{pitassi:LIPIcs.ICALP.2021.5, author = {Pitassi, Toniann}, title = {{Algebraic Proof Systems}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {5:1--5:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.5}, URN = {urn:nbn:de:0030-drops-140747}, doi = {10.4230/LIPIcs.ICALP.2021.5}, annote = {Keywords: complexity theory, proof complexity, algebraic circuits} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Joshua A. Grochow, Youming Qiao, and Gang Tang. Average-Case Algorithms for Testing Isomorphism of Polynomials, Algebras, and Multilinear Forms. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{grochow_et_al:LIPIcs.STACS.2021.38, author = {Grochow, Joshua A. and Qiao, Youming and Tang, Gang}, title = {{Average-Case Algorithms for Testing Isomorphism of Polynomials, Algebras, and Multilinear Forms}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {38:1--38:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.38}, URN = {urn:nbn:de:0030-drops-136836}, doi = {10.4230/LIPIcs.STACS.2021.38}, annote = {Keywords: polynomial isomorphism, trilinear form equivalence, algebra isomorphism, average-case algorithms, tensor isomorphism complete, symmetric and alternating bilinear maps} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Joshua A. Grochow and Youming Qiao. On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{grochow_et_al:LIPIcs.ITCS.2021.31, author = {Grochow, Joshua A. and Qiao, Youming}, title = {{On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {31:1--31:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.31}, URN = {urn:nbn:de:0030-drops-135702}, doi = {10.4230/LIPIcs.ITCS.2021.31}, annote = {Keywords: complexity class, tensor isomorphism, polynomial isomorphism, group isomorphism, stochastic local operations and classical communication} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Peter A. Brooksbank, Yinan Li, Youming Qiao, and James B. Wilson. Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{brooksbank_et_al:LIPIcs.ESA.2020.26, author = {Brooksbank, Peter A. and Li, Yinan and Qiao, Youming and Wilson, James B.}, title = {{Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {26:1--26:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.26}, URN = {urn:nbn:de:0030-drops-128920}, doi = {10.4230/LIPIcs.ESA.2020.26}, annote = {Keywords: Alternating Matrix Spaces, Average-case Algorithm, p-groups of Class 2nd Exponent p, Magma} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Janaky Murthy, Vineet Nair, and Chandan Saha. Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 72:1-72:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{murthy_et_al:LIPIcs.MFCS.2020.72, author = {Murthy, Janaky and Nair, Vineet and Saha, Chandan}, title = {{Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {72:1--72:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.72}, URN = {urn:nbn:de:0030-drops-127419}, doi = {10.4230/LIPIcs.MFCS.2020.72}, annote = {Keywords: equivalence testing, determinant, trace of the matrix product, full-matrix algebra isomorphism} }
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-dev.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 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Joshua A. Grochow and Jamie Tucker-Foltz. Computational Topology and the Unique Games Conjecture. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{grochow_et_al:LIPIcs.SoCG.2018.43, author = {Grochow, Joshua A. and Tucker-Foltz, Jamie}, title = {{Computational Topology and the Unique Games Conjecture}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {43:1--43:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.43}, URN = {urn:nbn:de:0030-drops-87566}, doi = {10.4230/LIPIcs.SoCG.2018.43}, annote = {Keywords: Unique Games Conjecture, homology localization, inapproximability, computational topology, graph lift, covering graph, permutation voltage graph, cell} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan. Minimum Circuit Size, Graph Isomorphism, and Related Problems. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{allender_et_al:LIPIcs.ITCS.2018.20, author = {Allender, Eric and Grochow, Joshua A. and van Melkebeek, Dieter and Moore, Cristopher and Morgan, Andrew}, title = {{Minimum Circuit Size, Graph Isomorphism, and Related Problems}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {20:1--20:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.20}, URN = {urn:nbn:de:0030-drops-83455}, doi = {10.4230/LIPIcs.ITCS.2018.20}, annote = {Keywords: Reductions between NP-intermediate problems, Graph Isomorphism, Minimum Circuit Size Problem, time-bounded Kolmogorov complexity} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. Boundaries of VP and VNP. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{grochow_et_al:LIPIcs.ICALP.2016.34, author = {Grochow, Joshua A. and Mulmuley, Ketan D. and Qiao, Youming}, title = {{Boundaries of VP and VNP}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {34:1--34:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.34}, URN = {urn:nbn:de:0030-drops-63147}, doi = {10.4230/LIPIcs.ICALP.2016.34}, annote = {Keywords: geometric complexity theory, arithmetic circuit, border complexity} }
Feedback for Dagstuhl Publishing