A symbolic determinant under rank-one restriction computes a polynomial of the form det(A0 + A1y1 + … + Anyn), where A0, A1, …, An are square matrices over a field F and rank(Ai) = 1 for each i ∈ [n]. This class of polynomials has been studied extensively, since the work of Edmonds (1967), in the context of linear matroids, matching, matrix completion and polynomial identity testing. We study the following learning problem for this class: Given black-box access to an n-variate polynomial f = det(A0 + A1y1 + … + Anyn), where A0, A1, …, An are unknown square matrices over F and rank(Ai) = 1 for each i ∈ [n], find a square matrix B0 and rank-one square matrices B1, …, Bn over F such that f = det(B0 + B1y1 + … + Bnyn). In this work, we give a randomized poly(n) time algorithm to solve this problem; the algorithm can be derandomized in quasi-polynomial time. To our knowledge, this is the first efficient learning algorithm for this class. As the above-mentioned class is known to be equivalent to the class of read-once determinants (RODs), we will refer to the problem as learning RODs. An ROD computes the determinant of a matrix whose entries are field constants or variables and every variable appears at most once in the matrix. Thus, the class of RODs is a rare example of a well-studied class of polynomials that admits efficient proper learning.

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 \(\mathbb {F}\) that outputs the evaluations of an m -variate polynomial of degree less than d in each variable at N points in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\) . A previous work of Kedlaya and Umans (FOCS 2008 and 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 and 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 . More specifically, our second algorithm solves the multivariate multipoint evaluation problem over a finite field \(\mathbb {F}\) in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\) , provided that the size of the finite field \(\mathbb {F}\) is at most \((\exp (\exp (\exp (\cdots (\exp (d)))))\) , where the height of this tower of exponentials is fixed.

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.

In this paper we address the multi-agent collab-orative object transportation problem in a partially known environment with obstacles under a specified goal condition. We propose a leader follower approach for two mobile manipulators collaboratively transporting an object along specified desired trajectories. The proposed approach treats the mobile manipulation system as two independent subsystems: a mobile platform and a manipulator arm and uses their kinematics model for trajectory tracking. In this work we considered that the mobile platform is subject to non-holonomic constraints, with a manipulator carrying a rigid load. The desired trajectories of the end points of the load are obtained from Probabilistic RoadMap-based planning approach. Our method combines Proportional Navigation Guidance-based approach with a proposed Stop-and-Sync algorithm to reach sufficiently close to the desired trajectory; the deviation due to the non-holonomic constraints being compensated by the manipulator arm. Concurrently, a leader follower approach for computing inverse kinematics solution for the position of the end-effector of the manipulator arm is proposed to maintain the load rigidity. Further, we compare the proposed approach with other approaches to analyse the efficacy of our algorithm.

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions such as polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck [ 7 ], fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state-of-the-art for this problem, Umans [ 25 ] and Kedlaya & Umans [ 16 ] gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields, respectively, provided that the number of variables n is at most \(d^{o(1)}\) where the degree of the input polynomial in every variable is less than d . They also stated the question of designing fast algorithms for the large variable case (i.e., \(n \notin d^{o(1)}\) ) as an open problem. In this work, we show that there is a deterministic algorithm for multivariate multipoint evaluation over a field \(\mathbb {F}_{q}\) of characteristic p , which evaluates an n -variate polynomial of degree less than d in each variable on N inputs in time \(\begin{equation*} \left((N + d^n)^{1 + o(1)}\text{poly}(\log q, d, n, p)\right), \end{equation*}\) provided that p is at most d o (1) , and q is at most (exp (exp (exp (...(exp ( d ))))), where the height of this tower of exponentials is fixed. When the number of variables is large (e.g., n ∉ d o (1) ), this is the first nearly linear time algorithm for this problem over any (large enough) field. Our algorithm is based on elementary algebraic ideas, and this algebraic structure naturally leads to the following two independently interesting applications: — We show that there is an algebraic data structure for univariate polynomial evaluation with nearly linear space complexity and sublinear time complexity over finite fields of small characteristic and quasipolynomially bounded size. This provides a counterexample to a conjecture of Miltersen [ 21 ] who conjectured that over small finite fields, any algebraic data structure for polynomial evaluation using polynomial space must have linear query complexity. — We also show that over finite fields of small characteristic and quasipolynomially bounded size, Vandermonde matrices are not rigid enough to yield size-depth tradeoffs for linear circuits via the current quantitative bounds in Valiant’s program [ 26 ]. More precisely, for every fixed prime p , we show that for every constant ɛ > 0, and large enough n , the rank of any \(n \times n\) Vandermonde matrix V over the field \(\mathbb {F}_{p^a}\) can be reduced to ( n /exp (Ω (poly(ɛ)log 0.53 n ))) by changing at most n Θ (ɛ) entries in every row of V , provided a ≤ poly(log n ). Prior to this work, similar upper bounds on rigidity were known only for special Vandermonde matrices. For instance, the Discrete Fourier Transform matrices and Vandermonde matrices with generators in a geometric progression [ 9 ].

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.

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).

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions like polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck, fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state of art for this problem, Umans and Kedlaya & Umans gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields respectively, provided that the number of variables n is at most do(1) where the degree of the input polynomial in every variable is less than d. They also stated the question of designing fast algorithms for the large variable case (i.e. n ∉ do(1)) as an open problem.

In this paper we study polynomials in VP_{e} (polynomial-sized formulas) and in ΣΠΣ (polynomial-size depth-3 circuits) whose orbits, under the action of the affine group GL^{aff}_n(𝔽) (the action of (A,b) ∈ GL^{aff}_n(𝔽) on a polynomial f ∈ 𝔽[x] is defined as (A,b)∘f = f(A^Tx+b)), are dense in their ambient class. We construct hitting sets and interpolating sets for these orbits as well as give reconstruction algorithms. Specifically, we obtain the following results: 1) For C_n(ℓ_1(x),…,ℓ_n(x)) ≜ Trace(\begin{pmatrix} 𝓁₁(x) & 1 \\ 1 & 0 \end{pmatrix} ⋅ … ⋅ \begin{pmatrix} 𝓁_n(x) & 1 \\ 1 & 0 \end{pmatrix}), where the 𝓁_is are linearly independent linear functions, we construct a polynomial-sized interpolating set, and give a polynomial-time reconstruction algorithm. By a result of Bringmann, Ikenmeyer and Zuiddam, the set of all such polynomials is dense in VP_e [Karl Bringmann et al., 2018], thus our construction gives the first polynomial-size interpolating set for a dense subclass of VP_e. 2) For polynomials of the form ANF_Δ(𝓁₁(x),…,𝓁_{4^Δ}(x)), where ANF_Δ(x) is the canonical read-once formula in alternating normal form, of depth 2Δ, and the 𝓁_is are linearly independent linear functions, we provide a quasipolynomial-size interpolating set. We also observe that the reconstruction algorithm of [Ankit Gupta et al., 2014] works for all polynomials in this class. This class is also dense in VP_e. 3) Similarly, we give a quasipolynomial-sized hitting set for read-once formulas (not necessarily in alternating normal form) composed with a set of linearly independent linear functions. This gives another dense class in VP_e. 4) We give a quasipolynomial-sized hitting set for polynomials of the form f(𝓁₁(x),…,𝓁_{m}(x)), where f is an m-variate s-sparse polynomial. and the 𝓁_is are linearly independent linear functions in n ≥ m variables. This class is dense in ΣΠΣ. 5) For polynomials of the form ∑_{i=1}^{s}∏_{j=1}^{d}𝓁_{i,j}(x), where the 𝓁_{i,j}s are linearly independent linear functions, we construct a polynomial-sized interpolating set. We also observe that the reconstruction algorithm of [Neeraj Kayal and Chandan Saha, 2019] works for every polynomial in the class. This class is dense in ΣΠΣ. As VP = VNC², our results for VP_{e} translate immediately to VP with a quasipolynomial blow up in parameters. If any of our hitting or interpolating sets could be made robust then this would immediately yield a hitting set for the superclass in which the relevant class is dense, and as a consequence also a lower bound for the superclass. Unfortunately, we also prove that the kind of constructions that we have found (which are defined in terms of k-independent polynomial maps) do not necessarily yield robust hitting sets.

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].

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.