Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
D. K. Arvind, Kemal Ebcioglu, Christian Lengauer, Keshav Pingali, and Robert S. Schreiber. Instruction-Level Parallelism and Parallelizing Compilation (Dagstuhl Seminar 99161). Dagstuhl Seminar Report 237, pp. 1-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1999)
@TechReport{arvind_et_al:DagSemRep.237, author = {Arvind, D. K. and Ebcioglu, Kemal and Lengauer, Christian and Pingali, Keshav and Schreiber, Robert S.}, title = {{Instruction-Level Parallelism and Parallelizing Compilation (Dagstuhl Seminar 99161)}}, pages = {1--30}, ISSN = {1619-0203}, year = {1999}, type = {Dagstuhl Seminar Report}, number = {237}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.237}, URN = {urn:nbn:de:0030-drops-151237}, doi = {10.4230/DagSemRep.237}, }
Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)
V. Arvind, Samir Datta, Asif Khan, Shivdutt Sharma, Yadu Vasudev, and Shankar Ram Vasudevan. The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2024.4, author = {Arvind, V. and Datta, Samir and Khan, Asif and Sharma, Shivdutt and Vasudev, Yadu and Vasudevan, Shankar Ram}, title = {{The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem}}, booktitle = {44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)}, pages = {4:1--4:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-355-3}, ISSN = {1868-8969}, year = {2024}, volume = {323}, editor = {Barman, Siddharth and Lasota, S{\l}awomir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.4}, URN = {urn:nbn:de:0030-drops-221939}, doi = {10.4230/LIPIcs.FSTTCS.2024.4}, annote = {Keywords: Dynamic Complexity, Group Theory, Cayley Group Membership, Abelian Group Isomorphism} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
V. Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On a Hierarchy of Spectral Invariants for Graphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arvind_et_al:LIPIcs.STACS.2024.6, author = {Arvind, V. and Fuhlbr\"{u}ck, Frank and K\"{o}bler, Johannes and Verbitsky, Oleg}, title = {{On a Hierarchy of Spectral Invariants for Graphs}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {6:1--6:18}, 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.6}, URN = {urn:nbn:de:0030-drops-197166}, doi = {10.4230/LIPIcs.STACS.2024.6}, annote = {Keywords: Graph Isomorphism, spectra of graphs, combinatorial refinement, strongly regular graphs} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
V. Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, and C. Ramya. On Identity Testing and Noncommutative Rank Computation over the Free Skew Field. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arvind_et_al:LIPIcs.ITCS.2023.6, author = {Arvind, V. and Chatterjee, Abhranil and Ghosal, Utsab and Mukhopadhyay, Partha and Ramya, C.}, title = {{On Identity Testing and Noncommutative Rank Computation over the Free Skew Field}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {6:1--6:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.6}, URN = {urn:nbn:de:0030-drops-175093}, doi = {10.4230/LIPIcs.ITCS.2023.6}, annote = {Keywords: Algebraic Complexity, Identity Testing, Non-commutative rank} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
V. Arvind, Abhranil Chatterjee, and Partha Mukhopadhyay. Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{arvind_et_al:LIPIcs.APPROX/RANDOM.2022.23, author = {Arvind, V. and Chatterjee, Abhranil and Mukhopadhyay, Partha}, title = {{Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {23:1--23: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.23}, URN = {urn:nbn:de:0030-drops-171451}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.23}, annote = {Keywords: Rational Identity Testing, Black-box Derandomization, Cyclic Division Algebra, Matrix coefficient realization theory} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Equivalence Testing of Weighted Automata over Partially Commutative Monoids. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arvind_et_al:LIPIcs.MFCS.2021.10, author = {Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha}, title = {{Equivalence Testing of Weighted Automata over Partially Commutative Monoids}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.10}, URN = {urn:nbn:de:0030-drops-144503}, doi = {10.4230/LIPIcs.MFCS.2021.10}, annote = {Keywords: Weighted Automata, Automata Equivalence, Partially Commutative Monoid} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. A Special Case of Rational Identity Testing and the Brešar-Klep Theorem. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{arvind_et_al:LIPIcs.MFCS.2020.10, author = {Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha}, title = {{A Special Case of Rational Identity Testing and the Bre\v{s}ar-Klep Theorem}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {10:1--10:14}, 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.10}, URN = {urn:nbn:de:0030-drops-126807}, doi = {10.4230/LIPIcs.MFCS.2020.10}, annote = {Keywords: Rational identity testing, ABP with inverses, Bre\v{s}ar-Klep Theorem, Invertible image, Amitsur’s theorem} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Fast Exact Algorithms Using Hadamard Product of Polynomials. 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. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2019.9, author = {Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha}, title = {{Fast Exact Algorithms Using Hadamard Product of Polynomials}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {9:1--9: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.9}, URN = {urn:nbn:de:0030-drops-115711}, doi = {10.4230/LIPIcs.FSTTCS.2019.9}, annote = {Keywords: Hadamard Product, Multilinear Monomial Detection and Counting, Rectangular Permanent, Symmetric Polynomial} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{arvind_et_al:LIPIcs.ISAAC.2019.38, author = {Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha}, title = {{On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {38:1--38:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.38}, URN = {urn:nbn:de:0030-drops-115340}, doi = {10.4230/LIPIcs.ISAAC.2019.38}, annote = {Keywords: Determinant, Permanent, Parameterized Complexity, Branching Programs} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Efficient Black-Box Identity Testing for Free Group Algebras. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{arvind_et_al:LIPIcs.APPROX-RANDOM.2019.57, author = {Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha}, title = {{Efficient Black-Box Identity Testing for Free Group Algebras}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {57:1--57:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.57}, URN = {urn:nbn:de:0030-drops-112723}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.57}, annote = {Keywords: Rational identity testing, Free group algebra, Noncommutative computation, Randomized algorithms} }
Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2018.7, author = {Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha}, title = {{Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators}}, booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-093-4}, ISSN = {1868-8969}, year = {2018}, volume = {122}, editor = {Ganguly, Sumit and Pandya, Paritosh}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.7}, URN = {urn:nbn:de:0030-drops-99068}, doi = {10.4230/LIPIcs.FSTTCS.2018.7}, annote = {Keywords: Combinatorial Nullstellensatz, Ideal Membership, Parametric Hardness, Low Rank Permanent} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
V. Arvind, Bireswar Das, Johannes Köbler, and Seinosuke Toda. Colored Hypergraph Isomorphism is Fixed Parameter Tractable. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 327-337, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2010.327, author = {Arvind, V. and Das, Bireswar and K\"{o}bler, Johannes and Toda, Seinosuke}, title = {{Colored Hypergraph Isomorphism is Fixed Parameter Tractable}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {327--337}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.327}, URN = {urn:nbn:de:0030-drops-28751}, doi = {10.4230/LIPIcs.FSTTCS.2010.327}, annote = {Keywords: Fixed parameter tractability, fpt algorithms, graph isomorphism, computational complexity} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
V. Arvind and Pushkar S. Joglekar. Some Sieving Algorithms for Lattice Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 25-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2008.1738, author = {Arvind, V. and Joglekar, Pushkar S.}, title = {{Some Sieving Algorithms for Lattice Problems}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {25--36}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-08-8}, ISSN = {1868-8969}, year = {2008}, volume = {2}, editor = {Hariharan, Ramesh and Mukund, Madhavan and Vinay, V}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1738}, URN = {urn:nbn:de:0030-drops-17380}, doi = {10.4230/LIPIcs.FSTTCS.2008.1738}, annote = {Keywords: Lattice problems, sieving algorithm, closest vector problem} }
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 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Vikraman Arvind and Pushkar S. Joglekar. Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arvind_et_al:LIPIcs.MFCS.2023.14, author = {Arvind, Vikraman and Joglekar, Pushkar S.}, title = {{Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {14:1--14:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.14}, URN = {urn:nbn:de:0030-drops-185480}, doi = {10.4230/LIPIcs.MFCS.2023.14}, annote = {Keywords: Arithmetic circuits, algebraic branching programs, polynomial factorization, automata, noncommutative polynomial ring} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Vikraman Arvind and Pushkar S. Joglekar. On Efficient Noncommutative Polynomial Factorization via Higman Linearization. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{arvind_et_al:LIPIcs.CCC.2022.12, author = {Arvind, Vikraman and Joglekar, Pushkar S.}, title = {{On Efficient Noncommutative Polynomial Factorization via Higman Linearization}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {12:1--12:22}, 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.12}, URN = {urn:nbn:de:0030-drops-165747}, doi = {10.4230/LIPIcs.CCC.2022.12}, annote = {Keywords: Noncommutative Polynomials, Arithmetic Circuits, Factorization, Identity testing} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Vikraman Arvind and Venkatesan Guruswami. CNF Satisfiability in a Subspace and Related Problems. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arvind_et_al:LIPIcs.IPEC.2021.5, author = {Arvind, Vikraman and Guruswami, Venkatesan}, title = {{CNF Satisfiability in a Subspace and Related Problems}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {5:1--5:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.5}, URN = {urn:nbn:de:0030-drops-153886}, doi = {10.4230/LIPIcs.IPEC.2021.5}, annote = {Keywords: CNF Satisfiability, Exact exponential algorithms, Hardness results} }
Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{arvind_et_al:LIPIcs.IPEC.2017.2, author = {Arvind, Vikraman and K\"{o}bler, Johannes and Kuhnert, Sebastian and Tor\'{a}n, Jacobo}, title = {{Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {2:1--2:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.2}, URN = {urn:nbn:de:0030-drops-85690}, doi = {10.4230/LIPIcs.IPEC.2017.2}, annote = {Keywords: parameterized algorithms, hypergraph isomorphism, mislabeled graphs} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, and S. Raja. Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{arvind_et_al:LIPIcs.MFCS.2017.38, author = {Arvind, Vikraman and Datta, Rajit and Mukhopadhyay, Partha and Raja, S.}, title = {{Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {38:1--38:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.38}, URN = {urn:nbn:de:0030-drops-80690}, doi = {10.4230/LIPIcs.MFCS.2017.38}, annote = {Keywords: Circuits, Nonassociative, Noncommutative, Polynomial Identity Testing, Factorization} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Parameterized Complexity of Small Weight Automorphisms. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{arvind_et_al:LIPIcs.STACS.2017.7, author = {Arvind, Vikraman and K\"{o}bler, Johannes and Kuhnert, Sebastian and Tor\'{a}n, Jacobo}, title = {{Parameterized Complexity of Small Weight Automorphisms}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {7:1--7:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert 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.2017.7}, URN = {urn:nbn:de:0030-drops-70278}, doi = {10.4230/LIPIcs.STACS.2017.7}, annote = {Keywords: Parameterized algorithms, hypergraph isomorphism.} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, and Gaurav Rattan. The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{arvind_et_al:LIPIcs.MFCS.2016.13, author = {Arvind, Vikraman and Fuhlbr\"{u}ck, Frank and K\"{o}bler, Johannes and Kuhnert, Sebastian and Rattan, Gaurav}, title = {{The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {13:1--13:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.13}, URN = {urn:nbn:de:0030-drops-64294}, doi = {10.4230/LIPIcs.MFCS.2016.13}, annote = {Keywords: parameterized complexity, graph automorphism, fixing number, base size, individualization} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Vikraman Arvind and Srikanth Srinivasan. The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 59-70, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{arvind_et_al:LIPIcs.STACS.2010.2444, author = {Arvind, Vikraman and Srinivasan, Srikanth}, title = {{The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {59--70}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2444}, URN = {urn:nbn:de:0030-drops-24449}, doi = {10.4230/LIPIcs.STACS.2010.2444}, annote = {Keywords: Small Bias Spaces, Expander Graphs, Cayley Graphs, Remote Point Problem} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Vikraman Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan. Arithmetic Circuits and the Hadamard Product of Polynomials. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 25-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2009.2304, author = {Arvind, Vikraman and Joglekar, Pushkar S. and Srinivasan, Srikanth}, title = {{Arithmetic Circuits and the Hadamard Product of Polynomials}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {25--36}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2304}, URN = {urn:nbn:de:0030-drops-23046}, doi = {10.4230/LIPIcs.FSTTCS.2009.2304}, annote = {Keywords: Hadamard product, identity testing, lower bounds, algebraic branching programs} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Vikraman Arvind and Partha Mukhopadhyay. Quantum Query Complexity of Multilinear Identity Testing. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 87-98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{arvind_et_al:LIPIcs.STACS.2009.1801, author = {Arvind, Vikraman and Mukhopadhyay, Partha}, title = {{Quantum Query Complexity of Multilinear Identity Testing}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {87--98}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1801}, URN = {urn:nbn:de:0030-drops-18014}, doi = {10.4230/LIPIcs.STACS.2009.1801}, annote = {Keywords: Quantum algorithm, Identity testing, Query complexity, Multilinear polynomials} }
Feedback for Dagstuhl Publishing