Search Results

Documents authored by Bhargava, Vishwas

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.28
Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition

Authors: Vishwas Bhargava and Devansh Shringi

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We present a deterministic 2^{k^{𝒪(1)}} poly(n,d) time algorithm for decomposing d-dimensional, width-n tensors of rank at most k over ℝ and ℂ. This improves upon the previous randomized algorithm of Peleg, Shpilka, and Volk (ITCS '24) that takes 2^{k^{k^{𝒪(k)}}} poly(n,d) time and the deterministic n^k^k time algorithms of Bhargava, Saraf, and Volkovich (STOC '21). Our work resolves an open question asked by Peleg, Shpilka, and Volk (ITCS '24) on whether a deterministic Fixed Parameter Tractable (FPT) algorithm exists for worst-case tensor decomposition. We also make substantial progress on the fundamental problem of how the tractability of tensor decomposition varies as the tensor rank increases. Our result implies that we can achieve deterministic polynomial-time decomposition as long as the rank of the tensor is at most (log n)^{1/C}, where C is some fixed constant independent of n and d. Further, we note that there cannot exist a polynomial-time algorithm for k = ω(log n) unless ETH fails. Our algorithm works for all fields; however, the time complexity worsens to 2^{k^{k^{𝒪(1)}}} and requires randomization for finite fields of large characteristics. Both conditions are provably necessary unless there are improvements in the state of the art for system solving over the corresponding fields. Our approach achieves this by designing a proper learning (reconstruction) algorithm for set-multilinear depth-3 arithmetic circuits. On a technical note, we design a "partial" clustering algorithm for set-multilinear depth-3 arithmetic circuits that lets us isolate a cluster from any set-multilinear depth-3 circuit while preserving the structure of the circuit.
Cite as

Vishwas Bhargava and Devansh Shringi. Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhargava_et_al:LIPIcs.ICALP.2025.28,
  author =	{Bhargava, Vishwas and Shringi, Devansh},
  title =	{{Faster \& Deterministic FPT Algorithm for Worst-Case Tensor Decomposition}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.28},
  URN =		{urn:nbn:de:0030-drops-234052},
  doi =		{10.4230/LIPIcs.ICALP.2025.28},
  annote =	{Keywords: Algebraic circuits, Deterministic algorithms, FPT algorithm, Learning circuits, Reconstruction, Tensor Decomposition, Tensor Rank}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2024.10
Explicit Commutative ROABPs from Partial Derivatives

Authors: Vishwas Bhargava and Anamay Tengse

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract
The dimension of partial derivatives (Nisan and Wigderson, 1997) is a popular measure for proving lower bounds in algebraic complexity. It is used to give strong lower bounds on the Waring decomposition of polynomials (called Waring rank). This naturally leads to an interesting open question: does this measure essentially characterize the Waring rank of any polynomial? The well-studied model of Read-once Oblivious ABPs (ROABPs for short) lends itself to an interesting hierarchy of "sub-models": Any-Order-ROABPs (ARO), Commutative ROABPs, and Diagonal ROABPs. It follows from previous works that for any polynomial, a bound on its Waring rank implies an analogous bound on its Diagonal ROABP complexity (called the duality trick), and a bound on its dimension of partial derivatives implies an analogous bound on its "ARO complexity": ROABP complexity in any order (Nisan, 1991). Our work strengthens the latter connection by showing that a bound on the dimension of partial derivatives in fact implies a bound on the commutative ROABP complexity. Thus, we improve our understanding of partial derivatives and move a step closer towards answering the above question. Our proof builds on the work of Ramya and Tengse (2022) to show that the commutative-ROABP-width of any homogeneous polynomial is at most the dimension of its partial derivatives. The technique itself is a generalization of the proof of the duality trick due to Saxena (2008).
Cite as

Vishwas Bhargava and Anamay Tengse. Explicit Commutative ROABPs from Partial Derivatives. 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. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhargava_et_al:LIPIcs.FSTTCS.2024.10,
  author =	{Bhargava, Vishwas and Tengse, Anamay},
  title =	{{Explicit Commutative ROABPs from Partial Derivatives}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{10:1--10:15},
  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.10},
  URN =		{urn:nbn:de:0030-drops-221994},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.10},
  annote =	{Keywords: Partial derivatives, Apolar ideals, Commuting matrices, Branching programs}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.21
Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case

Authors: Vishwas Bhargava, Ankit Garg, Neeraj Kayal, and Chandan Saha

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
Consider a homogeneous degree d polynomial f = T₁ + ⋯ + T_s, T_i = g_i(𝓁_{i,1}, …, 𝓁_{i, m}) where g_i’s are homogeneous m-variate degree d polynomials and 𝓁_{i,j}’s are linear polynomials in n variables. We design a (randomized) learning algorithm that given black-box access to f, computes black-boxes for the T_i’s. The running time of the algorithm is poly(n, m, d, s) and the algorithm works under some non-degeneracy conditions on the linear forms and the g_i’s, and some additional technical assumptions n ≥ (md)², s ≤ n^{d/4}. The non-degeneracy conditions on 𝓁_{i,j}’s constitute non-membership in a variety, and hence are satisfied when the coefficients of 𝓁_{i,j}’s are chosen uniformly and randomly from a large enough set. The conditions on g_i’s are satisfied for random polynomials and also for natural polynomials common in the study of arithmetic complexity like determinant, permanent, elementary symmetric polynomial, iterated matrix multiplication. A particularly appealing algorithmic corollary is the following: Given black-box access to an f = Det_r(L^(1)) + … + Det_r(L^(s)), where L^(k) = (𝓁_{i,j}^(k))_{i,j} with 𝓁_{i,j}^(k)’s being linear forms in n variables chosen randomly, there is an algorithm which in time poly(n, r) outputs matrices (M^(k))_k of linear forms s.t. there exists a permutation π: [s] → [s] with Det_r(M^(k)) = Det_r(L^(π(k))). Our work follows the works [Neeraj Kayal and Chandan Saha, 2019; Garg et al., 2020] which use lower bound methods in arithmetic complexity to design average case learning algorithms. It also vastly generalizes the result in [Neeraj Kayal and Chandan Saha, 2019] about learning depth three circuits, which is a special case where each g_i is just a monomial. At the core of our algorithm is the partial derivative method which can be used to prove lower bounds for generalized depth three circuits. To apply the general framework in [Neeraj Kayal and Chandan Saha, 2019; Garg et al., 2020], we need to establish that the non-degeneracy conditions arising out of applying the framework with the partial derivative method are satisfied in the random case. We develop simple but general and powerful tools to establish this, which might be useful in designing average case learning algorithms for other arithmetic circuit models.
Cite as

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, and Chandan Saha. Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhargava_et_al:LIPIcs.APPROX/RANDOM.2022.21,
  author =	{Bhargava, Vishwas and Garg, Ankit and Kayal, Neeraj and Saha, Chandan},
  title =	{{Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{21:1--21: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.21},
  URN =		{urn:nbn:de:0030-drops-171430},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.21},
  annote =	{Keywords: Arithemtic Circuits, Average-case Learning, Depth 3 Arithmetic Circuits, Learning Algorithms, Learning Circuits, Circuit Reconstruction}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.30
Improved Hitting Set for Orbit of ROABPs

Authors: Vishwas Bhargava and Sumanta Ghosh

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
The orbit of an n-variate polynomial f(x) over a field 𝔽 is the set {f(Ax+b) ∣ A ∈ GL(n, 𝔽) and b ∈ 𝔽ⁿ}, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of hitting-sets for the orbit of read-once oblivious algebraic branching programs (ROABPs) and a related model. Over fields with characteristic zero or greater than d, we construct a hitting set of size (ndw)^{O(w²log n⋅ min{w², dlog w})} for the orbit of ROABPs in unknown variable order where d is the individual degree and w is the width of ROABPs. We also give a hitting set of size (ndw)^{O(min{w²,dlog w})} for the orbit of polynomials computed by w-width ROABPs in any variable order. Our hitting sets improve upon the results of Saha and Thankey [Chandan Saha and Bhargav Thankey, 2021] who gave an (ndw)^{O(dlog w)} size hitting set for the orbit of commutative ROABPs (a subclass of any-order ROABPs) and (nw)^{O(w⁶log n)} size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance d > n, was asked as an open problem by [Chandan Saha and Bhargav Thankey, 2021] and this work solves it in small width setting. We prove some new rank concentration results by establishing low-cone concentration for the polynomials over vector spaces, and they strengthen some previously known low-support based rank concentrations shown in [Michael A. Forbes et al., 2013]. These new low-cone concentration results are crucial in our hitting set construction, and may be of independent interest. To the best of our knowledge, this is the first time when low-cone rank concentration has been used for designing hitting sets.
Cite as

Vishwas Bhargava and Sumanta Ghosh. Improved Hitting Set for Orbit of ROABPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 30:1-30:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhargava_et_al:LIPIcs.APPROX/RANDOM.2021.30,
  author =	{Bhargava, Vishwas and Ghosh, Sumanta},
  title =	{{Improved Hitting Set for Orbit of ROABPs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{30:1--30:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.30},
  URN =		{urn:nbn:de:0030-drops-147231},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.30},
  annote =	{Keywords: Hitting Set, Low Cone Concentration, Orbits, PIT, ROABP}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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