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 264, 38th Computational Complexity Conference (CCC 2023)
Prahladh Harsha, Tulasimohan Molli, and Ashutosh Shankar. Criticality of AC⁰-Formulae. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{harsha_et_al:LIPIcs.CCC.2023.19, author = {Harsha, Prahladh and Molli, Tulasimohan and Shankar, Ashutosh}, title = {{Criticality of AC⁰-Formulae}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {19:1--19:24}, 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.19}, URN = {urn:nbn:de:0030-drops-182898}, doi = {10.4230/LIPIcs.CCC.2023.19}, annote = {Keywords: AC⁰ circuits, AC⁰ formulae, criticality, switching lemma, correlation bounds} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, and Srikanth Srinivasan. Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bhandari_et_al:LIPIcs.CCC.2022.31, author = {Bhandari, Siddharth and Harsha, Prahladh and Saptharishi, Ramprasad and Srinivasan, Srikanth}, title = {{Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {31:1--31:14}, 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.31}, URN = {urn:nbn:de:0030-drops-165934}, doi = {10.4230/LIPIcs.CCC.2022.31}, annote = {Keywords: Reed-Muller codes, polynomials, weight-distribution, vanishing ideals, erasures, capacity} }
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.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 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
C. Ramya and Anamay Tengse. On Finer Separations Between Subclasses of Read-Once Oblivious ABPs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 53:1-53:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ramya_et_al:LIPIcs.STACS.2022.53, author = {Ramya, C. and Tengse, Anamay}, title = {{On Finer Separations Between Subclasses of Read-Once Oblivious ABPs}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {53:1--53:23}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.53}, URN = {urn:nbn:de:0030-drops-158636}, doi = {10.4230/LIPIcs.STACS.2022.53}, annote = {Keywords: Algebraic Complexity Theory, Algebraic Branching Programs, Commutative Matrices} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, and Swagato Sanyal. Tight Chang’s-Lemma-Type Bounds for Boolean Functions. 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. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2021.10, author = {Chakraborty, Sourav and Mande, Nikhil S. and Mittal, Rajat and Molli, Tulasimohan and Paraashar, Manaswi and Sanyal, Swagato}, title = {{Tight Chang’s-Lemma-Type Bounds for Boolean Functions}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {10:1--10:22}, 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.10}, URN = {urn:nbn:de:0030-drops-155215}, doi = {10.4230/LIPIcs.FSTTCS.2021.10}, annote = {Keywords: Analysis of Boolean functions, Chang’s lemma, Parity decision trees, Fourier dimension} }
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)
Mrinal Kumar and Ben Lee Volk. A Lower Bound on Determinantal Complexity. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kumar_et_al:LIPIcs.CCC.2021.4, author = {Kumar, Mrinal and Volk, Ben Lee}, title = {{A Lower Bound on Determinantal Complexity}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {4:1--4:12}, 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.4}, URN = {urn:nbn:de:0030-drops-142781}, doi = {10.4230/LIPIcs.CCC.2021.4}, annote = {Keywords: Determinantal Complexity, Algebraic Circuits, Lower Bounds, Singular Variety} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Prerona Chatterjee. Separating ABPs and Some Structured Formulas in the Non-Commutative Setting. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chatterjee:LIPIcs.CCC.2021.7, author = {Chatterjee, Prerona}, title = {{Separating ABPs and Some Structured Formulas in the Non-Commutative Setting}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {7:1--7:24}, 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.7}, URN = {urn:nbn:de:0030-drops-142812}, doi = {10.4230/LIPIcs.CCC.2021.7}, annote = {Keywords: Non-Commutative Formulas, Lower Bound, Separating ABPs and Formulas} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk. A Quadratic Lower Bound for Algebraic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chatterjee_et_al:LIPIcs.CCC.2020.2, author = {Chatterjee, Prerona and Kumar, Mrinal and She, Adrian and Volk, Ben Lee}, title = {{A Quadratic Lower Bound for Algebraic Branching Programs}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {2:1--2:21}, 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.2}, URN = {urn:nbn:de:0030-drops-125546}, doi = {10.4230/LIPIcs.CCC.2020.2}, annote = {Keywords: Algebraic Branching Programs, Lower Bound} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan. Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 14:1-14:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chaugule_et_al:LIPIcs.CCC.2020.14, author = {Chaugule, Prasad and Kumar, Mrinal and Limaye, Nutan and Mohapatra, Chandra Kanta and She, Adrian and Srinivasan, Srikanth}, title = {{Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {14:1--14:27}, 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.14}, URN = {urn:nbn:de:0030-drops-125660}, doi = {10.4230/LIPIcs.CCC.2020.14}, annote = {Keywords: Schur polynomial, Jacobian, Algebraic independence, Generalized Vandermonde determinant, Taylor expansion, Formula complexity, Lower bound} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Prerona Chatterjee and Ramprasad Saptharishi. Constructing Faithful Homomorphisms over Fields of Finite Characteristic. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chatterjee_et_al:LIPIcs.FSTTCS.2019.11, author = {Chatterjee, Prerona and Saptharishi, Ramprasad}, title = {{Constructing Faithful Homomorphisms over Fields of Finite Characteristic}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {11:1--11:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.11}, URN = {urn:nbn:de:0030-drops-115733}, doi = {10.4230/LIPIcs.FSTTCS.2019.11}, annote = {Keywords: Faithful Homomorphisms, Identity Testing, Algebraic Independence, Finite characteristic fields} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi. Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 78:1-78:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kumar_et_al:LIPIcs.ICALP.2019.78, author = {Kumar, Mrinal and Oliveira, Rafael and Saptharishi, Ramprasad}, title = {{Towards Optimal Depth Reductions for Syntactically Multilinear Circuits}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {78:1--78: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.78}, URN = {urn:nbn:de:0030-drops-106548}, doi = {10.4230/LIPIcs.ICALP.2019.78}, annote = {Keywords: arithmetic circuits, multilinear circuits, depth reduction, lower bounds} }