Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Fixed-Parameter Debordering of Waring Rank. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dutta_et_al:LIPIcs.STACS.2024.30, author = {Dutta, Pranjal and Gesmundo, Fulvio and Ikenmeyer, Christian and Jindal, Gorav and Lysikov, Vladimir}, title = {{Fixed-Parameter Debordering of Waring Rank}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {30:1--30:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.30}, URN = {urn:nbn:de:0030-drops-197403}, doi = {10.4230/LIPIcs.STACS.2024.30}, annote = {Keywords: border complexity, Waring rank, debordering, apolarity} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Pranjal Dutta, Christian Ikenmeyer, Balagopal Komarath, Harshil Mittal, Saraswati Girish Nanoti, and Dhara Thakkar. On the Power of Border Width-2 ABPs over Fields of Characteristic 2. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dutta_et_al:LIPIcs.STACS.2024.31, author = {Dutta, Pranjal and Ikenmeyer, Christian and Komarath, Balagopal and Mittal, Harshil and Nanoti, Saraswati Girish and Thakkar, Dhara}, title = {{On the Power of Border Width-2 ABPs over Fields of Characteristic 2}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {31:1--31:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.31}, URN = {urn:nbn:de:0030-drops-197419}, doi = {10.4230/LIPIcs.STACS.2024.31}, annote = {Keywords: Algebraic branching programs, border complexity, characteristic 2} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Homogeneous Algebraic Complexity Theory and Algebraic Formulas. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 43:1-43:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dutta_et_al:LIPIcs.ITCS.2024.43, author = {Dutta, Pranjal and Gesmundo, Fulvio and Ikenmeyer, Christian and Jindal, Gorav and Lysikov, Vladimir}, title = {{Homogeneous Algebraic Complexity Theory and Algebraic Formulas}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {43:1--43: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.43}, URN = {urn:nbn:de:0030-drops-195713}, doi = {10.4230/LIPIcs.ITCS.2024.43}, annote = {Keywords: Homogeneous polynomials, Waring rank, Arithmetic formulas, Border complexity, Geometric Complexity theory, Symmetric polynomials} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 11:1-11:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{dutta_et_al:LIPIcs.CCC.2021.11, author = {Dutta, Pranjal and Dwivedi, Prateek and Saxena, Nitin}, title = {{Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {11:1--11: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.11}, URN = {urn:nbn:de:0030-drops-142857}, doi = {10.4230/LIPIcs.CCC.2021.11}, annote = {Keywords: Polynomial identity testing, hitting set, depth-4 circuits} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu. Arithmetic Circuit Complexity of Division and Truncation. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 25:1-25:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{dutta_et_al:LIPIcs.CCC.2021.25, author = {Dutta, Pranjal and Jindal, Gorav and Pandey, Anurag and Sinhababu, Amit}, title = {{Arithmetic Circuit Complexity of Division and Truncation}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {25:1--25:36}, 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.25}, URN = {urn:nbn:de:0030-drops-142990}, doi = {10.4230/LIPIcs.CCC.2021.25}, annote = {Keywords: Arithmetic Circuits, Division, Truncation, Division elimination, Rational function, Algebraic power series, Transcendental power series, Integer factorization} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Pranjal Dutta, Nitin Saxena, and Thomas Thierauf. A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{dutta_et_al:LIPIcs.ITCS.2021.23, author = {Dutta, Pranjal and Saxena, Nitin and Thierauf, Thomas}, title = {{A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {23:1--23:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.23}, URN = {urn:nbn:de:0030-drops-135629}, doi = {10.4230/LIPIcs.ITCS.2021.23}, annote = {Keywords: VP, VNP, hitting set, circuit, polynomial, sparsity, SOS, SOC, PIT, lower bound} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Amit Sinhababu and Thomas Thierauf. Factorization of Polynomials Given By Arithmetic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{sinhababu_et_al:LIPIcs.CCC.2020.33, author = {Sinhababu, Amit and Thierauf, Thomas}, title = {{Factorization of Polynomials Given By Arithmetic Branching Programs}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {33:1--33:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.33}, URN = {urn:nbn:de:0030-drops-125854}, doi = {10.4230/LIPIcs.CCC.2020.33}, annote = {Keywords: Arithmetic Branching Program, Multivariate Polynomial Factorization, Hensel Lifting, Newton Iteration, Hardness vs Randomness} }
Feedback for Dagstuhl Publishing