Minimally rigid graphs can be decided and embedded in the plane efficiently, i.e. in polynomial time. There is also an efficient randomized parallel algorithm, i.e. in RNC. We present an NC-algorithm to decide whether one-crossing-minor-free graphs are minimally rigid. In the special case of K_{3,3}-free graphs, we also compute an infinitesimally rigid embedding in NC.

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.

In this paper, we suggest to extend the notion of a kernel to permit the kernelization algorithm to be executed in quasi-polynomial time rather than polynomial time. So far, we are only aware of one work that addressed this negatively, showing that some lower bounds on kernel sizes proved for kernelization also hold when quasi-polynomial time complexity is allowed. When we, anyway, deal with an NP-hard problem, sacrificing polynomial time in preprocessing for quasi-polynomial time may often not be a big deal, but, of course, the question is - does it give us more power? The only known work, mentioned above, seems to suggest that the answer is "no". In this paper, we show that this is not the case - in particular, we show that this notion is extremely powerful for derandomization. Some of the most basic kernelization algorithms in the field are based on inherently randomized tools whose derandomization is a huge problem that has remained (and may still remain) open for many decades. Still, some breakthrough advances for derandomization in quasi-polynomial time have been made. Can we harness these advancements to design quasi-polynomial deterministic kernelization algorithms for basic problems in the field? To this end, we revisit the question of deterministic polynomial-time computation of a linear representation of transversal matroids and gammoids, which is a longstanding open problem. We present a deterministic computation of a representation matrix of a transversal matroid in time quasipolynomial in the rank of the matroid, where each entry of the matrix can be represented in quasipolynomial (in the rank of the matroid) bits. As a corollary, we obtain a linear representation of a gammoid in deterministic quasipolynomial time and quasipolynomial bits in the size of the underlying ground set of the gammoid. In turn, as applications of our results, we present deterministic quasi-polynomial time kernels of polynomial size for several central problems in the field.

The matching and linear matroid intersection problems are solvable in quasi-NC, meaning that there exist deterministic algorithms that run in polylogarithmic time and use quasi-polynomially many parallel processors. However, such a parallel algorithm is unknown for linear matroid matching, which generalizes both of these problems. In this work, we propose a quasi-NC algorithm for fractional linear matroid matching, which is a relaxation of linear matroid matching and commonly generalizes fractional matching and linear matroid intersection. Our algorithm builds upon the connection of fractional matroid matching to non-commutative Edmonds' problem recently revealed by Oki and Soma~(2023). As a corollary, we also solve black-box non-commutative Edmonds' problem with rank-two skew-symmetric coefficients.

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

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

We show that the bipartite perfect matching problem is in quasi-$\mathsf{NC}^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

We present a geometric approach toward derandomizing the isolation lemma of Mulmuley, Vazirani, and Vazirani. We construct a quasi-polynomial family of weights that isolate a vertex in any 0/1-polytope for which each face spans an affine space defined by a totally unimodular matrix. These polytopes are also called box-totally dual integral or principally box-integer. This includes the polytopes given by totally unimodular constraints and generalizes the recent derandomization of the isolation lemma for bipartite perfect matching and matroid intersection. We prove our result by associating a lattice to each face of the polytope and showing that if there is a totally unimodular kernel matrix for this lattice, then the number of vectors of length within 3/2 of the shortest vector in it is polynomially bounded. The proof of this latter geometric fact is combinatorial and follows from a polynomial bound on the number of circuits of size within 3/2 of the shortest circuit in a regular matroid. This is the technical core of the paper and relies on a variant of Seymour's decomposition theorem for regular matroids. It generalizes an influential result by Karger on the number of minimum cuts in a graph to regular matroids.

We show that for any regular matroid on m elements and $\alpha \geq 1$, the number of $\alpha$-minimum circuits, or circuits whose size is at most an $\alpha$-multiple of the minimum size of a circuit in the matroid, is bounded by $m^{O(\alpha^2)}.$ This generalizes a result of Karger for the number of $\alpha$-minimum cuts in a graph. As a consequence, we obtain similar bounds on the number of $\alpha$-shortest vectors in totally unimodular lattices and on the number of $\alpha$-minimum weight code words in regular codes.

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

A set function f : 2^E → ℝ on the subsets of a set E is called submodular if it satisfies a natural diminishing returns property: for any S ⊆ E and x,y ∉ S, we have f(S ∪ {x,y}) - f(S ∪ {y}) ≤ f(S ∪ {x}) - f(S). Submodular minimization problem asks for finding the minimum value a given submodular function takes. We give an algebraic algorithm for this problem for a special class of submodular functions that are "linearly representable". It is known that every submodular function f can be decomposed into a sum of two monotone submodular functions, i.e., there exist two non-decreasing submodular functions f₁,f₂ such that f(S) = f₁(S) + f₂(E ⧵ S) for each S ⊆ E. Our class consists of those submodular functions f, for which each of f₁ and f₂ is a sum of k rank functions on families of subspaces of 𝔽ⁿ, for some field 𝔽. Our algebraic algorithm for this class of functions can be parallelized, and thus, puts the problem of finding the minimizing set in the complexity class randomized NC. Further, we derandomize our algorithm so that it needs only O(log²(kn|E|)) many random bits. We also give reductions from two combinatorial optimization problems to linearly representable submodular minimization, and thus, get such parallel algorithms for these problems. These problems are (i) covering a directed graph by k a-arborescences and (ii) packing k branchings with given root sets in a directed graph.

Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. In case of linear matroids, the problem had a randomized parallel algorithm but no deterministic one. We give an almost complete derandomization of this algorithm, which implies that the linear matroid intersection problem is in quasi-NC. That is, it has uniform circuits of quasi-polynomial size $$n^{O(\log n)}$$ n O ( log n ) and O(polylog(n)) depth. Moreover, the depth of the circuit can be reduced to O(log2 n) in case of zero characteristic fields. This generalizes a similar result for the bipartite perfect matching problem. Our main technical contribution is to derandomize the Isolation lemma for the family of common bases of two matroids. We use our isolation result to give a quasi-polynomial time blackbox algorithm for a special case of Edmonds' problem, i.e., singularity testing of a symbolic matrix, when the given matrix is of the form $$A_{0} + A_{1 }x_{1} + \cdots + A_{m} x_{m}$$ A 0 + A 1 x 1 + ⋯ + A m x m , for an arbitrary matrix A0 and rank-1 matrices $$A_{1}, A_{2}, \dots, A_{m}$$ A 1 , A 2 , ⋯ , A m . This can also be viewed as a blackbox polynomial identity testing algorithm for the corresponding determinant polynomial. Another consequence of this result is a deterministic solution to the maximum rank matrix completion problem. Finally, we use our result to find a deterministic representation for the union of linear matroids in quasi-NC.

We show that for any regular matroid on m elements and any α ≥ 1, the number of α-minimum circuits, or circuits whose size is at most an α-multiple of the minimum size of a circuit in the matroid is bounded by mO(α2). This generalizes a result of Karger for the number of α-minimum cuts in a graph. As a consequence, we obtain similar bounds on the number of α-shortest vectors in “totally unimodular” lattices and on the number of α-minimum weight codewords in “regular” codes.

We give improved hitting-sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known variable order. The best hitting-set known for this case had cost (nw)^{O(log(n))}, where n is the number of variables and w is the width of the ROABP. Even for a constant-width ROABP, nothing better than a quasi-polynomial bound was known. We improve the hitting-set complexity for the known-order case to n^{O(log(w))}. In particular, this gives the first polynomial time hitting-set for constant-width ROABP (known-order). However, our hitting-set works only over those fields whose characteristic is zero or large enough. To construct the hitting-set, we use the concept of the rank of partial derivative matrix. Unlike previous approaches whose starting point is a monomial map, we use a polynomial map directly. The second case we consider is that of commutative ROABP. The best known hitting-set for this case had cost d^{O(log(w))}(nw)^{O(log(log(w)))}, where d is the individual degree. We improve this hitting-set complexity to (ndw)^{O(log(log(w)))}. We get this by achieving rank concentration more efficiently.

The perfect matching problem has a randomized NC algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph ensures that it has a unique minimum weight perfect matching, with a good probability. We derandomize this lemma for K3,3-free and K5-free bipartite graphs. That is, we give a deterministic log-space construction of such a weight assignment for these graphs. Such a construction was known previously for planar bipartite graphs. Our result implies that the perfect matching problem for K3,3-free and K5-free bipartite graphs is in SPL. It also gives an alternate proof for an already known result – reachability for K3,3-free and K5-free graphs is in UL.

We show that the bipartite perfect matching problem is in quasi- NC2. That is, it has uniform circuits of quasi-polynomial size nO(logn), and O(log2 n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity n^(O(log(n))). In both the cases, our time complexity is double exponential in the number of ROABPs. ROABPs are a generalization of set-multilinear depth-3 circuits. The prior results for the sum of constantly many set-multilinear depth-3 circuits were only slightly better than brute-force, i.e. exponential-time. Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).

We give an $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious arithmetic branching programs (ROABPs). The best time complexity known for blackbox polynomial identity testing (PIT) for this class was $n^{O(\log^2 n)}$ due to Forbes, Saptharishi, and Shpilka [Proceedings of the 2014 ACM Symposium on Theory of Computing, 2014, pp. 867--875]. Moreover, their result holds only when the individual degree is small, while we do not need any such assumption. With this, we match the time complexity for the unknown-order ROABP with the known-order ROABP (due to Forbes and Shpilka [Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 243--252]) and also with the depth-3 set-multilinear circuits (due to Agrawal, Saha, and Saxena [Proceedings of the 2013 ACM Symposium on Theory of Computing, 2013, pp. 321--330]). Our proof is simpler and involves a new technique called basis isolation. The depth-3 model has recently gained much importance, as it has become a stepping stone to understanding general arithmetic circuits. Multilinear depth-3 circuits are known to have exponential lower bounds but no polynomial time blackbox identity tests. In this paper, we take a step toward designing such hitting-sets. We give the first subexponential whitebox PIT for the sum of constantly many set-multilinear depth-3 circuits. To achieve this, we define the notions of distance and base sets. Distance, for a multilinear depth-3 circuit (say, in $n$ variables and $k$ product gates), measures how far the variable partitions corresponding to the product gates are from being a mere refinement of each other. The 1-distance circuits strictly contain the set-multilinear model, while $n$-distance captures general multilinear depth-3. We design a hitting-set in time $(nk)^{O(\Delta \log n)}$ for $\Delta$-distance. Further, we give an extension of our result to models where the distance is large (close to $n$) but is small when restricted to certain base sets (of variables). We also explore a new model of ROABPs where the factor matrices are invertible (called invertible-factor ROABPs). We design a hitting-set in time poly($n^{w^2}$) for width-$w$ invertible-factor ROABPs. Further, we could do without the invertibility restriction when w=2. Previously, the best result for width-2 ROABPs was quasi-polynomial time [M. A. Forbes, R. Saptharishi, and A. Shpilka, Proceedings of the 2014 ACM Symposium on Theory of Computing, 2014, pp. 867--875].