In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds. Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar. As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.
Toda @cite_7 proved that several definitions for the class @math are equivalent, see also @cite_31 . In particular @math is the class of polynomials that can be written as determinants of matrices of polynomially bounded size whose entries are affine linear forms. Due to its pure mathematical formulation, lower bounds for this attracted the attention of geometers @cite_15 @cite_19 @cite_16 . Moreover, Mulmuley and Sohoni's geometric complexity approach @cite_21 @cite_40 is also mainly focused on lower bounds for the determinantal complexity and the symmetries of the determinant polynomial play a key role in their work. Recently @cite_52 showed that it is not possible to prove superpolynomial lower bounds on the determinantal complexity using only information about the occurrences non-occurrences of irreducible representations in the coordinate rings of the orbit closures of the determinant and the (padded) permanent. This disproves a major conjecture in geometric complexity theory. The proof in @cite_52 is fairly general and also holds for lower bounds on the formula size. Only very recently the formula size analog to determinantal complexity, the was studied from a geometric perspective @cite_17 .
@cite_7 @cite_15 @cite_21 @cite_52 @cite_19 @cite_40 @cite_31 @cite_16 @cite_17
2313549751 2084050956 2591592591 2170546552 2963573981 2962723550 2341997752 2077575254 1982831910
The determinantal complexity of a polynomial f is defined here as the minimal size of a matrix M with affine entries such that f = det M. This function gives a minoration of the more traditional size of an arithmetical formula. Consider the polynomial “permanent” perm d of a d × d matrix with entries X i,j . A conjecture in complexity theory says that the determinantal complexity (dc) of perm d should not be polynomial in d. In this article we prove that dc(permd)≥d2 2, improving the previously known minoration, 2d. We also begin a systematic study of the function dc, and compute it for the homogeneous polynomials of degree 2. We show that, over Q, if an n-variate polynomial of degree d = nO(1) is computable by an arithmetic circuit of size s (respectively by an arithmetic branching program of size s) then it can also be computed by a depth three circuit (i.e. a ΣΠΣ-circuit) of size exp(O(√(d log n log d log s))) (respectively of size exp(O(√(d log n log s))). In particular this yields a ΣΠΣ circuit of size exp(O(√(d log d))) computing the d × d determinant Detd. It also means that if we can prove a lower bound of exp(omega(√(d log d))) on the size of any ΣΠΣ-circuit computing the d × d permanent Permd then we get super polynomial lower bounds for the size of any arithmetic branching program computing Permd. We then give some further results pertaining to derandomizing polynomial identity testing and circuit lower bounds. The ΣΠΣ circuits that we construct have the property that (some of) the intermediate polynomials have degree much higher than d. Indeed such a counterintuitive construction is unavoidable - it is known that in any ΣΠΣ circuit C computing either Detd or Perm_d, if every multiplication gate has fanin at most d (or any constant multiple thereof) then C must have size at least exp(Ω(d)). This paper considers the problem of designing maximum distance separable (MDS) codes over small fields with constraints on the support of their generator matrices. For any given @math binary matrix @math , the GM-MDS conjecture, proposed by , states that if @math satisfies the so-called MDS condition, then for any field @math of size @math , there exists an @math MDS code whose generator matrix @math , with entries in @math , fits the matrix @math (i.e., @math is the support matrix of @math ). Despite all the attempts by the coding theory community, this conjecture remains still open in general. It was shown, independently by and , that the GM-MDS conjecture holds if the following conjecture, referred to as the TM-MDS conjecture, holds: if @math satisfies the MDS condition, then the determinant of a transform matrix @math , such that @math fits @math , is not identically zero, where @math is a Vandermonde matrix with distinct parameters. In this work, we first reformulate the TM-MDS conjecture in terms of the Wronskian determinant, and then present an algebraic-combinatorial approach based on polynomial-degree reduction for proving this conjecture. Our proof technique's strength is based primarily on reducing inherent combinatorics in the proof. We demonstrate the strength of our technique by proving the TM-MDS conjecture for the cases where the number of rows ( @math ) of @math is upper bounded by @math . For this class of special cases of @math where the only additional constraint is on @math , only cases with @math were previously proven theoretically, and the previously used proof techniques are not applicable to cases with @math . Mulmuley [Mul12a] recently gave an explicit version of Noether’s Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In this work, we show this is not the case. That is, we improve Mulmuley’s reduction and correspondingly weaken the conjecture regarding PIT needed to give explicit Noether Normalization. We then observe that the weaker conjecture has recently been nearly settled by the authors ([FS12]), who gave quasipolynomial size hitting sets for the class of read-once oblivious algebraic branching programs (ROABPs). This gives the desired explicit Noether Normalization unconditionally, up to quasipolynomial factors. As a consequence of our proof we give a deterministic parallel polynomial-time algorithm for deciding if two matrix tuples have intersecting orbit closures, under simultaneous conjugation. We also study the strength of conjectures that Mulmuley requires to obtain similar results as ours. We prove that his conjectures are stronger, in the sense that the computational model he needs PIT algorithms for is equivalent to the well-known algebraic branching program (ABP) model, which is provably stronger than the ROABP model. Finally, we consider the depth-3 diagonal circuit model as defined by Saxena [Sax08], as PIT algorithms for this model also have implications in Mulmuley’s work. Previous work (such as [ASS12] and [FS12]) have given quasipolynomial size hitting sets for this model. In this work, we give a much simpler construction of such hitting sets, using techniques of Shpilka and Volkovich [SV09]. We prove that the determinantal complexity of a hypersurface of degree @math d>2 is bounded below by one more than the codimension of the singular locus, provided that this codimension is at least 5. As a result, we obtain that the determinantal complexity of the @math 3×3 permanent is 7. We also prove that for @math n>3, there is no nonsingular hypersurface in @math Pn of degree d that has an expression as a determinant of a @math d×d matrix of linear forms, while on the other hand for @math n≤3, a general determinantal expression is nonsingular. Finally, we answer a question of Ressayre by showing that the determinantal complexity of the unique (singular) cubic surface containing a single line is 5. We determine set-theoretic defining equations for the variety of hypersurfaces of degree d in an N-dimensional complex vector space that have dual variety of dimension at most k. We apply these equations to the Mulmuley-Sohoni variety, the GL_ n^2 orbit closure of the determinant, showing it is an irreducible component of the variety of hypersurfaces of degree n in C^ n^2 with dual of dimension at most 2n-2. We establish additional geometric properties of the Mulmuley-Sohoni variety and prove a quadratic lower bound for the determinantal border-complexity of the permanent. The permanent versus determinant conjecture is a major problem in complexity theory that is equivalent to the separation of the complexity classes VP_ ws and VNP. Mulmuley and Sohoni (SIAM J. Comput., 2001) suggested to study a strengthened version of this conjecture over the complex numbers that amounts to separating the orbit closures of the determinant and padded permanent polynomials. In that paper it was also proposed to separate these orbit closures by exhibiting occurrence obstructions, which are irreducible representations of GL_ n^2 (C), which occur in one coordinate ring of the orbit closure, but not in the other. We prove that this approach is impossible. However, we do not rule out the general approach to the permanent versus determinant problem via multiplicity obstructions as proposed by Mulmuley and Sohoni. Given an n × m nonnegative matrix A = (a ij ) and positive integral vectors r e ℜ n and c e Âm having a common one-norm h, the (r,c)-scaling problem is to obtain positive diagonal matrices X and Y, if they exist, such that XAY has row and column sums equal to r and c, respectively. The entropy minimization problem corresponding to A is to find an n × m matrix z = (z ij ) having the same zero pattern as A, the sum of whose entries is a given number h, its row and column sums are within given integral vectors of lower and upper bounds, and such that the entropy function consisting of the sum of the terms z ij ln (z ij a ij ) is minimized. When the lower and upper bounds coincide, matrix scaling and entropy minimization are closely related. In this paper we present several complexity bounds for the e-approximate (r,c)-scaling problem, polynomial in n,m,h, 1 e, and ln V v, where V and v are the largest and the smallest positive entries of A, respectively. These bounds, although not polynomial in ln(1 1 e), not only provide alternative complexities for the polynomial time algorithms, but could result in better overall complexities. In particular, our theoretical analysis supports the practicality of the well-known RAS algorithm. In our analysis we obtain bounds on the norm of scaling vectors which will be used in deriving not only some of the above complexities, but also a complexity for square nonnegative matrices having positive permanent. In particular, our results extend, nontrivially, many bounds for the doubly stochastic scaling of square nonnegative matrices previously given by Kalantari and Khachiyan to the case of general (r,c)-scaling. Finally, we study a more general entropy minimization problem where row and column sums are constrained to lie in prescribed intervals, and the sum of all entries is also prescribed. Balinski and Demange described an RAS type algorithm for its continuous version, but did not analyze its complexity. We show that this algorithm produces an 1 e-approximate solution within complexity polynomial in n, m, h, V v and 1 1 e. In this paper, we consider conic programming problems whose constraints consist of linear equalities, linear inequalities, a nonpolyhedral cone, and a polyhedral cone. A convenient way for solving this class of problems is to apply the directly extended alternating direction method of multipliers (ADMM) to its dual problem, which has been observed to perform well in numerical computations but may diverge in theory. Ideally, one should find a convergent variant which is at least as efficient as the directly extended ADMM in practice. We achieve this goal by designing a convergent semiproximal ADMM (called sPADMM3c for convenience) for convex programming problems having three separable blocks in the objective function with the third part being linear. At each iteration, the proposed sPADMM3c takes one special block coordinate descent (BCD) cycle with the order @math , instead of the usual @math Gauss--Seidel BCD cycle used in the nonconvergent directly extended 3-block ADMM, for updating the variable blocks. Our numerical experiments demonstrate that the convergent method is at least 20 faster than the directly extended ADMM with unit step-length for the vast majority of about 550 large-scale doubly nonnegative semidefinite programming problems with linear equality and or inequality constraints. This confirms that at least for conic convex programming, one can design a convergent and efficient ADMM with a special BCD cycle of updating the variable blocks.