Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Peter Bürgisser, Mahmut Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson. Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 14:1-14:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{burgisser_et_al:LIPIcs.CCC.2024.14, author = {B\"{u}rgisser, Peter and Do\u{g}an, Mahmut Levent and Makam, Visu and Walter, Michael and Wigderson, Avi}, title = {{Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {14:1--14:48}, 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.14}, URN = {urn:nbn:de:0030-drops-204100}, doi = {10.4230/LIPIcs.CCC.2024.14}, annote = {Keywords: computational invariant theory, geometric complexity theory, orbit problems, abc-conjecture, closest vector problem} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, and Amir Shpilka. Lower Bounds for Set-Multilinear Branching Programs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chatterjee_et_al:LIPIcs.CCC.2024.20, author = {Chatterjee, Prerona and Kush, Deepanshu and Saraf, Shubhangi and Shpilka, Amir}, title = {{Lower Bounds for Set-Multilinear Branching Programs}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {20:1--20:20}, 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.20}, URN = {urn:nbn:de:0030-drops-204167}, doi = {10.4230/LIPIcs.CCC.2024.20}, annote = {Keywords: Lower Bounds, Algebraic Branching Programs, Set-multilinear polynomials} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Michael A. Forbes. Low-Depth Algebraic Circuit Lower Bounds over Any Field. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{forbes:LIPIcs.CCC.2024.31, author = {Forbes, Michael A.}, title = {{Low-Depth Algebraic Circuit Lower Bounds over Any Field}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {31:1--31:16}, 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.31}, URN = {urn:nbn:de:0030-drops-204271}, doi = {10.4230/LIPIcs.CCC.2024.31}, annote = {Keywords: algebraic circuits, lower bounds, low-depth circuits, positive characteristic} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{baraskar_et_al:LIPIcs.ICALP.2024.16, author = {Baraskar, Omkar and Dewan, Agrim and Saha, Chandan and Sinha, Pulkit}, title = {{NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {16:1--16:21}, 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.16}, URN = {urn:nbn:de:0030-drops-201598}, doi = {10.4230/LIPIcs.ICALP.2024.16}, annote = {Keywords: Equivalence testing, MCSP, sparse polynomials, 3SAT} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, and Tanmay Sinha. Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chandra_et_al:LIPIcs.ITCS.2024.25, author = {Chandra, Pritam and Garg, Ankit and Kayal, Neeraj and Mittal, Kunal and Sinha, Tanmay}, title = {{Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {25:1--25:19}, 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.25}, URN = {urn:nbn:de:0030-drops-195537}, doi = {10.4230/LIPIcs.ITCS.2024.25}, annote = {Keywords: Arithmetic Circuits, Robust Vector Space Decomposition, Subspace Clustering, Mixtures of Gaussians} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, and Bhargav Thankey. Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{amireddy_et_al:LIPIcs.ICALP.2023.12, author = {Amireddy, Prashanth and Garg, Ankit and Kayal, Neeraj and Saha, Chandan and Thankey, Bhargav}, title = {{Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {12:1--12:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.12}, URN = {urn:nbn:de:0030-drops-180642}, doi = {10.4230/LIPIcs.ICALP.2023.12}, annote = {Keywords: arithmetic circuits, low-depth circuits, lower bounds, shifted partials} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Vishwas Bhargava, Ankit Garg, Neeraj Kayal, and Chandan Saha. Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bhargava_et_al:LIPIcs.APPROX/RANDOM.2022.21, author = {Bhargava, Vishwas and Garg, Ankit and Kayal, Neeraj and Saha, Chandan}, title = {{Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {21:1--21:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.21}, URN = {urn:nbn:de:0030-drops-171430}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.21}, annote = {Keywords: Arithemtic Circuits, Average-case Learning, Depth 3 Arithmetic Circuits, Learning Algorithms, Learning Circuits, Circuit Reconstruction} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Gaurav Sinha. Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 118:1-118:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{sinha:LIPIcs.ITCS.2022.118, author = {Sinha, Gaurav}, title = {{Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {118:1--118:33}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.118}, URN = {urn:nbn:de:0030-drops-157143}, doi = {10.4230/LIPIcs.ITCS.2022.118}, annote = {Keywords: Arithmetic Circuits, Circuit Reconstruction} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Chandan Saha and Bhargav Thankey. Hitting Sets for Orbits of Circuit Classes and Polynomial Families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 50:1-50:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{saha_et_al:LIPIcs.APPROX/RANDOM.2021.50, author = {Saha, Chandan and Thankey, Bhargav}, title = {{Hitting Sets for Orbits of Circuit Classes and Polynomial Families}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {50:1--50:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.50}, URN = {urn:nbn:de:0030-drops-147433}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.50}, annote = {Keywords: Hitting Sets, Orbits, ROABPs, Rank Concentration} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Dori Medini and Amir Shpilka. Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 19:1-19:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{medini_et_al:LIPIcs.CCC.2021.19, author = {Medini, Dori and Shpilka, Amir}, title = {{Hitting Sets and Reconstruction for Dense Orbits in VP\underline\{e\} and \Sigma\Pi\Sigma Circuits}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {19:1--19:27}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.19}, URN = {urn:nbn:de:0030-drops-142930}, doi = {10.4230/LIPIcs.CCC.2021.19}, annote = {Keywords: Algebraic complexity, VP, VNP, algebraic circuits, algebraic formula} }
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.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 169, 35th Computational Complexity Conference (CCC 2020)
Nikhil Gupta, Chandan Saha, and Bhargav Thankey. A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 23:1-23:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gupta_et_al:LIPIcs.CCC.2020.23, author = {Gupta, Nikhil and Saha, Chandan and Thankey, Bhargav}, title = {{A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {23:1--23:31}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.23}, URN = {urn:nbn:de:0030-drops-125757}, doi = {10.4230/LIPIcs.CCC.2020.23}, annote = {Keywords: depth four arithmetic circuits, Projected Shifted Partials, super-quadratic lower bound} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Nikhil Gupta and Chandan Saha. On the Symmetries of and Equivalence Test for Design Polynomials. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gupta_et_al:LIPIcs.MFCS.2019.53, author = {Gupta, Nikhil and Saha, Chandan}, title = {{On the Symmetries of and Equivalence Test for Design Polynomials}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {53:1--53:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.53}, URN = {urn:nbn:de:0030-drops-109979}, doi = {10.4230/LIPIcs.MFCS.2019.53}, annote = {Keywords: Nisan-Wigderson design polynomial, characterization by symmetries, Lie algebra, group of symmetries, circuit testability, flip theorem, equivalence test} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha. Determinant Equivalence Test over Finite Fields and over Q. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{garg_et_al:LIPIcs.ICALP.2019.62, author = {Garg, Ankit and Gupta, Nikhil and Kayal, Neeraj and Saha, Chandan}, title = {{Determinant Equivalence Test over Finite Fields and over Q}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {62:1--62:15}, 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.62}, URN = {urn:nbn:de:0030-drops-106382}, doi = {10.4230/LIPIcs.ICALP.2019.62}, annote = {Keywords: Determinant equivalence test, full matrix algebra isomorphism, Lie algebra} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of Full Rank Algebraic Branching Programs. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 21:1-21:61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{kayal_et_al:LIPIcs.CCC.2017.21, author = {Kayal, Neeraj and Nair, Vineet and Saha, Chandan and Tavenas, S\'{e}bastien}, title = {{Reconstruction of Full Rank Algebraic Branching Programs}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {21:1--21:61}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.21}, URN = {urn:nbn:de:0030-drops-75318}, doi = {10.4230/LIPIcs.CCC.2017.21}, annote = {Keywords: Circuit reconstruction, algebraic branching programs, equivalence test, iterated matrix multiplication, Lie algebra} }