Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Vikraman Arvind and Pushkar S. Joglekar. A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arvind_et_al:LIPIcs.ICALP.2024.14, author = {Arvind, Vikraman and Joglekar, Pushkar S.}, title = {{A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {14:1--14:19}, 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.14}, URN = {urn:nbn:de:0030-drops-201571}, doi = {10.4230/LIPIcs.ICALP.2024.14}, annote = {Keywords: noncommutative rank, rational formulas, identity testing, parallel complexity} }
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 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 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.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, 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 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Markus Bläser and Gorav Jindal. On the Complexity of Symmetric Polynomials. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{blaser_et_al:LIPIcs.ITCS.2019.47, author = {Bl\"{a}ser, Markus and Jindal, Gorav}, title = {{On the Complexity of Symmetric Polynomials}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {47:1--47:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.47}, URN = {urn:nbn:de:0030-drops-101402}, doi = {10.4230/LIPIcs.ITCS.2019.47}, annote = {Keywords: Symmetric Polynomials, Arithmetic Circuits, Arithmetic Complexity, Power Series, Elementary Symmetric Polynomials, Newton's Iteration} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Gorav Jindal, Pavel Kolev, Richard Peng, and Saurabh Sawlani. Density Independent Algorithms for Sparsifying k-Step Random Walks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{jindal_et_al:LIPIcs.APPROX-RANDOM.2017.14, author = {Jindal, Gorav and Kolev, Pavel and Peng, Richard and Sawlani, Saurabh}, title = {{Density Independent Algorithms for Sparsifying k-Step Random Walks}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {14:1--14:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.14}, URN = {urn:nbn:de:0030-drops-75638}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.14}, annote = {Keywords: random walks, graph sparsification, spectral graph theory, effective resistances} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Markus Blaeser, Gorav Jindal, and Anurag Pandey. Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{blaeser_et_al:LIPIcs.CCC.2017.33, author = {Blaeser, Markus and Jindal, Gorav and Pandey, Anurag}, title = {{Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {33:1--33:16}, 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.33}, URN = {urn:nbn:de:0030-drops-75194}, doi = {10.4230/LIPIcs.CCC.2017.33}, annote = {Keywords: Commutative Rank, Matrix Spaces, PTAS, Wong sequences} }