7 Search Results for "C., Ramya"


Document
Lower Bounds for Planar Arithmetic Circuits

Authors: C. Ramya and Pratik Shastri

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


Abstract
Arithmetic circuits are a natural well-studied model for computing multivariate polynomials over a field. In this paper, we study planar arithmetic circuits. These are circuits whose underlying graph is planar. In particular, we prove an Ω(nlog n) lower bound on the size of planar arithmetic circuits computing explicit bilinear forms on 2n variables. As a consequence, we get an Ω(nlog n) lower bound on the size of arithmetic formulas and planar algebraic branching programs computing explicit bilinear forms. This is the first such lower bound on the formula complexity of an explicit bilinear form. In the case of read-once planar circuits, we show Ω(n²) size lower bounds for computing explicit bilinear forms. Furthermore, we prove fine separations between the various planar models of computations mentioned above. In addition to this, we look at multi-output planar circuits and show Ω(n^{4/3}) size lower bound for computing an explicit linear transformation on n-variables. For a suitable definition of multi-output formulas, we extend the above result to get an Ω(n²/log n) size lower bound. As a consequence, we demonstrate that there exists an n-variate polynomial computable by n^{1 + o(1)}-sized formulas such that any multi-output planar circuit (resp., multi-output formula) simultaneously computing all its first-order partial derivatives requires size Ω(n^{4/3}) (resp., Ω(n²/log n)). This shows that a statement analogous to that of Baur, Strassen[Walter Baur and Volker Strassen, 1983] does not hold in the case of planar circuits and formulas.

Cite as

C. Ramya and Pratik Shastri. Lower Bounds for Planar Arithmetic Circuits. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 91:1-91:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{ramya_et_al:LIPIcs.ITCS.2024.91,
  author =	{Ramya, C. and Shastri, Pratik},
  title =	{{Lower Bounds for Planar Arithmetic Circuits}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{91:1--91:22},
  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.91},
  URN =		{urn:nbn:de:0030-drops-196199},
  doi =		{10.4230/LIPIcs.ITCS.2024.91},
  annote =	{Keywords: Arithmetic circuit complexity, Planar circuits, Bilinear forms}
}
Document
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field

Authors: V. Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, and C. Ramya

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


Abstract
The identity testing of rational formulas (RIT) in the free skew field efficiently reduces to computing the rank of a matrix whose entries are linear polynomials in noncommuting variables [Hrubeš and Wigderson, 2015]. This rank computation problem has deterministic polynomial-time white-box algorithms [Ankit Garg et al., 2016; Ivanyos et al., 2018] and a randomized polynomial-time algorithm in the black-box setting [Harm Derksen and Visu Makam, 2017]. In this paper, we propose a new approach for efficient derandomization of black-box RIT. Additionally, we obtain results for matrix rank computation over the free skew field and construct efficient linear pencil representations for a new class of rational expressions. More precisely, we show: - Under the hardness assumption that the ABP (algebraic branching program) complexity of every polynomial identity for the k×k matrix algebra is 2^Ω(k) [Andrej Bogdanov and Hoeteck Wee, 2005], we obtain a subexponential-time black-box RIT algorithm for rational formulas of inversion height almost logarithmic in the size of the formula. This can be seen as the first "hardness implies derandomization" type theorem for rational formulas. - We show that the noncommutative rank of any matrix over the free skew field whose entries have small linear pencil representations can be computed in deterministic polynomial time. While an efficient rank computation was known for matrices with noncommutative formulas as entries [Ankit Garg et al., 2020], we obtain the first deterministic polynomial-time algorithms for rank computation of matrices whose entries are noncommutative ABPs or rational formulas. - Motivated by the definition given by Bergman [George M Bergman, 1976], we define a new class of rational functions where a rational function of inversion height at most h is defined as a composition of a noncommutative r-skewed circuit (equivalently an ABP) with inverses of rational functions of this class of inversion height at most h-1 which are also disjoint. We obtain a polynomial-size linear pencil representation for this class which gives a white-box deterministic polynomial-time identity testing algorithm for the class.

Cite as

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)


Copy BibTex To Clipboard

@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-dev.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}
}
Document
If VNP Is Hard, Then so Are Equations for It

Authors: Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)


Abstract
Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP does not have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size. In a recent work of Chatterjee, Kumar, Ramya, Saptharishi and Tengse (FOCS 2020), it was shown that the subclasses of VP and VNP consisting of polynomials with bounded integer coefficients do have equations with small algebraic circuits. Their work left open the possibility that these results could perhaps be extended to all of VP or VNP. The results in this paper show that assuming the hardness of Permanent, at least for VNP, allowing polynomials with large coefficients does indeed incur a significant blow up in the circuit complexity of equations.

Cite as

Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse. If VNP Is Hard, Then so Are Equations for It. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.STACS.2022.44,
  author =	{Kumar, Mrinal and Ramya, C. and Saptharishi, Ramprasad and Tengse, Anamay},
  title =	{{If VNP Is Hard, Then so Are Equations for It}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{44:1--44:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.44},
  URN =		{urn:nbn:de:0030-drops-158547},
  doi =		{10.4230/LIPIcs.STACS.2022.44},
  annote =	{Keywords: Computational Complexity, Algebraic Circuits, Algebraic Natural Proofs}
}
Document
On Finer Separations Between Subclasses of Read-Once Oblivious ABPs

Authors: C. Ramya and Anamay Tengse

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)


Abstract
Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand the landscape of algebraic complexity classes surrounding ROABPs, we study classes of ROABPs based on the algebraic structure of these coefficient matrices. We study connections between polynomials computed by these structured variants of ROABPs and other well-known classes of polynomials (such as depth-three powering circuits, tensor-rank and Waring rank of polynomials). Our main result concerns commutative ROABPs, where all coefficient matrices commute with each other, and diagonal ROABPs, where all the coefficient matrices are just diagonal matrices. In particular, we show a somewhat surprising connection between these models and the model of depth-three powering circuits that is related to the Waring rank of polynomials. We show that if the dimension of partial derivatives captures Waring rank up to polynomial factors, then the model of diagonal ROABPs efficiently simulates the seemingly more expressive model of commutative ROABPs. Further, a commutative ROABP that cannot be efficiently simulated by a diagonal ROABP will give an explicit polynomial that gives a super-polynomial separation between dimension of partial derivatives and Waring rank. Our proof of the above result builds on the results of Marinari, Möller and Mora (1993), and Möller and Stetter (1995), that characterise rings of commuting matrices in terms of polynomials that have small dimension of partial derivatives. The algebraic structure of the coefficient matrices of these ROABPs plays a crucial role in our proofs.

Cite as

C. Ramya and Anamay Tengse. On Finer Separations Between Subclasses of Read-Once Oblivious ABPs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 53:1-53:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ramya_et_al:LIPIcs.STACS.2022.53,
  author =	{Ramya, C. and Tengse, Anamay},
  title =	{{On Finer Separations Between Subclasses of Read-Once Oblivious ABPs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{53:1--53:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.53},
  URN =		{urn:nbn:de:0030-drops-158636},
  doi =		{10.4230/LIPIcs.STACS.2022.53},
  annote =	{Keywords: Algebraic Complexity Theory, Algebraic Branching Programs, Commutative Matrices}
}
Document
Separating ABPs and Some Structured Formulas in the Non-Commutative Setting

Authors: Prerona Chatterjee

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)


Abstract
The motivating question for this work is a long standing open problem, posed by Nisan [Noam Nisan, 1991], regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question remains open, we make some progress towards its resolution. To that effect, we generalise the notion of ordered polynomials in the non-commutative setting (defined by Hrubeš, Wigderson and Yehudayoff [Hrubeš et al., 2011]) to define abecedarian polynomials and models that naturally compute them. Our main contribution is a possible new approach towards resolving the VF_{nc} vs VBP_{nc} question, via lower bounds against abecedarian formulas. In particular, we show the following. There is an explicit n²-variate degree d abecedarian polynomial f_{n,d}(𝐱) such that - f_{n, d}(𝐱) can be computed by an abecedarian ABP of size O(nd); - any abecedarian formula computing f_{n, log n}(𝐱) must have size at least n^{Ω(log log n)}. We also show that a super-polynomial lower bound against abecedarian formulas for f_{log n, n}(𝐱) would separate the powers of formulas and ABPs in the non-commutative setting.

Cite as

Prerona Chatterjee. Separating ABPs and Some Structured Formulas in the Non-Commutative Setting. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{chatterjee:LIPIcs.CCC.2021.7,
  author =	{Chatterjee, Prerona},
  title =	{{Separating ABPs and Some Structured Formulas in the Non-Commutative Setting}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{7:1--7:24},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.7},
  URN =		{urn:nbn:de:0030-drops-142812},
  doi =		{10.4230/LIPIcs.CCC.2021.7},
  annote =	{Keywords: Non-Commutative Formulas, Lower Bound, Separating ABPs and Formulas}
}
Document
Lower Bounds for Multilinear Order-Restricted ABPs

Authors: C. Ramya and B. V. Raghavendra Rao

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
Proving super-polynomial lower bounds on the size of syntactic multilinear Algebraic Branching Programs (smABPs) computing an explicit polynomial is a challenging problem in Algebraic Complexity Theory. The order in which variables in {x_1,...,x_n} appear along any source to sink path in an smABP can be viewed as a permutation in S_n. In this article, we consider the following special classes of smABPs where the order of occurrence of variables along a source to sink path is restricted: 1) Strict circular-interval ABPs: For every sub-program the index set of variables occurring in it is contained in some circular interval of {1,..., n}. 2) L-ordered ABPs: There is a set of L permutations (orders) of variables such that every source to sink path in the smABP reads variables in one of these L orders, where L <=2^{n^{1/2 -epsilon}} for some epsilon>0. We prove exponential (i.e., 2^{Omega(n^delta)}, delta>0) lower bounds on the size of above models computing an explicit multilinear 2n-variate polynomial in VP. As a main ingredient in our lower bounds, we show that any polynomial that can be computed by an smABP of size S, can be written as a sum of O(S) many multilinear polynomials where each summand is a product of two polynomials in at most 2n/3 variables, computable by smABPs. As a corollary, we show that any size S syntactic multilinear ABP can be transformed into a size S^{O(sqrt{n})} depth four syntactic multilinear Sigma Pi Sigma Pi circuit where the bottom Sigma gates compute polynomials on at most O(sqrt{n}) variables. Finally, we compare the above models with other standard models for computing multilinear polynomials.

Cite as

C. Ramya and B. V. Raghavendra Rao. Lower Bounds for Multilinear Order-Restricted ABPs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{ramya_et_al:LIPIcs.MFCS.2019.52,
  author =	{Ramya, C. and Rao, B. V. Raghavendra},
  title =	{{Lower Bounds for Multilinear Order-Restricted ABPs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.52},
  URN =		{urn:nbn:de:0030-drops-109963},
  doi =		{10.4230/LIPIcs.MFCS.2019.52},
  annote =	{Keywords: Computational complexity, Algebraic complexity theory, Polynomials}
}
Document
Sum of Products of Read-Once Formulas

Authors: Ramya C. and B. V. Raghavendra Rao

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)


Abstract
We study limitations of polynomials computed by depth two circuits built over read-once formulas (ROFs). In particular, 1. We prove an exponential lower bound for the sum of ROFs computing the 2n-variate polynomial in VP defined by Raz and Yehudayoff [CC,2009]. 2. We obtain an exponential lower bound on the size of arithmetic circuits computing sum of products of restricted ROFs of unbounded depth computing the permanent of an n by n matrix. The restriction is on the number of variables with + gates as a parent in a proper sub formula of the ROF to be bounded by sqrt(n). Additionally, we restrict the product fan in to be bounded by a sub linear function. This proves an exponential lower bound for a subclass of possibly non-multilinear formulas of unbounded depth computing the permanent polynomial. 3. We also show an exponential lower bound for the above model against a polynomial in VP. 4. Finally we observe that the techniques developed yield an exponential lower bound on the size of sums of products of syntactically multilinear arithmetic circuits computing a product of variable disjoint linear forms where the bottom sum gate and product gates at the second level have fan in bounded by a sub linear function. Our proof techniques are built on the measure developed by Kumar et al.[ICALP 2013] and are based on a non-trivial analysis of ROFs under random partitions. Further, our results exhibit strengths and provide more insight into the lower bound techniques introduced by Raz [STOC 2004].

Cite as

Ramya C. and B. V. Raghavendra Rao. Sum of Products of Read-Once Formulas. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{c._et_al:LIPIcs.FSTTCS.2016.39,
  author =	{C., Ramya and Rao, B. V. Raghavendra},
  title =	{{Sum of Products of Read-Once Formulas}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.39},
  URN =		{urn:nbn:de:0030-drops-68741},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.39},
  annote =	{Keywords: Arithmetic Circuits, Permanent, Computational Complexity, Algebraic Complexity Theory}
}
  • Refine by Author
  • 5 Ramya, C.
  • 2 Rao, B. V. Raghavendra
  • 2 Tengse, Anamay
  • 1 Arvind, V.
  • 1 C., Ramya
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Circuit complexity

  • Refine by Keyword
  • 2 Algebraic Complexity Theory
  • 2 Computational Complexity
  • 1 Algebraic Branching Programs
  • 1 Algebraic Circuits
  • 1 Algebraic Complexity
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2022
  • 1 2016
  • 1 2019
  • 1 2021
  • 1 2023
  • Show More...

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