4 Search Results for "Sinha, Gaurav"

Document
DOI: 10.4230/LIPIcs.CCC.2025.21
Reconstruction of Depth 3 Arithmetic Circuits with Top Fan-In 3

Authors: Shubhangi Saraf and Devansh Shringi

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
In this paper, we give the first subexponential (and in fact quasi-polynomial time) reconstruction algorithm for depth 3 circuits of top fan-in 3 (ΣΠΣ(3) circuits) over the fields ℝ and C. Concretely, we show that given blackbox access to an n-variate polynomial f computed by a ΣΠΣ(3) circuit of size s, there is a randomized algorithm that runs in time quasi-poly(n,s) and outputs a generalized ΣΠΣ(3) circuit computing f. The size s includes the bit complexity of coefficients appearing in the circuit. Depth 3 circuits of constant fan-in (ΣΠΣ(k) circuits) and closely related models have been extensively studied in the context of polynomial identity testing (PIT). The study of PIT for these models led to an understanding of the structure of identically zero ΣΠΣ(3) circuits and ΣΠΣ(k) circuits using some very elegant connections to discrete geometry, specifically the Sylvester-Gallai Theorem, and colorful and high dimensional variants of them. Despite a lot of progress on PIT for ΣΠΣ(k) circuits and more recently on PIT for depth 4 circuits of bounded top and bottom fan-in, reconstruction algorithms for ΣΠΣ(k) circuits has proven to be extremely challenging. In this paper, we build upon the structural results for identically zero ΣΠΣ(3) circuits that bound their rank, and prove stronger structural properties of ΣΠΣ(3) circuits (again using connections to discrete geometry). One such result is a bound on the number of codimension 3 subspaces on which a polynomial computed by an ΣΠΣ(3) circuit can vanish on. Armed with the new structural results, we provide the first reconstruction algorithms for ΣΠΣ(3) circuits over ℝ and C. Our work extends the work of [Sinha, CCC 2016] who provided a reconstruction algorithm for ΣΠΣ(2) circuits over ℝ and C as well as the works of [Shpilka, STOC 2007] who provided a reconstruction algorithms for ΣΠΣ(2) circuits in the setting of small finite fields, and [Karnin-Shpilka, CCC 2009] who provided reconstruction algorithms for ΣΠΣ(k) circuits in the setting of small finite fields.
Cite as

Shubhangi Saraf and Devansh Shringi. Reconstruction of Depth 3 Arithmetic Circuits with Top Fan-In 3. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{saraf_et_al:LIPIcs.CCC.2025.21,
  author =	{Saraf, Shubhangi and Shringi, Devansh},
  title =	{{Reconstruction of Depth 3 Arithmetic Circuits with Top Fan-In 3}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.21},
  URN =		{urn:nbn:de:0030-drops-237151},
  doi =		{10.4230/LIPIcs.CCC.2025.21},
  annote =	{Keywords: arithmetic circuits, learning, reconstruction}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.118
Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two

Authors: Gaurav Sinha

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
In this paper we develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials over finite fields, computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that output gate is an addition gate with in-degree two. Such circuits naturally compute polynomials of the form G×(T₁ + T₂), where G,T₁,T₂ are product of affine forms computed at the first layer in the circuit, and polynomials T₁,T₂ have no common factors. Rank of such a circuit is defined to be the dimension of vector space spanned by all affine factors of T₁ and T₂. For any polynomial f computable by such a circuit, rank(f) is defined to be the minimum rank of any such circuit computing it. Our work develops randomized reconstruction algorithms which take as input black-box access to a polynomial f (over finite field 𝔽), computable by such a circuit. Here are the results. - [Low rank]: When 5 ≤ rank(f) = O(log³ d), it runs in time (nd^{log³d}log |𝔽|)^{O(1)}, and, with high probability, outputs a depth three circuit computing f, with top addition gate having in-degree ≤ d^{rank(f)}. - [High rank]: When rank(f) = Ω(log³ d), it runs in time (ndlog |𝔽|)^{O(1)}, and, with high probability, outputs a depth three circuit computing f, with top addition gate having in-degree two. Prior to our work, black-box reconstruction for this circuit class was addressed in [Amir Shpilka, 2007; Karnin and Shpilka, 2009; Sinha, 2016]. Reconstruction algorithm in [Amir Shpilka, 2007] runs in time quasi-polynomial in n,d,|𝔽| and that in [Karnin and Shpilka, 2009] is quasi-polynomial in d,|𝔽|. Algorithm in [Sinha, 2016] works only for polynomials over characteristic zero fields. Thus, ours is the first blackbox reconstruction algorithm for this class of circuits that runs in time polynomial in log |𝔽|. This problem has been mentioned as an open problem in [Ankit Gupta et al., 2012] (STOC 2012). In the high rank case, our algorithm runs in (ndlog|𝔽|)^{O(1)} time, thereby significantly improving the existing algorithms in [Amir Shpilka, 2007; Karnin and Shpilka, 2009].
Cite as

Gaurav Sinha. Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 118:1-118:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{sinha:LIPIcs.ITCS.2022.118,
  author =	{Sinha, Gaurav},
  title =	{{Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{118:1--118:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.118},
  URN =		{urn:nbn:de:0030-drops-157143},
  doi =		{10.4230/LIPIcs.ITCS.2022.118},
  annote =	{Keywords: Arithmetic Circuits, Circuit Reconstruction}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.59
The Landform Reference Ontology (LFRO): A Foundation for Exploring Linguistic and Geospatial Conceptualization of Landforms (Short Paper)

Authors: Gaurav Sinha, Samantha T. Arundel, Torsten Hahmann, E. Lynn Usery, Kathleen Stewart, and David M. Mark

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
The landform reference ontology (LFRO) formalizes ontological distinctions underlying naïve geographic cognition and reasoning about landforms. The LFRO taxonomy is currently based only on form-based distinctions. In this significantly revised version, several new categories have been added to explicate ontological distinctions related to material-spatial dependence and physical support. Nuances of common natural language landform terms and implications for their mapping are discussed.
Cite as

Gaurav Sinha, Samantha T. Arundel, Torsten Hahmann, E. Lynn Usery, Kathleen Stewart, and David M. Mark. The Landform Reference Ontology (LFRO): A Foundation for Exploring Linguistic and Geospatial Conceptualization of Landforms (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 59:1-59:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sinha_et_al:LIPIcs.GISCIENCE.2018.59,
  author =	{Sinha, Gaurav and Arundel, Samantha T. and Hahmann, Torsten and Usery, E. Lynn and Stewart, Kathleen and Mark, David M.},
  title =	{{The Landform Reference Ontology (LFRO): A Foundation for Exploring Linguistic and Geospatial Conceptualization of Landforms}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{59:1--59:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.59},
  URN =		{urn:nbn:de:0030-drops-93873},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.59},
  annote =	{Keywords: landform, reference ontology, terrain reasoning, dependence, support}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.31
Reconstruction of Real Depth-3 Circuits with Top Fan-In 2

Authors: Gaurav Sinha

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
Reconstruction of arithmetic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing SigmaPiSigma(2) circuits over F (char(F)=0), i.e. depth-3 circuits with fan-in 2 at the top addition gate and having coefficients from a field of characteristic 0. The algorithm needs only a blackbox query access to the polynomial f in F[x_1,..., x_n] of degree d, computable by a SigmaPiSigma(2) circuit C. In addition, we assume that the "simple rank" of this polynomial (essential number of variables after removing the gcd of the two multiplication gates) is bigger than a fixed constant. Our algorithm runs in time poly(n,d) and returns an equivalent SigmaPiSigma(2) circuit (with high probability). The problem of reconstructing SigmaPiSigma(2) circuits over finite fields was first proposed by Shpilka [Shpilka, STOC 2007]. The generalization to SigmaPiSigma(k) circuits, k = O(1) (over finite fields) was addressed by Karnin and Shpilka in [Karnin/Shpilka, CCC 2015]. The techniques in these previous involve iterating over all objects of certain kinds over the ambient field and thus the running time depends on the size of the field F. Their reconstruction algorithm uses lower bounds on the lengths of Linear Locally Decodable Codes with 2 queries. In our settings, such ideas immediately pose a problem and we need new ideas to handle the case of the characteristic 0 field F. Our main techniques are based on the use of Quantitative Sylvester Gallai Theorems from the work of Barak et al. [Barak/Dvir/Wigderson/Yehudayoff, STOC 2011] to find a small collection of "nice" subspaces to project onto. The heart of our paper lies in subtle applications of the Quantitative Sylvester Gallai theorems to prove why projections w.r.t. the "nice" subspaces can be "glued". We also use Brill's Equations from [Gelfand/Kapranov/Zelevinsky, 1994] to construct a small set of candidate linear forms (containing linear forms from both gates). Another important technique which comes very handy is the polynomial time randomized algorithm for factoring multivariate polynomials given by Kaltofen [Kaltofen/Trager, J. Symb. Comp. 1990].
Cite as

Gaurav Sinha. Reconstruction of Real Depth-3 Circuits with Top Fan-In 2. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 31:1-31:53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{sinha:LIPIcs.CCC.2016.31,
  author =	{Sinha, Gaurav},
  title =	{{Reconstruction of Real Depth-3 Circuits with Top Fan-In 2}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{31:1--31:53},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.31},
  URN =		{urn:nbn:de:0030-drops-58545},
  doi =		{10.4230/LIPIcs.CCC.2016.31},
  annote =	{Keywords: Reconstruction, SigmaPiSigma(2), Sylvester-Gallai, Brill's Equations}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2022
  • 1 2018
  • 1 2016

  • Refine by Author
  • 3 Sinha, Gaurav
  • 1 Arundel, Samantha T.
  • 1 Hahmann, Torsten
  • 1 Mark, David M.
  • 1 Saraf, Shubhangi
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Algebraic complexity theory
  • 1 Information systems → Ontologies
  • 1 Theory of computation → Circuit complexity

  • Refine by Keyword
  • 1 Arithmetic Circuits
  • 1 Brill's Equations
  • 1 Circuit Reconstruction
  • 1 Reconstruction
  • 1 SigmaPiSigma(2)
  • Show More...

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