5 Search Results for "Arvind, D. K."

Document
DOI: 10.4230/LIPIcs.ITCS.2024.79
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions

Authors: Arvind V. Mahankali, David P. Woodruff, and Ziyu Zhang

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We study low rank approximation of tensors, focusing on the Tensor Train and Tucker decompositions, as well as approximations with tree tensor networks and general tensor networks. As suggested by hardness results also shown in this work, obtaining (1+ε)-approximation algorithms for rank k tensor train and Tucker decompositions efficiently may be computationally hard for these problems. Therefore, we propose different algorithms that respectively satisfy some of the objectives above while violating some others within a bound, known as bicriteria algorithms. On the one hand, for rank-k tensor train decomposition for tensors with q modes, we give a (1 + ε)-approximation algorithm with a small bicriteria rank (O(qk/ε) up to logarithmic factors) and O(q ⋅ nnz(A)) running time, up to lower order terms. Here nnz(A) denotes the number of non-zero entries in the input tensor A. We also show how to convert the algorithm of [Huber et al., 2017] into a relative error approximation algorithm, but their algorithm necessarily has a running time of O(qr² ⋅ nnz(A)) + n ⋅ poly(qk/ε) when converted to a (1 + ε)-approximation algorithm with bicriteria rank r. Thus, the running time of our algorithm is better by at least a k² factor. To the best of our knowledge, our work is the first to achieve a near-input-sparsity time relative error approximation algorithm for tensor train decomposition. Our key technique is a method for efficiently obtaining subspace embeddings for a matrix which is the flattening of a Tensor Train of q tensors - the number of rows in the subspace embeddings is polynomial in q, thus avoiding the curse of dimensionality. We extend our algorithm to tree tensor networks and tensor networks on arbitrary graphs. Another way of coping with intractability is by looking at fixed-parameter tractable (FPT) algorithms. We give FPT algorithms for the tensor train, Tucker, and Canonical Polyadic (CP) decompositions, which are simpler than the FPT algorithms of [Song et al., 2019], since our algorithms do not make use of polynomial system solvers. Our technique of using an exponential number of Gaussian subspace embeddings with exactly k rows (and thus exponentially small success probability) may be of independent interest.
Cite as

Arvind V. Mahankali, David P. Woodruff, and Ziyu Zhang. Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 79:1-79:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mahankali_et_al:LIPIcs.ITCS.2024.79,
  author =	{Mahankali, Arvind V. and Woodruff, David P. and Zhang, Ziyu},
  title =	{{Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{79:1--79: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.79},
  URN =		{urn:nbn:de:0030-drops-196078},
  doi =		{10.4230/LIPIcs.ITCS.2024.79},
  annote =	{Keywords: Low rank approximation, Sketching algorithms, Tensor decomposition}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.10
A Special Case of Rational Identity Testing and the Brešar-Klep Theorem

Authors: V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We explore a special case of rational identity testing and algorithmic versions of two theorems on noncommutative polynomials, namely, Amitsur's theorem [S.A Amitsur, 1966] and the Brešar-Klep theorem [Brešar and Klep, 2008] when the input polynomial is given by an algebraic branching program (ABP). Let f be a degree-d n-variate noncommutative polynomial in the free ring Q<x_1,x_2,...,x_n> over rationals. 1) We consider the following special case of rational identity testing: Given a noncommutative ABP as white-box, whose edge labels are linear forms or inverses of linear forms, we show a deterministic polynomial-time algorithm to decide if the rational function computed by it is equivalent to zero in the free skew field Q<(X)>. Given black-box access to the ABP, we give a deterministic quasi-polynomial time algorithm for this problem. 2) Amitsur's theorem implies that if a noncommutative polynomial f is nonzero on k x k matrices then, in fact, f(M_1,M_2,...,M_n) is invertible for some matrix tuple (M_1,M_2,...,M_n) in (M_k(ℚ))^n. While a randomized polynomial time algorithm to find such (M_1,M_2,...,M_n) given black-box access to f is simple, we obtain a deterministic s^{O(log d)} time algorithm for the problem with black-box access to f, where s is the minimum ABP size for f and d is the degree of f. 3) The Brešar-Klep Theorem states that the span of the range of any noncommutative polynomial f on k x k matrices over Q is one of the following: zero, scalar multiples of I_k, trace-zero matrices in M_k(Q), or all of M_k(Q). We obtain a deterministic polynomial-time algorithm to decide which case occurs, given white-box access to an ABP for f. We also give a deterministic s^{O(log d)} time algorithm given black-box access to an ABP of size s for f. Our algorithms work when k >= d. Our techniques are based on some automata theory combined with known techniques for noncommutative ABP identity testing [Ran Raz and Amir Shpilka, 2005; Michael A. Forbes and Amir Shpilka, 2013].
Cite as

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)

Copy BibTex To Clipboard

@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-dev.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}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.7
Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators

Authors: V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
Let F[X] be the polynomial ring over the variables X={x_1,x_2, ..., x_n}. An ideal I= <p_1(x_1), ..., p_n(x_n)> generated by univariate polynomials {p_i(x_i)}_{i=1}^n is a univariate ideal. We study the ideal membership problem for the univariate ideals and show the following results. - Let f(X) in F[l_1, ..., l_r] be a (low rank) polynomial given by an arithmetic circuit where l_i : 1 <= i <= r are linear forms, and I=<p_1(x_1), ..., p_n(x_n)> be a univariate ideal. Given alpha in F^n, the (unique) remainder f(X) mod I can be evaluated at alpha in deterministic time d^{O(r)} * poly(n), where d=max {deg(f),deg(p_1)...,deg(p_n)}. This yields a randomized n^{O(r)} algorithm for minimum vertex cover in graphs with rank-r adjacency matrices. It also yields an n^{O(r)} algorithm for evaluating the permanent of a n x n matrix of rank r, over any field F. Over Q, an algorithm of similar run time for low rank permanent is due to Barvinok [Barvinok, 1996] via a different technique. - Let f(X)in F[X] be given by an arithmetic circuit of degree k (k treated as fixed parameter) and I=<p_1(x_1), ..., p_n(x_n)>. We show that in the special case when I=<x_1^{e_1}, ..., x_n^{e_n}>, we obtain a randomized O^*(4.08^k) algorithm that uses poly(n,k) space. - Given f(X)in F[X] by an arithmetic circuit and I=<p_1(x_1), ..., p_k(x_k)>, membership testing is W[1]-hard, parameterized by k. The problem is MINI[1]-hard in the special case when I=<x_1^{e_1}, ..., x_k^{e_k}>.
Cite as

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)

Copy BibTex To Clipboard

@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-dev.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}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.13
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs

Authors: Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, and Gaurav Rattan

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
In this paper we study the complexity of the following problems: 1. Given a colored graph X=(V,E,c), compute a minimum cardinality set of vertices S (subset of V) such that no nontrivial automorphism of X fixes all vertices in S. A closely related problem is computing a minimum base S for a permutation group G <= S_n given by generators, i.e., a minimum cardinality subset S of [n] such that no nontrivial permutation in G fixes all elements of S. Our focus is mainly on the parameterized complexity of these problems. We show that when k=|S| is treated as parameter, then both problems are MINI[1]-hard. For the dual problems, where k=n-|S| is the parameter, we give FPT~algorithms. 2. A notion closely related to fixing is called individualization. Individualization combined with the Weisfeiler-Leman procedure is a fundamental technique in algorithms for Graph Isomorphism. Motivated by the power of individualization, in the present paper we explore the complexity of individualization: what is the minimum number of vertices we need to individualize in a given graph such that color refinement "succeeds" on it. Here "succeeds" could have different interpretations, and we consider the following: It could mean the individualized graph becomes: (a) discrete, (b) amenable, (c)compact, or (d) refinable. In particular, we study the parameterized versions of these problems where the parameter is the number of vertices individualized. We show a dichotomy: For graphs with color classes of size at most 3 these problems can be solved in polynomial time, while starting from color class size 4 they become W[P]-hard.
Cite as

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)

Copy BibTex To Clipboard

@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-dev.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}
}
Document
DOI: 10.4230/DagSemRep.237
Instruction-Level Parallelism and Parallelizing Compilation (Dagstuhl Seminar 99161)

Authors: D. K. Arvind, Kemal Ebcioglu, Christian Lengauer, Keshav Pingali, and Robert S. Schreiber

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

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)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.237},
  URN =		{urn:nbn:de:0030-drops-151237},
  doi =		{10.4230/DagSemRep.237},
}
  • Refine by Author
  • 2 Arvind, V.
  • 2 Chatterjee, Abhranil
  • 2 Datta, Rajit
  • 2 Mukhopadhyay, Partha
  • 1 Arvind, D. K.
  • Show More...

  • Refine by Classification
  • 2 Theory of computation
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 ABP with inverses
  • 1 Amitsur’s theorem
  • 1 Brešar-Klep Theorem
  • 1 Combinatorial Nullstellensatz
  • 1 Ideal Membership
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 1999
  • 1 2016
  • 1 2018
  • 1 2020
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact