4 Search Results for "Thankey, Bhargav"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.12
Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization

Authors: Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, and Bhargav Thankey

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
A recent breakthrough work of Limaye, Srinivasan and Tavenas [Nutan Limaye et al., 2021] proved superpolynomial lower bounds for low-depth arithmetic circuits via a "hardness escalation" approach: they proved lower bounds for low-depth set-multilinear circuits and then lifted the bounds to low-depth general circuits. In this work, we prove superpolynomial lower bounds for low-depth circuits by bypassing the hardness escalation, i.e., the set-multilinearization, step. As set-multilinearization comes with an exponential blow-up in circuit size, our direct proof opens up the possibility of proving an exponential lower bound for low-depth homogeneous circuits by evading a crucial bottleneck. Our bounds hold for the iterated matrix multiplication and the Nisan-Wigderson design polynomials. We also define a subclass of unrestricted depth homogeneous formulas which we call unique parse tree (UPT) formulas, and prove superpolynomial lower bounds for these. This significantly generalizes the superpolynomial lower bounds for regular formulas [Neeraj Kayal et al., 2014; Hervé Fournier et al., 2015].
Cite as

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, and Bhargav Thankey. Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{amireddy_et_al:LIPIcs.ICALP.2023.12,
  author =	{Amireddy, Prashanth and Garg, Ankit and Kayal, Neeraj and Saha, Chandan and Thankey, Bhargav},
  title =	{{Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel 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.2023.12},
  URN =		{urn:nbn:de:0030-drops-180642},
  doi =		{10.4230/LIPIcs.ICALP.2023.12},
  annote =	{Keywords: arithmetic circuits, low-depth circuits, lower bounds, shifted partials}
}
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}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.50
Hitting Sets for Orbits of Circuit Classes and Polynomial Families

Authors: Chandan Saha and Bhargav Thankey

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(𝐱) over a field 𝔽 is the set {f(A𝐱+𝐛) : A ∈ GL(n,𝔽) and 𝐛 ∈ 𝔽ⁿ}. In this paper, we initiate the study of explicit hitting sets for the orbits of polynomials computable by several natural and well-studied circuit classes and polynomial families. In particular, we give quasi-polynomial time hitting sets for the orbits of: 1) Low-individual-degree polynomials computable by commutative ROABPs. This implies quasi-polynomial time hitting sets for the orbits of the elementary symmetric polynomials. 2) Multilinear polynomials computable by constant-width ROABPs. This implies a quasi-polynomial time hitting set for the orbits of the family {IMM_{3,d}}_{d ∈ ℕ}, which is complete for arithmetic formulas. 3) Polynomials computable by constant-depth, constant-occur formulas. This implies quasi-polynomial time hitting sets for the orbits of multilinear depth-4 circuits with constant top fan-in, and also polynomial-time hitting sets for the orbits of the power symmetric and the sum-product polynomials. 4) Polynomials computable by occur-once formulas.
Cite as

Chandan Saha and Bhargav Thankey. Hitting Sets for Orbits of Circuit Classes and Polynomial Families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 50:1-50:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{saha_et_al:LIPIcs.APPROX/RANDOM.2021.50,
  author =	{Saha, Chandan and Thankey, Bhargav},
  title =	{{Hitting Sets for Orbits of Circuit Classes and Polynomial Families}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{50:1--50:26},
  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.50},
  URN =		{urn:nbn:de:0030-drops-147433},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.50},
  annote =	{Keywords: Hitting Sets, Orbits, ROABPs, Rank Concentration}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.23
A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

Authors: Nikhil Gupta, Chandan Saha, and Bhargav Thankey

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We show an Ω̃(n^2.5) lower bound for general depth four arithmetic circuits computing an explicit n-variate degree-Θ(n) multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey [Amir Shpilka and Amir Yehudayoff, 2010], no super-quadratic lower bound was known for depth four circuits over fields of characteristic ≠ 2 before this work. The previous best lower bound is Ω̃(n^1.5) [Abhijat Sharma, 2017], which is a slight quantitative improvement over the roughly Ω(n^1.33) bound obtained by invoking the super-linear lower bound for constant depth circuits in [Ran Raz, 2010; Victor Shoup and Roman Smolensky, 1997]. Our lower bound proof follows the approach of the almost cubic lower bound for depth three circuits in [Neeraj Kayal et al., 2016] by replacing the shifted partials measure with a suitable variant of the projected shifted partials measure, but it differs from [Neeraj Kayal et al., 2016]’s proof at a crucial step - namely, the way "heavy" product gates are handled. Loosely speaking, a heavy product gate has a relatively high fan-in. Product gates of a depth three circuit compute products of affine forms, and so, it is easy to prune Θ(n) many heavy product gates by projecting the circuit to a low-dimensional affine subspace [Neeraj Kayal et al., 2016; Amir Shpilka and Avi Wigderson, 2001]. However, in a depth four circuit, the second (from the top) layer of product gates compute products of polynomials having arbitrary degree, and hence it was not clear how to prune such heavy product gates from the circuit. We show that heavy product gates can also be eliminated from a depth four circuit by projecting the circuit to a low-dimensional affine subspace, unless the heavy gates together account for Ω̃(n^2.5) size. This part of our argument is inspired by a well-known greedy approximation algorithm for the weighted set-cover problem.
Cite as

Nikhil Gupta, Chandan Saha, and Bhargav Thankey. A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 23:1-23:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.CCC.2020.23,
  author =	{Gupta, Nikhil and Saha, Chandan and Thankey, Bhargav},
  title =	{{A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{23:1--23:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.23},
  URN =		{urn:nbn:de:0030-drops-125757},
  doi =		{10.4230/LIPIcs.CCC.2020.23},
  annote =	{Keywords: depth four arithmetic circuits, Projected Shifted Partials, super-quadratic lower bound}
}
  • Refine by Author
  • 3 Saha, Chandan
  • 3 Thankey, Bhargav
  • 1 Amireddy, Prashanth
  • 1 Bhargava, Vishwas
  • 1 Garg, Ankit
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Algebraic complexity theory
  • 1 Computing methodologies → Algebraic algorithms

  • Refine by Keyword
  • 2 Orbits
  • 1 Hitting Set
  • 1 Hitting Sets
  • 1 Low Cone Concentration
  • 1 PIT
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2021
  • 1 2020
  • 1 2023

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