Arrow Research search

Author name cluster

Sumanta Ghosh

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
1 author row

Possible papers

6

STOC Conference 2025 Conference Paper

Characterizing and Testing Principal Minor Equivalence of Matrices

  • Abhranil Chatterjee 0001
  • Sumanta Ghosh
  • Rohit Gurjar
  • Roshan Raj

Two matrices are said to be principal minor equivalent if they have equal corresponding principal minors of all orders. We give a characterization of principal minor equivalence and a deterministic polynomial time algorithm to check if two given matrices are principal minor equivalent. Earlier such results were known for certain special cases like symmetric matrices, skew-symmetric matrices with 0, 1, -1-entries, and matrices with no cuts (i.e., for any non-trivial partition of the indices, the top right block or the bottom left block must have rank more than 1). As an immediate application, we get an algorithm to check if the determinantal point processes corresponding to two given kernel matrices (not necessarily symmetric) are the same. As another application, we give a deterministic polynomial-time test to check the equality of two multivariate polynomials, each computed by a symbolic determinant with a rank 1 constraint on coefficient matrices.

Details

FOCS Conference 2023 Conference Paper

Fast Numerical Multivariate Multipoint Evaluation

  • Sumanta Ghosh
  • Prahladh Harsha
  • Simao Herdade
  • Mrinal Kumar 0001
  • Ramprasad Saptharishi

We design nearly-linear time numerical algorithms for the problem of multivariate multipoint evaluation over the fields of rational, real and complex numbers. We consider both exact and approximate versions of the algorithm. The input to the algorithms are (1) coefficients of an m-variate polynomial f with degree d in each variable, and (2) points $\mathbf{a}_{1}, \ldots, \mathbf{a}_{N}$ each of whose coordinate has absolute value bounded by one. Approximate version: Given additionally an accuracy parameter t, the algorithm computes rational numbers $\beta_{1}, \ldots, \beta_{N}$ such that $\left|f\left(\mathbf{a}_{i}\right)-\beta_{i}\right| \leq 1 / 2^{t}$ for all i, and has a running time of $\left(\left(N m+d^{m}\right) t\right)^{1+o(1)}$ for all m and all sufficiently large d. Exact version (when over rationals): Given additionally a bound s on the bit-complexity of all the rational numbers in the input and output, the algorithm computes the rational numbers $f\left(\mathbf{a}_{1}\right), \ldots, f\left(\mathbf{a}_{N}\right)$, in time $\left(\left(N m+d^{m}\right) s\right)^{1+o(1)}$ for all m and all sufficiently large d. Our results also naturally extend to the case when the input is over the field of real or complex numbers under an appropriate standard model of representation of field elements in such fields. Prior to this work, a nearly-linear time algorithm for multivariate multipoint evaluation (exact or approximate) over any infinite field appears to be known only for the case of univariate polynomials, and was discovered in a recent work of Moroz [Proc. 62nd FOCS, 2021]. In this work, we extend this result from the univariate to the multivariate setting. However, our algorithm is based on ideas that seem to be conceptually different from those of Moroz [Proc. 62nd FOCS, 2021] and crucially relies on a recent algorithm of Bhargava, Ghosh, Guo, Kumar & Umans [Proc. 63rd FOCS, 2022] for multivariate multipoint evaluation over finite fields, and known efficient algorithms for the problems of rational number reconstruction and fast Chinese remaindering in computational number theory.

Details

SODA Conference 2022 Conference Paper

A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision

  • Sumanta Ghosh
  • Rohit Gurjar
  • Roshan Raj

Given two matroids on the same ground set, the matroid intersection problem asks for a common base, i. e. , a subset of the ground set that is a base in both the matroids. The weighted version of the problem asks for a common base with maximum weight. In the general case, when the two matroids are given via rank oracles, the question of its parallel complexity is completely open. In the case of linearly representable matroids, the problem is known to have randomized parallel (RNC) algorithms, when the given weights are polynomially bounded. Finding a deterministic parallel (NC) algorithm in this case, even for the decision question, has been a long standing open question. We make some progress towards understanding the parallel complexity of matroid intersection by showing that the weighted matroid intersection (WMI) search problem is equivalent to its decision version, in a parallel model of computation. More precisely, we give an NC algorithm for WMI-search using an oracle access to WMI-decision. This resolves an open question posed by Anari and Vazirani (ITCS 2020).

Details

FOCS Conference 2022 Conference Paper

Fast Multivariate Multipoint Evaluation Over All Finite Fields

  • Vishwas Bhargava
  • Sumanta Ghosh
  • Zeyu Guo 0001
  • Mrinal Kumar 0001
  • Chris Umans

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field F that outputs the evaluations of an m-variate polynomial of degree less than d in each variable at N points in time $(d^{m}+N)^{1+o(1)}$ poly $(m, \ d, \ \log|\mathbb{F}|)$ for all $m\in \mathbb{N}$ and all sufficiently large $d\in \mathbb{N}$. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables m is at most $d^{o(1)}$ and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than $d^{o(1)}$. In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski and Williams (IPEC 2017, Algorithmica 2019), and that of Bhargava, Ghosh, Kumar and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and in particular, avoids the use of the Bombieri-Vinogradov Theorem. However, it requires a mild assumption that the field size is bounded by an exponential-tower in d of bounded height.

Details