Search Results

Documents authored by Chillara, Suryajith

Document
DOI: 10.4230/LIPIcs.STACS.2023.22
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

Authors: Suryajith Chillara, Coral Grichener, and Amir Shpilka

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
We say that two given polynomials f, g ∈ R[x_1, ..., x_n], over a ring R, are equivalent under shifts if there exists a vector (a_1, ..., a_n) ∈ Rⁿ such that f(x_1+a_1, ..., x_n+a_n) = g(x_1, ..., x_n). This is a special variant of the polynomial projection problem in Algebraic Complexity Theory. Grigoriev and Karpinski (FOCS 1990), Lakshman and Saunders (SIAM J. Computing, 1995), and Grigoriev and Lakshman (ISSAC 1995) studied the problem of testing polynomial equivalence of a given polynomial to any t-sparse polynomial, over the rational numbers, and gave exponential time algorithms. In this paper, we provide hardness results for this problem. Formally, for a ring R, let SparseShift_R be the following decision problem - Given a polynomial P(X), is there a vector 𝐚 such that P(X+𝐚) contains fewer monomials than P(X). We show that SparseShift_R is at least as hard as checking if a given system of polynomial equations over R[x_1,..., x_n] has a solution (Hilbert’s Nullstellensatz). As a consequence of this reduction, we get the following results. 1) SparseShift_ℤ is undecidable. 2) For any ring R (which is not a field) such that HN_R is NP_R-complete over the Blum-Shub-Smale model of computation, SparseShift_ is also NP_R-complete. In particular, SparseShift_ℤ is also NP_ℤ-complete. We also study the gap version of the SparseShift_R and show the following. 1) For every function β:ℕ → ℝ_+ such that β ∈ o(1), N^β-gap-SparseShift_ℤ is also undecidable (where N is the input length). 2) For R = 𝔽_p, ℚ, ℝ or ℤ_q and for every β > 1 the β-gap-SparseShift_R problem is NP-hard. Furthermore, there exists a constant α > 1 such that for every d = O(1) in the sparse representation model, and for every d ≤ n^O(1) in the arithmetic circuit model, the α^d-gap-SparseShift_R problem is NP-hard when given polynomials of degree at most d, in O(nd) many variables, as input.
Cite as

Suryajith Chillara, Coral Grichener, and Amir Shpilka. On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chillara_et_al:LIPIcs.STACS.2023.22,
  author =	{Chillara, Suryajith and Grichener, Coral and Shpilka, Amir},
  title =	{{On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.22},
  URN =		{urn:nbn:de:0030-drops-176744},
  doi =		{10.4230/LIPIcs.STACS.2023.22},
  annote =	{Keywords: algebraic complexity, shift equivalence, polynomial equivalence, Hilbert’s Nullstellensatz, hardness of approximation}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.14
Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four

Authors: Suryajith Chillara

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit d^{O(1)}-variate and degree d polynomial P_{d} ∈ VNP such that if any depth four circuit C of bounded formal degree d which computes a polynomial of bounded individual degree O(1), that is functionally equivalent to P_d, then C must have size 2^Ω(√dlog{d}). The motivation for their work comes from Boolean Circuit Complexity. Based on a characterization for ACC⁰ circuits by Yao [FOCS, 1985] and Beigel and Tarui [CC, 1994], Forbes, Kumar and Saptharishi [CCC, 2016] observed that functions in ACC⁰ can also be computed by algebraic Σ∧ΣΠ circuits (i.e., circuits of the form - sums of powers of polynomials) of 2^(log^O(1) n) size. Thus they argued that a 2^{ω(polylog n)} "functional" lower bound for an explicit polynomial Q against Σ∧ΣΠ circuits would imply a lower bound for the "corresponding Boolean function" of Q against non-uniform ACC⁰. In their work, they ask if their lower bound be extended to Σ∧ΣΠ circuits. In this paper, for large integers n and d such that ω(log²n) ≤ d ≤ n^{0.01}, we show that any Σ∧ΣΠ circuit of bounded individual degree at most O(d/k²) that functionally computes Iterated Matrix Multiplication polynomial IMM_{n,d} (∈ VP) over {0,1}^{n²d} must have size n^Ω(k). Since Iterated Matrix Multiplication IMM_{n,d} over {0,1}^{n²d} is functionally in GapL, improvement of the afore mentioned lower bound to hold for quasipolynomially large values of individual degree would imply a fine-grained separation of ACC⁰ from GapL. For the sake of completeness, we also show a syntactic size lower bound against any Σ∧ΣΠ circuit computing IMM_{n,d} (for the same regime of d) which is tight over large fields. Like Forbes, Kumar and Saptharishi [CCC, 2016], we too prove lower bounds against circuits of bounded formal degree which functionally compute IMM_{n,d}, for a slightly larger range of individual degree.
Cite as

Suryajith Chillara. Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chillara:LIPIcs.FSTTCS.2021.14,
  author =	{Chillara, Suryajith},
  title =	{{Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.14},
  URN =		{urn:nbn:de:0030-drops-155251},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.14},
  annote =	{Keywords: Functional Lower Bounds, Boolean Circuit Lower Bounds, Depth Four, Connections to Boolean Complexity, Iterated Matrix Multiplication}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.47
On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits

Authors: Suryajith Chillara

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of r (referred to as multi-r-ic circuits). The goal of this study is to make progress towards proving superpolynomial lower bounds for general depth four circuits computing multilinear polynomials, by proving better and better bounds as the value of r increases. Recently, Kayal, Saha and Tavenas (Theory of Computing, 2018) showed that any depth four arithmetic circuit of bounded individual degree r computing a multilinear polynomial on n^O(1) variables and degree d=o(n), must have size at least (n/r^1.1)^Ω(√{d/r}) when r is o(d) and is strictly less than n^1.1. This bound however deteriorates with increasing r. It is a natural question to ask if we can prove a bound that does not deteriorate with increasing r or a bound that holds for a larger regime of r. We here prove a lower bound which does not deteriorate with r, however for a specific instance of d = d(n) but for a wider range of r. Formally, we show that there exists an explicit polynomial on n^O(1) variables and degree Θ(log² n) such that any depth four circuit of bounded individual degree r<n^0.2 must have size at least exp(Ω(log² n)). This improvement is obtained by suitably adapting the complexity measure of Kayal et al. (Theory of Computing, 2018). This adaptation of the measure is inspired by the complexity measure used by Kayal et al. (SIAM J. Computing, 2017).
Cite as

Suryajith Chillara. On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chillara:LIPIcs.STACS.2020.47,
  author =	{Chillara, Suryajith},
  title =	{{On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{47:1--47:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.47},
  URN =		{urn:nbn:de:0030-drops-119084},
  doi =		{10.4230/LIPIcs.STACS.2020.47},
  annote =	{Keywords: Lower Bounds, Multilinear, Multi-r-ic}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.36
A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas

Authors: Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We show explicit separations between the expressive powers of multilinear formulas of small-depth and all polynomial sizes. Formally, for any s = s(n) = n^{O(1)} and any delta>0, we construct explicit families of multilinear polynomials P_n in F[x_1,...,x_n] that have multilinear formulas of size s and depth three but no multilinear formulas of size s^{1/2-delta} and depth o(log n/log log n). As far as we know, this is the first such result for an algebraic model of computation. Our proof can be viewed as a derandomization of a lower bound technique of Raz (JACM 2009) using epsilon-biased spaces.
Cite as

Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chillara_et_al:LIPIcs.ICALP.2018.36,
  author =	{Chillara, Suryajith and Limaye, Nutan and Srinivasan, Srikanth},
  title =	{{A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{36:1--36:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.36},
  URN =		{urn:nbn:de:0030-drops-90401},
  doi =		{10.4230/LIPIcs.ICALP.2018.36},
  annote =	{Keywords: Algebraic circuit complexity, Multilinear formulas, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.21
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications

Authors: Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within P. In this paper, we study the algebraic formula complexity of multiplying d many 2x2 matrices, denoted IMM_d, and show that the well-known divide-and-conquer algorithm cannot be significantly improved at any depth, as long as the formulas are multilinear. Formally, for each depth Delta <= log d, we show that any product-depth Delta multilinear formula for IMM_d must have size exp(Omega(Delta d^{1/Delta})). It also follows from this that any multilinear circuit of product-depth Delta for the same polynomial of the above form must have a size of exp(Omega(d^{1/Delta})). In particular, any polynomial-sized multilinear formula for IMM_d must have depth Omega(log d), and any polynomial-sized multilinear circuit for IMM_d must have depth Omega(log d/log log d). Both these bounds are tight up to constant factors. Our lower bound has the following consequences for multilinear formula complexity. Depth-reduction: A well-known result of Brent (JACM 1974) implies that any formula of size s can be converted to one of size s^{O(1)} and depth O(log s); further, this reduction continues to hold for multilinear formulas. On the other hand, our lower bound implies that any depth-reduction in the multilinear setting cannot reduce the depth to o(log s) without a superpolynomial blow-up in size. Separations from general formulas: Shpilka and Yehudayoff (FnTTCS 2010) asked whether general formulas can be more efficient than multilinear formulas for computing multilinear polynomials. Our result, along with a non-trivial upper bound for IMM_d implied by a result of Gupta, Kamath, Kayal and Saptharishi (SICOMP 2016), shows that for any size s and product-depth Delta = o(log s), general formulas of size s and product-depth Delta cannot be converted to multilinear formulas of size s^{O(1)} and product-depth Delta, when the underlying field has characteristic zero.
Cite as

Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chillara_et_al:LIPIcs.STACS.2018.21,
  author =	{Chillara, Suryajith and Limaye, Nutan and Srinivasan, Srikanth},
  title =	{{Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.21},
  URN =		{urn:nbn:de:0030-drops-85235},
  doi =		{10.4230/LIPIcs.STACS.2018.21},
  annote =	{Keywords: Algebraic circuit complexity, Multilinear formulas, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.239
Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach

Authors: Suryajith Chillara and Partha Mukhopadhyay

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
Tavenas has recently proved that any n^{O(1)}-variate and degree n polynomial in VP can be computed by a depth-4 SigmaPi^[O(sqrt{n})]SigmaPi^{[sqrt{n}]} circuit of size 2^{O(n^{1/2}.log(n))} [Tavenas, 2013]. So, to prove that VP is not equal to VNP it is sufficient to show that an explicit polynomial in VNP of degree n requires 2^{omega(n^{1/2}.log(n))} size depth-4 circuits. Soon after Tavenas' result, for two different explicit polynomials, depth-4 circuit size lower bounds of 2^{Omega(n^{1/2}.log(n))} have been proved (see [Kayal, Saha, and Saptharishi, 2013] and [Fournier et al., 2013]). In particular, using combinatorial design [Kayal et al., 2013] construct an explicit polynomial in VNP that requires depth-4 circuits of size 2^{Omega(n^{1/2}.log(n))} and [Fournier et al., 2013] show that the iterated matrix multiplication polynomial (which is in VP) also requires 2^{Omega(n^{1/2}.log(n))} size depth-4 circuits. In this paper, we identify a simple combinatorial property such that any polynomial f that satisfies this property would achieve a similar depth-4 circuit size lower bound. In particular, it does not matter whether f is in VP or in VNP. As a result, we get a simple unified lower bound analysis for the above mentioned polynomials. Another goal of this paper is to compare our current knowledge of the depth-4 circuit size lower bounds and the determinantal complexity lower bounds. Currently the best known determinantal complexity lower bound is Omega(n^2) for Permanent of a nxn matrix (which is a n^2-variate and degree n polynomial) [Cai, Chen, and Li, 2008]. We prove that the determinantal complexity of the iterated matrix multiplication polynomial is Omega(dn) where d is the number of matrices and n is the dimension of the matrices. So for d=n, we get that the iterated matrix multiplication polynomial achieves the current best known lower bounds in both fronts: depth-4 circuit size and determinantal complexity. Our result also settles the determinantal complexity of the iterated matrix multiplication polynomial to Theta(dn). To the best of our knowledge, a Theta(n) bound for the determinantal complexity for the iterated matrix multiplication polynomial was known only for any constant d>1 [Jansen, 2011].
Cite as

Suryajith Chillara and Partha Mukhopadhyay. Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 239-250, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chillara_et_al:LIPIcs.STACS.2014.239,
  author =	{Chillara, Suryajith and Mukhopadhyay, Partha},
  title =	{{Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{239--250},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.239},
  URN =		{urn:nbn:de:0030-drops-44610},
  doi =		{10.4230/LIPIcs.STACS.2014.239},
  annote =	{Keywords: Arithmetic Circuits, Determinantal Complexity, Depth-4 Lower Bounds}
}
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