Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Suryajith Chillara, Coral Grichener, and Amir Shpilka. On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 22:1-22:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chillara_et_al:LIPIcs.STACS.2023.22, author = {Chillara, Suryajith and Grichener, Coral and Shpilka, Amir}, title = {{On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {22:1--22:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.22}, URN = {urn:nbn:de:0030-drops-176744}, doi = {10.4230/LIPIcs.STACS.2023.22}, annote = {Keywords: algebraic complexity, shift equivalence, polynomial equivalence, Hilbert’s Nullstellensatz, hardness of approximation} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Suryajith Chillara. Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 14:1-14:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chillara:LIPIcs.FSTTCS.2021.14, author = {Chillara, Suryajith}, title = {{Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {14:1--14:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.14}, URN = {urn:nbn:de:0030-drops-155251}, doi = {10.4230/LIPIcs.FSTTCS.2021.14}, annote = {Keywords: Functional Lower Bounds, Boolean Circuit Lower Bounds, Depth Four, Connections to Boolean Complexity, Iterated Matrix Multiplication} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Zeyu Guo. Variety Evasive Subspace Families. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 20:1-20:33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{guo:LIPIcs.CCC.2021.20, author = {Guo, Zeyu}, title = {{Variety Evasive Subspace Families}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {20:1--20:33}, 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.20}, URN = {urn:nbn:de:0030-drops-142949}, doi = {10.4230/LIPIcs.CCC.2021.20}, annote = {Keywords: algebraic complexity, dimension reduction, Noether normalization, polynomial identity testing, pseudorandomness, varieties} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Suryajith Chillara. On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 47:1-47:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chillara:LIPIcs.STACS.2020.47, author = {Chillara, Suryajith}, title = {{On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {47:1--47:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.47}, URN = {urn:nbn:de:0030-drops-119084}, doi = {10.4230/LIPIcs.STACS.2020.47}, annote = {Keywords: Lower Bounds, Multilinear, Multi-r-ic} }
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 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
C. Ramya and B. V. Raghavendra Rao. Lower Bounds for Multilinear Order-Restricted ABPs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ramya_et_al:LIPIcs.MFCS.2019.52, author = {Ramya, C. and Rao, B. V. Raghavendra}, title = {{Lower Bounds for Multilinear Order-Restricted ABPs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {52:1--52:14}, 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.52}, URN = {urn:nbn:de:0030-drops-109963}, doi = {10.4230/LIPIcs.MFCS.2019.52}, annote = {Keywords: Computational complexity, Algebraic complexity theory, Polynomials} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 36:1-36:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{chillara_et_al:LIPIcs.ICALP.2018.36, author = {Chillara, Suryajith and Limaye, Nutan and Srinivasan, Srikanth}, title = {{A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {36:1--36:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.36}, URN = {urn:nbn:de:0030-drops-90401}, doi = {10.4230/LIPIcs.ICALP.2018.36}, annote = {Keywords: Algebraic circuit complexity, Multilinear formulas, Lower Bounds} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 21:1-21:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{chillara_et_al:LIPIcs.STACS.2018.21, author = {Chillara, Suryajith and Limaye, Nutan and Srinivasan, Srikanth}, title = {{Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {21:1--21:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.21}, URN = {urn:nbn:de:0030-drops-85235}, doi = {10.4230/LIPIcs.STACS.2018.21}, annote = {Keywords: Algebraic circuit complexity, Multilinear formulas, Lower Bounds} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Suryajith Chillara and Partha Mukhopadhyay. Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 239-250, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{chillara_et_al:LIPIcs.STACS.2014.239, author = {Chillara, Suryajith and Mukhopadhyay, Partha}, title = {{Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {239--250}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.239}, URN = {urn:nbn:de:0030-drops-44610}, doi = {10.4230/LIPIcs.STACS.2014.239}, annote = {Keywords: Arithmetic Circuits, Determinantal Complexity, Depth-4 Lower Bounds} }
Feedback for Dagstuhl Publishing