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.

Abstract For a polynomial f, a weighted sum-of-squares representation (SOS) has the form $$f = \sum_{i\in [s]} c_i f_i^2$$ f = ∑ i ∈ [ s ] c i f i 2 , where the weights $$c_i$$ c i are field elements. The size of the representation is the number of monomials that appear across the $$f_i$$ f i 's. Its minimum across all such decompositions is called the support-sum S(f) of f. For a univariate polynomial f of degree d of full support, a lower bound for the support-sum is $$S(f) \ge \sqrt d$$ S ( f ) ≥ d . We show that the existence of an explicit univariate polynomial f with support-sum just slightly larger than the lower bound, that is, $$S(f) \ge d^{0.5+\varepsilon}$$ S ( f ) ≥ d 0.5 + ε , for some $$\varepsilon > 0$$ ε > 0 , implies that $$\ne$$ ≠ , the major open problem in algebraic complexity. In fact, our proof works for some subconstant functions $$\varepsilon(d) > 0$$ ε ( d ) > 0 as well. We also consider the sum-of-cubes representation (SOC) of polynomials. We show that an explicit hard polynomial implies both blackbox-PIT is in , and $$\neq$$ ≠ .

For a polynomial f, we study the sum of squares representation (SOS), i.e. f = ∑_{i ∈ [s]} c_i f_i² , where c_i are field elements and the f_i’s are polynomials. The size of the representation is the number of monomials that appear across the f_i’s. Its minimum is the support-sum S(f) of f. For simplicity of exposition, we consider univariate f. A trivial lower bound for the support-sum of, a full-support univariate polynomial, f of degree d is S(f) ≥ d^{0.5}. We show that the existence of an explicit polynomial f with support-sum just slightly larger than the trivial bound, that is, S(f) ≥ d^{0.5+ε(d)}, for a sub-constant function ε(d) > ω(√{log log d/log d}), implies that VP ≠ VNP. The latter is a major open problem in algebraic complexity. A further consequence is that blackbox-PIT is in SUBEXP. Note that a random polynomial fulfills the condition, as there we have S(f) = Θ(d). We also consider the sum-of-cubes representation (SOC) of polynomials. In a similar way, we show that here, an explicit hard polynomial even implies that blackbox-PIT is in P.

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^{ {\rm \log} s}) $$ ( s log s ) .

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.

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

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

Counting the number of perfect matchings in arbitrary graphs is a #P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for K3,3-free graphs, Vazirani showed that it is in NC2. The technique there is to compute a Pfaffian orientation of a graph. In the case of K5-free graphs, this technique will not work because some K5-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K5-free graphs can be computed in polynomial time and we describe a circuit construction in TC2.

The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class AC 1. In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to UL∩coUL. As a consequence of our method we get that the isomorphism problem for oriented graphs is in NL. We also show that the problems are hard for L.

Graph isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and important special case by presenting an upper bound that matches the known log-space hardness. In fact, we show the formally stronger result that planar graph canonization is in log-space. This improves the previously known upper bound of AC. Our algorithm first constructs the biconnected component tree of a connected planar graph and then refines each biconnected component into a triconnected component tree. The next step is to log-space reduce the biconnected planar graph isomorphism and canonization problems to those for 3-connected planar graphs, which are known to be in log-space by. This is achieved by using the above decomposition, and by making significant modifications to Lindellpsilas algorithm for tree canonization, along with changes in the space complexity analysis. The reduction from the connected case to the biconnected case requires further new ideas, including a non-trivial case analysis and a group theoretic lemma to bound the number of automorphisms of a colored 3-connected planar graph. This lemma is crucial for the reduction to work in log-space.

Graph isomorphism is an important and widely studied computational problem with a yet unsettled complexity. However, the exact complexity is known for isomorphism of various classes of graphs. Recently, \cite{DLNTW09} proved that planar isomorphism is complete for log-space. We extend this result %of \cite{DLNTW09} further to the classes of graphs which exclude $K_{3,3}$ or $K_5$ as a minor, and give a log-space algorithm. Our algorithm decomposes $K_{3,3}$ minor-free graphs into biconnected and those further into triconnected components, which are known to be either planar or $K_5$ components \cite{Vaz89}. This gives a triconnected component tree similar to that for planar graphs. An extension of the log-space algorithm of \cite{DLNTW09} can then be used to decide the isomorphism problem. For $K_5$ minor-free graphs, we consider $3$-connected components. These are either planar or isomorphic to the four-rung mobius ladder on $8$ vertices or, with a further decomposition, one obtains planar $4$-connected components \cite{Khu88}. We give an algorithm to get a unique decomposition of $K_5$ minor-free graphs into bi-, tri- and $4$-connected components, and construct trees, accordingly. Since the algorithm of \cite{DLNTW09} does not deal with four-connected component trees, it needs to be modified in a quite non-trivial way.

The inertia of an n /spl times/ n matrix A is defined as the triple (i/sub +/ (A), i/spl I.bar/(A), i/sub 0/(A)), where i/sub +/(A), i/spl I.bar/(A), and i/sub 0/(A) are the number of eigenvalues of A, counting multiplicities, with positive, negative, and zero real part. It is known that the inertia of a large class of matrices can be determined in PL (probabilistic logspace). However, the general problem, whether the inertia of an arbitrary integer matrix is computable in PL, was an open question. In this paper we give a positive answer to this question and show that the problem is complete for PL. As consequences of this result we show necessary and sufficient conditions that certain algebraic functions like the rank or the inertia of an integer matrix can be computed in GapL.

We investigate the computational complexity of some important problems in linear algebra. 1. The problem of verifying the characteristic polynomial of a matrix is known to be in the complexity class C/sub =/L (Exact Counting in Logspace). We show that it is complete for C/sub =/L under logspace many-one reductions. 2. The problem of deciding whether two matrices are similar is known to be in the complexity class AC/sup 0/(C=L). We show that it is complete for this class under logspace many-one reductions. We also consider the problems of deciding equivalence and congruence of matrices.

We investigate the computational complexity of the formula isomorphism problem (FI): on input of two boolean formulas F and G decide whether there exists a permutation of the variables of G such that F and G become equivalent. FI is contained in ${\Sigma_{2}{\bf P}}$, the second level of the polynomial hierarchy. Our main result is a one-round interactive proof for the complementary formula nonisomorphism problem (FNI), where the verifier has access to an NP-oracle. To obtain this, we use a result from learning theory by Bshouty et al. that boolean formulas can be learned probabilistically with equivalence queries and access to an NP-oracle. As a consequence, FI cannot be ${\Sigma_{2}{\bf P}}$-complete unless the polynomial hierarchy collapses. Further properties of FI are shown: FI has and- and or-functions, the counting version, #FI, can be computed in polynomial time relative to FI, and FI is self-reducible.

We show that MA/sub EXP/, the exponential time version of the Merlin-Arthur class, does not have polynomial size circuits. This significantly improves the previous known result due to Kannan since we furthermore show that our result does not relativize. This is the first separation result in complexity theory that does not relativize. As a corollary to our separation result we also obtain that PEXP, the exponential time version of PP is nor in P/poly.

Threshold machines are Turing machines whose acceptance is determined by what portion of the machine's computation paths are accepting paths. Probabilistic machines are Turing machines whose acceptance is determined by the probability weight of the machine's accepting computation paths. In 1975, Simon proved that for unbounded-error polynomial-time machines these two notions yield the same class, PP\@. Perhaps because Simon's result seemed to collapse the threshold and probabilistic modes of computation, the relationship between threshold and probabilistic computing for the case of bounded error has remained unexplored. In this paper, we compare the bounded-error probabilistic class BPP with the analogous threshold class, $\bpppath$, and, more generally, we study the structural properties of $\bpppath$. We prove that $\rm BPP_{path}$ contains both $\np^{\bpp}$ and $\p^{\rm NP[\log]}$ and that $\rm BPP_{path}$ is contained in $\p^{{\rm \Sigma}_2^p[\log]}$, $\rm BPP^{NP}$, and PP\@. We conclude that, unless the polynomial hierarchy collapses, bounded-error threshold computation is strictly more powerful than bounded-error probabilistic computation. We also consider the natural notion of secure access to a database: an adversary who watches the queries should gain no information about the input other than perhaps its length. We show for both $\bpp$ and $\bpppath$ that if there is any database for which this formalization of security differs from the security given by oblivious database access, then $\p\neq \pspace$\@. It follows that if any set lacking small circuits can be securely accepted, then $\p\neq\pspace$.

We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV this class exhibits very different properties. We clarify the complexity of coNPMV by showing that it is essentially the same as that of NPMV/sup NP/ complete functions for coNPMV are exhibited and central complexity-theoretic properties of this class are studied. We show that computing maximum satisfying assignments can be done in coNPMV, which leads us to a comparison of NPMV and coNPMV with Krentel's classes Max P and Min P. The difference hierarchy for NPMV is related to the query hierarchy for coNPMV. Finally, we examine a functional analogue of Chang and Kadin's relationship between a collapse of the Boolean hierarchy over NP and a collapse of the polynomial time hierarchy.

We investigate the computational complexity of the Boolean isomorphism problem (BI): on input of two Boolean formulas F and G decide whether there exists a permutation of the variables of G such that F and G become equivalent. Our main result is a one-round interactive proof for BI, where the verifier has access to an NP oracle. To obtain this, we use a recent result from learning theory by N. Bshouty et al. (1995), that Boolean formulas can be learned probabilistically with equivalence queries and access to an NP oracle. As a consequence, BI cannot be /spl Sigma//sub 2//sup p/ complete unless the polynomial hierarchy collapses. This solves an open problem posed previously. Further properties of BI are shown: BI has And- and Or-functions, the counting version, BI, can be computed in polynomial time relative to BI, and BI is self-reducible.

We investigate classes of sets that can be decided by bounded truth-table reductions to an NP set in which evaluators donothave full access to the answers to the queries but get only restricted information such as the number of queries that are in the oracle set or even just this number modulom, for somem⩾2. We also investigate the case in which evaluators are nondeterministic. We show that when we vary the information that the evaluators get, this can change the resulting power of the evaluators. We locate all these classes within levels of the Boolean hierarchy which allows us to compare the complexity of such classes.

For any operatorτon integer-valued functions, we say that #P isclosed under τ in the context ofPF∘#P if, for everyf∈#P,τ[f] belongs to PF∘num;P. For several operatorsτ, it is shown that the closure properties of #P underτin the above sense is closely related to the relationships between P#P[1]and higher classes such as PHPPand PPPP.

The authors consider uniform subclasses of the nonuniform complexity classes defined by Karp and Lipton [L’Enseign. Math., 28 (1982)) via the notion of advice functions. These subclasses are obtained by restricting the complexity of computing correct advice. Also, the effect of allowing advice functions of limited complexity to depend on the input rather than on the input’s length is investigated. Among other results, using the notions described above, new characterizations of (a) ${\text{NP}}^{{\text{NP}} \cap {\text{SPARSE}}} $, (b) ${\text{NP}}$ with a restricted access to an ${\text{NP}}$ oracle, and (c) the odd levels of the boolean hierarchy are given. As a consequence, it is shown that every set that is nondeterministically truth-table reducible to SAT in the sense of Rich [J. Comput. System Sci., 38 (1989), pp. 511–523) is already deterministically truth-table reducible to SAT. Furthermore, it turns out that the NP reduction classes of bounded versions of this reducibility coincide with the odd levels of the boolean hierarchy.