14 Search Results for "Ghosh, Sumanta"

Document
DOI: 10.4230/LIPIcs.STACS.2026.28
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank

Authors: Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Arina Smirnova

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform (algorithm) lower bounds and nonuniform (circuit) lower bounds in restricted circuit models. About a decade ago, Williams (STOC 2010) showed how to derive nonuniform lower bounds from uniform upper bounds: roughly, by designing a fast algorithm for checking satisfiability of circuits, one gets a lower bound for this circuit class. Since then, a number of results of this kind have been proved. For example, Jahanjou et al. (ICALP 2015) and Carmosino et al. (ITCS 2016) proved that if NSETH fails, then E^{NP} has series-parallel circuit size ω(n). One can also derive nonuniform lower bounds from nondeterministic uniform lower bounds. Perhaps the most well-known example is the Karp-Lipton theorem (STOC 1980): if Σ₂ ≠ Π₂, then NP ⊄ P/poly. Some recent examples include the following. Nederlof (STOC 2020) proved a lower bound on the matrix multiplication tensor rank under an assumption that TSP cannot be solved faster than in 2ⁿ time. Belova et al. (SODA 2024) proved that there exists an explicit polynomial family of arithmetic circuit size Ω(n^{δ}), for any δ > 0, assuming that MAX-3-SAT cannot be solved faster than in 2ⁿ nondeterministic time. Williams (FOCS 2024) proved an exponential lower bound for ETHR ∘ ETHR circuits under the Orthogonal Vectors conjecture. Whereas all the lower bounds above are proved under strong assumptions that might eventually be refuted, the revealed connections are of great interest and may still give further insights: one may be able to weaken the used assumptions or to construct generators from other fine-grained reductions. In this paper, we continue developing this line of research and show how uniform nondeterministic lower bounds can be used to construct generators of various types of combinatorial objects that are notoriously hard to analyze: Boolean functions of high circuit size, matrices of high rigidity, and tensors of high rank. Specifically, we prove the following. - If, for some ε and k, k-SAT cannot be solved in input-oblivious co-nondeterministic time O(2^{(1/2+ε)n}), then there exists a monotone Boolean function family in coNP of monotone circuit size 2^{Ω(n / log n)}. Combining this with the result above, we get win-win circuit lower bounds: either E^{NP{}} requires series-parallel circuits of size ω(n) or coNP requires monotone circuits of size 2^{Ω(n / log n)}. - If, for all ε > 0, MAX-3-SAT cannot be solved in co-nondeterministic time O(2^{(1 - ε)n}), then there exist small families of matrices with rigidity exceeding the best known constructions as well as small families of three-dimensional tensors of rank n^{1+Δ}, for some Δ > 0.
Cite as

Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Arina Smirnova. Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chukhin_et_al:LIPIcs.STACS.2026.28,
  author =	{Chukhin, Nikolai and Kulikov, Alexander S. and Mihajlin, Ivan and Smirnova, Arina},
  title =	{{Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{28:1--28:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.28},
  URN =		{urn:nbn:de:0030-drops-255177},
  doi =		{10.4230/LIPIcs.STACS.2026.28},
  annote =	{Keywords: computational complexity, circuit complexity, lower bounds, conditional lower bounds, monotone circuits, matrix rigidity, tensor rank, arithmetic circuits, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.49
Debordering Closure Results in Determinantal and Pfaffian Ideals

Authors: Anakin Dey and Zeyu Guo

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
One important question in algebraic complexity is understanding the complexity of polynomial ideals (Grochow, Bulletin of EATCS 131, 2020). Andrews and Forbes (STOC 2022) studied the determinantal ideals I^{det}_{n,m,r} generated by the r× r minors of n× m matrices. Over fields of characteristic zero or of sufficiently large characteristic, they showed that for any nonzero f ∈ I^{det}_{n,m,r}, the determinant of a t × t matrix of variables with t = Θ{r^{1/3}} is approximately computed by a constant-depth, polynomial-size f-oracle algebraic circuit, in the sense that the determinant lies in the border of such circuits. An analogous result was also obtained for Pfaffians in the same paper. In this work, we deborder the result of Andrews and Forbes by showing that when f has polynomial degree, the determinant is in fact exactly computed by a constant-depth, polynomial-size f-oracle algebraic circuit. We further establish an analogous result for Pfaffian ideals. Our results are established using the isolation lemma, combined with a careful analysis of straightening-law expansions of polynomials in determinantal and Pfaffian ideals.
Cite as

Anakin Dey and Zeyu Guo. Debordering Closure Results in Determinantal and Pfaffian Ideals. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 49:1-49:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ITCS.2026.49,
  author =	{Dey, Anakin and Guo, Zeyu},
  title =	{{Debordering Closure Results in Determinantal and Pfaffian Ideals}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{49:1--49:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.49},
  URN =		{urn:nbn:de:0030-drops-253363},
  doi =		{10.4230/LIPIcs.ITCS.2026.49},
  annote =	{Keywords: Algebraic circuit complexity, Isolation lemma, Debordering}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.9
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

Authors: Robert Andrews, Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure under factoring: There is a sequence of explicit polynomials (f_n(x₁,…, x_n))_n that have poly(n)-sized roABPs such that some irreducible factor of f_n requires roABPs of superpolynomial size in any order. - Non-closure under powering: There is a sequence of polynomials (f_n(x₁,…, x_n))_n with poly(n)-sized roABPs such that any super-constant power of f_n does not have roABPs of polynomial size in any order (and f_nⁿ requires exponential size in any order). - Non-closure under symmetric operations: There are symmetric polynomials (f_n(e₁,…, e_n))_n that have roABPs of polynomial size such that f_n(x₁,…, x_n) do not have roABPs of subexponential size. (Here, e₁,…, e_n denote the elementary symmetric polynomials in n variables.) These results should be viewed in light of known results on models such as algebraic circuits, (general) algebraic branching programs, formulas and constant-depth circuits, all of which are known to be closed under these operations. To prove non-closure under factoring, we construct hard polynomials based on expander graphs using gadgets that lift their hardness from sparse polynomials to roABPs. For symmetric compositions, we show that the circulant polynomial requires roABPs of exponential size in every variable order.
Cite as

Robert Andrews, Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. On Closure Properties of Read-Once Oblivious Algebraic Branching Programs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{andrews_et_al:LIPIcs.ITCS.2026.9,
  author =	{Andrews, Robert and Armand, Jules and Dwivedi, Prateek and Hansen, Magnus Rahbek Dalgaard and Limaye, Nutan and Srinivasan, Srikanth and Tavenas, S\'{e}bastien},
  title =	{{On Closure Properties of Read-Once Oblivious Algebraic Branching Programs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.9},
  URN =		{urn:nbn:de:0030-drops-252964},
  doi =		{10.4230/LIPIcs.ITCS.2026.9},
  annote =	{Keywords: Factoring, Closure Properties, Sparsity Bounds, Symmetric Polynomials, roABP, Expander Graphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.4
Pseudodeterministic Algorithms for Minimum Cut Problems

Authors: Aryan Agarwala and Nithin Varma

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In this paper we present efficient pseudodeterministic algorithms for both the global minimum cut and minimum s-t cut problems. The running time of our algorithm for the global minimum cut problem is asymptotically better than the fastest sequential deterministic global minimum cut algorithm (Henzinger, Li, Rao, Wang; SODA 2024). Furthermore, we implement our algorithm in streaming, PRAM, and cut-query models, where no efficient deterministic global minimum cut algorithms are known.
Cite as

Aryan Agarwala and Nithin Varma. Pseudodeterministic Algorithms for Minimum Cut Problems. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwala_et_al:LIPIcs.ITCS.2026.4,
  author =	{Agarwala, Aryan and Varma, Nithin},
  title =	{{Pseudodeterministic Algorithms for Minimum Cut Problems}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.4},
  URN =		{urn:nbn:de:0030-drops-252917},
  doi =		{10.4230/LIPIcs.ITCS.2026.4},
  annote =	{Keywords: Minimum Cut, Pseudodeterministic Algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.49
On the Hardness of Order Finding and Equivalence Testing for ROABPs

Authors: C. Ramya and Pratik Shastri

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
The complexity of representing a polynomial by a Read-Once Oblivious Algebraic Branching Program (ROABP) is highly dependent on the chosen variable ordering. Bhargava et al. [Bhargava et al., 2024] prove that finding the optimal ordering is NP-hard, and provide some evidence (based on the Small Set Expansion hypothesis) that it is also hard to approximate the optimal ROABP width. In another work, Baraskar et al. [Baraskar et al., 2024] show that it is NP-hard to test whether a polynomial is in the GL_n orbit of a polynomial of sparsity at most s. Building upon these works, we show the following results: first, we prove that approximating the minimum ROABP width up to any constant factor is NP-hard, when the input is presented as a circuit. This removes the reliance on stronger conjectures in the previous work [Bhargava et al., 2024]. Second, we show that testing if an input polynomial given in the sparse representation is in the affine GL_n orbit of a width-w ROABP is NP-hard. Furthermore, we show that over fields of characteristic 0, the problem is NP-hard even when the input polynomial is homogeneous. This provides the first NP-hardness results for membership testing for a dense subclass of polynomial sized algebraic branching programs (VBP). Finally, we locate the source of hardness for the order finding problem at the lowest possible non-trivial degree, proving that the problem is NP-hard even for quadratic forms.
Cite as

C. Ramya and Pratik Shastri. On the Hardness of Order Finding and Equivalence Testing for ROABPs. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ramya_et_al:LIPIcs.FSTTCS.2025.49,
  author =	{Ramya, C. and Shastri, Pratik},
  title =	{{On the Hardness of Order Finding and Equivalence Testing for ROABPs}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{49:1--49:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.49},
  URN =		{urn:nbn:de:0030-drops-251296},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.49},
  annote =	{Keywords: ROABP, Order Finding, Equivalence Testing, NP-hardness, Hardness of Approximation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.89
A Simple Algorithm for Trimmed Multipoint Evaluation

Authors: Nick Fischer, Melvin Kallmayer, and Leo Wennmann

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Evaluating a polynomial on a set of points is a fundamental task in computer algebra. In this work, we revisit a particular variant called trimmed multipoint evaluation: given an n-variate polynomial with bounded individual degree d and total degree D, the goal is to evaluate it on a natural class of input points. This problem arises as a key subroutine in recent algorithmic results [Dinur; SODA '21], [Dell, Haak, Kallmayer, Wennmann; SODA '25]. It is known that trimmed multipoint evaluation can be solved in near-linear time [van der Hoeven, Schost; AAECC '13] by a clever yet somewhat involved algorithm. We give a simple recursive algorithm that avoids heavy computer-algebraic machinery, and can be readily understood by researchers without specialized background.
Cite as

Nick Fischer, Melvin Kallmayer, and Leo Wennmann. A Simple Algorithm for Trimmed Multipoint Evaluation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 89:1-89:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.ESA.2025.89,
  author =	{Fischer, Nick and Kallmayer, Melvin and Wennmann, Leo},
  title =	{{A Simple Algorithm for Trimmed Multipoint Evaluation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{89:1--89:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.89},
  URN =		{urn:nbn:de:0030-drops-245574},
  doi =		{10.4230/LIPIcs.ESA.2025.89},
  annote =	{Keywords: Algebraic Algorithms, Multipoint Evaluation, Interpolation, LU Decomposition}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.15
Algebraic Pseudorandomness in VNC⁰

Authors: Robert Andrews

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

Abstract
We study the arithmetic complexity of hitting set generators, which are pseudorandom objects used for derandomization of the polynomial identity testing problem. We give new explicit constructions of hitting set generators whose outputs are computable in VNC⁰, i.e., can be computed by arithmetic formulas of constant size. Unconditionally, we construct a VNC⁰-computable generator that hits arithmetic circuits of constant depth and polynomial size. We also give conditional constructions, under strong but plausible hardness assumptions, of VNC⁰-computable generators that hit arithmetic formulas and arithmetic branching programs of polynomial size, respectively. As a corollary of our constructions, we derive lower bounds for subsystems of the Geometric Ideal Proof System of Grochow and Pitassi. Constructions of such generators are implicit in prior work of Kayal on lower bounds for the degree of annihilating polynomials. Our main contribution is a construction whose correctness relies on circuit complexity lower bounds rather than degree lower bounds.
Cite as

Robert Andrews. Algebraic Pseudorandomness in VNC⁰. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{andrews:LIPIcs.CCC.2025.15,
  author =	{Andrews, Robert},
  title =	{{Algebraic Pseudorandomness in VNC⁰}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{15:1--15:15},
  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.15},
  URN =		{urn:nbn:de:0030-drops-237092},
  doi =		{10.4230/LIPIcs.CCC.2025.15},
  annote =	{Keywords: Polynomial identity testing, Algebraic circuits, Ideal Proof System}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.2
Border Complexity of Symbolic Determinant Under Rank One Restriction

Authors: Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form A_0 + ∑_{i=1}^n A_i x_i where the size of each A_i is polynomial in the number of variables (equivalently, computable by polynomial-sized algebraic branching programs (ABP)). A major open problem in geometric complexity theory (GCT) is to determine whether VBP is closed under approximation i.e. whether VBP = VBP^ ̅. The power of approximation is well understood for some restricted models of computation, e.g. the class of depth-two circuits, read-once oblivious ABPs (ROABP), monotone ABPs, depth-three circuits of bounded top fan-in, and width-two ABPs. The former three classes are known to be closed under approximation [Markus Bläser et al., 2020], whereas the approximative closure of the last one captures the entire class of polynomial families computable by polynomial-sized formulas [Bringmann et al., 2017]. In this work, we consider the subclass of VBP computed by the determinant of a symbolic matrix of the form A_0 + ∑_{i=1}^n A_i x_i where for each 1 ≤ i ≤ n, A_i is of rank one. This class has been studied extensively [Edmonds, 1968; Jack Edmonds, 1979; Murota, 1993] and efficient identity testing algorithms are known for it [Lovász, 1989; Rohit Gurjar and Thomas Thierauf, 2020]. We show that this class is closed under approximation. In the language of algebraic geometry, we show that the set obtained by taking coordinatewise products of pairs of points from (the Plücker embedding of) a Grassmannian variety is closed.
Cite as

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj. Border Complexity of Symbolic Determinant Under Rank One Restriction. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.CCC.2023.2,
  author =	{Chatterjee, Abhranil and Ghosh, Sumanta and Gurjar, Rohit and Raj, Roshan},
  title =	{{Border Complexity of Symbolic Determinant Under Rank One Restriction}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.2},
  URN =		{urn:nbn:de:0030-drops-182721},
  doi =		{10.4230/LIPIcs.CCC.2023.2},
  annote =	{Keywords: Border Complexity, Symbolic Determinant, Valuated Matroid}
}
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.41
Matroid Intersection: A Pseudo-Deterministic Parallel Reduction from Search to Weighted-Decision

Authors: Sumanta Ghosh and Rohit Gurjar

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

Abstract
We study the matroid intersection problem from the parallel complexity perspective. Given two matroids over the same ground set, the problem asks to decide whether they have a common base and its search version asks to find a common base, if one exists. Another widely studied variant is the weighted decision version where with the two matroids, we are given small weights on the ground set elements and a target weight W, and the question is to decide whether there is a common base of weight at least W. From the perspective of parallel complexity, the relation between the search and the decision versions is not well understood. We make a significant progress on this question by giving a pseudo-deterministic parallel (NC) algorithm for the search version that uses an oracle access to the weighted decision. The notion of pseudo-deterministic NC was recently introduced by Goldwasser and Grossman [Shafi Goldwasser and Ofer Grossman, 2017], which is a relaxation of NC. A pseudo-deterministic NC algorithm for a search problem is a randomized NC algorithm that, for a given input, outputs a fixed solution with high probability. In case the given matroids are linearly representable, our result implies a pseudo-deterministic NC algorithm (without the weighted decision oracle). This resolves an open question posed by Anari and Vazirani [Nima Anari and Vijay V. Vazirani, 2020].
Cite as

Sumanta Ghosh and Rohit Gurjar. Matroid Intersection: A Pseudo-Deterministic Parallel Reduction from Search to Weighted-Decision. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.APPROX/RANDOM.2021.41,
  author =	{Ghosh, Sumanta and Gurjar, Rohit},
  title =	{{Matroid Intersection: A Pseudo-Deterministic Parallel Reduction from Search to Weighted-Decision}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{41:1--41:16},
  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.41},
  URN =		{urn:nbn:de:0030-drops-147342},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.41},
  annote =	{Keywords: Linear Matroid, Matroid Intersection, Parallel Complexity, Pseudo-deterministic NC}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.4
Improved Explicit Hitting-Sets for ROABPs

Authors: Zeyu Guo and Rohit Gurjar

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

Abstract
We give improved explicit constructions of hitting-sets for read-once oblivious algebraic branching programs (ROABPs) and related models. For ROABPs in an unknown variable order, our hitting-set has size polynomial in (nr)^{(log n)/(max{1, log log n-log log r})}d over a field whose characteristic is zero or large enough, where n is the number of variables, d is the individual degree, and r is the width of the ROABP. A similar improved construction works over fields of arbitrary characteristic with a weaker size bound. Based on a result of Bisht and Saxena (2020), we also give an improved explicit construction of hitting-sets for sum of several ROABPs. In particular, when the characteristic of the field is zero or large enough, we give polynomial-size explicit hitting-sets for sum of constantly many log-variate ROABPs of width r = 2^{O(log d/log log d)}. Finally, we give improved explicit hitting-sets for polynomials computable by width-r ROABPs in any variable order, also known as any-order ROABPs. Our hitting-set has polynomial size for width r up to 2^{O(log(nd)/log log(nd))} or 2^{O(log^{1-ε} (nd))}, depending on the characteristic of the field. Previously, explicit hitting-sets of polynomial size are unknown for r = ω(1).
Cite as

Zeyu Guo and Rohit Gurjar. Improved Explicit Hitting-Sets for ROABPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.APPROX/RANDOM.2020.4,
  author =	{Guo, Zeyu and Gurjar, Rohit},
  title =	{{Improved Explicit Hitting-Sets for ROABPs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.4},
  URN =		{urn:nbn:de:0030-drops-126076},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.4},
  annote =	{Keywords: polynomial identity testing, hitting-set, ROABP, arithmetic branching programs, derandomization}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.33
Factorization of Polynomials Given By Arithmetic Branching Programs

Authors: Amit Sinhababu and Thomas Thierauf

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

Abstract
Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size s, we show that all its factors can be computed by arithmetic branching programs of size poly(s). Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was poly(s^(log s)).
Cite as

Amit Sinhababu and Thomas Thierauf. Factorization of Polynomials Given By Arithmetic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sinhababu_et_al:LIPIcs.CCC.2020.33,
  author =	{Sinhababu, Amit and Thierauf, Thomas},
  title =	{{Factorization of Polynomials Given By Arithmetic Branching Programs}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{33:1--33:19},
  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.33},
  URN =		{urn:nbn:de:0030-drops-125854},
  doi =		{10.4230/LIPIcs.CCC.2020.33},
  annote =	{Keywords: Arithmetic Branching Program, Multivariate Polynomial Factorization, Hensel Lifting, Newton Iteration, Hardness vs Randomness}
}
Document
DOI: 10.4230/LIPIcs.CCC.2019.15
Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications

Authors: Ashish Dwivedi, Rajat Mittal, and Nitin Saxena

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

Abstract
Finding an irreducible factor, of a polynomial f(x) modulo a prime p, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that counts the number of irreducible factors of f mod p. We can ask the same question modulo prime-powers p^k. The irreducible factors of f mod p^k blow up exponentially in number; making it hard to describe them. Can we count those irreducible factors mod p^k that remain irreducible mod p? These are called basic-irreducible. A simple example is in f=x^2+px mod p^2; it has p many basic-irreducible factors. Also note that, x^2+p mod p^2 is irreducible but not basic-irreducible! We give an algorithm to count the number of basic-irreducible factors of f mod p^k in deterministic poly(deg(f),k log p)-time. This solves the open questions posed in (Cheng et al, ANTS'18 & Kopp et al, Math.Comp.'19). In particular, we are counting roots mod p^k; which gives the first deterministic poly-time algorithm to compute Igusa zeta function of f. Also, our algorithm efficiently partitions the set of all basic-irreducible factors (possibly exponential) into merely deg(f)-many disjoint sets, using a compact tree data structure and split ideals.
Cite as

Ashish Dwivedi, Rajat Mittal, and Nitin Saxena. Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 15:1-15:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dwivedi_et_al:LIPIcs.CCC.2019.15,
  author =	{Dwivedi, Ashish and Mittal, Rajat and Saxena, Nitin},
  title =	{{Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{15:1--15:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.15},
  URN =		{urn:nbn:de:0030-drops-108373},
  doi =		{10.4230/LIPIcs.CCC.2019.15},
  annote =	{Keywords: deterministic, root, counting, modulo, prime-power, tree, basic irreducible, unramified}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.54
Towards Blackbox Identity Testing of Log-Variate Circuits

Authors: Michael A. Forbes, Sumanta Ghosh, and Nitin Saxena

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

Abstract
Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few variables, eg. logarithmic in the size s. We give the first poly(s)-time blackbox identity test for n=O(log s) variate size-s circuits that have poly(s)-dimensional partial derivative space; eg. depth-3 diagonal circuits (or Sigma wedge Sigma^n). The former model is well-studied (Nisan,Wigderson, FOCS'95) but no poly(s2^n)-time identity test was known before us. We introduce the concept of cone-closed basis isolation and prove its usefulness in studying log-variate circuits. It subsumes the previous notions of rank-concentration studied extensively in the context of ROABP models.
Cite as

Michael A. Forbes, Sumanta Ghosh, and Nitin Saxena. Towards Blackbox Identity Testing of Log-Variate Circuits. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{forbes_et_al:LIPIcs.ICALP.2018.54,
  author =	{Forbes, Michael A. and Ghosh, Sumanta and Saxena, Nitin},
  title =	{{Towards Blackbox Identity Testing of Log-Variate Circuits}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{54:1--54:16},
  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.54},
  URN =		{urn:nbn:de:0030-drops-90582},
  doi =		{10.4230/LIPIcs.ICALP.2018.54},
  annote =	{Keywords: hitting-set, depth-3, diagonal, derandomization, polynomial identity testing, log-variate, concentration, cone closed, basis isolation}
}
  • Refine by Type
  • 14 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 3 2025
  • 1 2023
  • 2 2021
  • 2 2020
  • Show More...

  • Refine by Author
  • 4 Ghosh, Sumanta
  • 3 Gurjar, Rohit
  • 2 Andrews, Robert
  • 2 Guo, Zeyu
  • 2 Saxena, Nitin
  • Show More...

  • Refine by Series/Journal
  • 14 LIPIcs

  • Refine by Classification
  • 9 Theory of computation → Algebraic complexity theory
  • 4 Theory of computation → Pseudorandomness and derandomization
  • 2 Computing methodologies → Algebraic algorithms
  • 2 Mathematics of computing → Combinatoric problems
  • 2 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 3 ROABP
  • 2 derandomization
  • 2 hitting-set
  • 2 polynomial identity testing
  • 1 Algebraic Algorithms
  • 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact