Tag - Complexity theory

Computing the (real) roots of polynomial is an important problem in mathematics and theoretical computer science. We propose an efficient algorithm to compute the real roots of a sparse polynomial having k non-zero real-valued coefficients. It is known that even for 4-nomials, one can not hope for a polynomial (in the input size) time algorithm for isolating the real roots. Therefore we propose a slightly relaxed notion of isolation of real roots. For a given positive integer L, our algorithm returns disjoint disks D₁,D₂,...,D_s with s<2k, centred at the real axis and of radius less than 2^−L together with positive integers u₁,...,u_s such that each disk D_i contains exactly u_i roots of f counted with multiplicity. In addition, it is ensured that each real root of f is contained in one of the disks. If f has only simple real roots, our algorithm can also be used to isolate all real roots.The bit complexity of our algorithm is polynomial in k and log(n),and near-linear in L and τ, where 2^−τ and 2^τ constitute lower and upper bounds on the absolute values of the non-zero coefficients of f, and n is the degree of f. For root isolation, the bit complexity is polynomial in k and log(n), and near-linear in τ and log(1/σ), where σ denotes the separation of the real roots. We also show that the roots of integer trinomials are well separated (this was also independently proved by Koiran). By using our algorithm, it follows that the real roots of trinomials can be isolated in polynomial time.

We consider the special class of ideals where each generator is a univariate p_i over the variable x_i. First we show a randomized O(d^r poly(n)) algorithm for testing if a rank r polynomial is in a univariate ideal or not.

In a special case this lends itself to an algorithm for computing the Permanent of a matrix of rank r which works over all fields and generalizes a result of Barvinok. Next we discuss a result of Glynn that states that the Permanent of an n×n matrix of rank r is 0 modulo p when p<n/r and we prove a a more general theorem.

When the univariate ideal has only repeated roots we show a randomized O∗(4.08^d) algorithm where d is the degree of the input polynomial. When the generators of the ideal have distinct roots and the input polynomial is a depth 3 circuit we show a deterministic O∗(4^d) algorithm where d is the degree of the input polynomial.

The Unique Games Conjecture, proposed by Subhash Khot [Khot 2002], is a complexity theoretic assumption that if true yields optimal inapproximability results of several optimization problems. Since it was proposed in 2002, the theoretical computer science community has spent equal effort in proving and refuting the conjecture and till recently were evenly divided in their belief in the conjecture. Recently, in a remarkable sequence of 4 papers, 5 researchers (Minzer, Khot, Safra, Dinur and Kindler) proved a weaker version of the conjecture, called the 2-to-2 Games conjecture (or now, the 2-to-2 Games Theorem).

At the heart of their proof is a study of the Grassmann Graph and its expansion properties. The Grassmann Graph is a graph whose vertices are k-dimensional subspaces of GF(2)^m and two subspaces are connected if they intersect on a (k-1)-dimensional subspace. This graph is known to have several small structured sets that do not expand. A crucial element of the proof goes towards showing that any set that does not have such an algebraic structure does in fact expand. In this survey talk, I'll explain the UGC conjecture, its implications, the 2-to-2 Games Theorem, the Grassmann Graph, its expansion properties and some keys steps in the proof.

No background (but for a familiarity with complexity theory) will be assumed.

The Unique Games Conjecture, proposed by Subhash Khot [Khot 2002], is a complexity theoretic assumption that if true yields optimal inapproximability results of several optimization problems. Since it was proposed in 2002, the theoretical computer science community has spent equal effort in proving and refuting the conjecture and till recently were evenly divided in their belief in the conjecture. Recently, in a remarkable sequence of 4 papers, 5 researchers (Minzer, Khot, Safra, Dinur and Kindler) proved a weaker version of the conjecture, called the 2-to-2 Games conjecture (or now, the 2-to-2 Games Theorem).

At the heart of their proof is a study of the Grassmann Graph and its expansion properties. The Grassmann Graph is a graph whose vertices are k-dimensional subspaces of GF(2)^m and two subspaces are connected if they intersect on a (k-1)-dimensional subspace. This graph is known to have several small structured sets that do not expand. A crucial element of the proof goes towards showing that any set that does not have such an algebraic structure does in fact expand. In this survey talk, I'll explain the UGC conjecture, its implications, the 2-to-2 Games Theorem, the Grassmann Graph, its expansion properties and some keys steps in the proof.

No background (but for a familiarity with complexity theory) will be assumed.

It is a long-standing open problem in computer algebra to find a deterministic polynomial-time algorithm that factorizes a given univariate polynomial f(X) over a finite field 𝔽_p. Such an algorithm is not known even under the generalized Riemann hypothesis (GRH). In this talk, I will discuss a unifying approach for this problem based on a family of combinatorial objects called P-schemes. Our approach subsumes known GRH-based results and also leads to some new results. In particular, we show how to beat Evdokimov's algorithm when a polynomial f̃ (X)∈ℤ[X] lifting f(X) is given whose Galois group has a "linear" structure.

Algebraic Branching Programs (ABPs) whose computational power is encapsulated between that of arithmetic formulas and arithmetic circuits are standard models for computing polynomials. The absence of considerable progress on proving lower bounds for ABPs calls for further restrictions such as homogeneity and mutlilnearity. An ABP is said to be a syntactic multilinear ABP (smABP) if every variable appears as an edge label at most once on any path from source to sink. The best known size lower bound for smABPs is barely quadratic in the number of variables. Obtaining super-polynomial lower bounds for smABPs remains to be a challenging open problem in algebraic complexity theory.

By a simple divide and conquer approach, any smABP of polynomial size can be converted into an equivalent multilinear formula with a super-polynomial blow up in size. A crucial observation is that, although the above conversion of an smABP into a multilinear formula blows up the size, the resulting formula has far more structure than an arbitrary multilinear formula of super-polynomial size. In this talk, we try to identify and exploit the structural limitations of multilinear formulas thus obtained from smABPs. Using a finer analysis of these multilinear formulas, we outline a few approaches to prove super-polynomial lower bounds for smABPs.

It is a fundamental problem in the study of computational complexity to understand if access to more resources would mean strictly more computational power. In classical complexity, we have seen such examples in terms of Time Hierarchy and Space Hierarchy theorems. Here, time and space are the resources. It is natural to ask such a question in the setting of algebraic complexity setting. Here, access to more resources translates to allowing the model to perform more number of operations which in turn is allowing the "algebraic formulas" to have larger size.

Arithmetic formulas are directed trees where the leaves are labelled by variables and elements of the field, and internal vertices are labelled by + or x. Every internal vertex computes a polynomial by operating on its inputs. It is easy to see that they are a natural model of computation of polynomials, syntactically (symbolically). The size of the arithmetic formulas refers to the number of + and x operations needed to compute the polynomial. Rephrasing the question in the algebraic setting we ask the following: for any s, ε > 0, are there polynomial computations that can be efficiently computed by arithmetic formulas of size s but not by any arithmetic formula of size s^1-ε?

In this talk, we will restrict ourselves to arithmetic formulas where computation at every vertex is a multilinear polynomial and here we show explicit separations between the expressive powers of multilinear formulas of small-depth and all polynomial sizes. The multilinear restriction is a reasonable one since most polynomials of interest are indeed multilinear. Formally, we will show that for any s = poly(n) and δ > 0, we show that there are explicit polynomial families that have multilinear formulas of size at most s but no 'small'-depth multilinear formulas of size less than s^{0.5 - δ}. Our proof can be viewed as a derandomization of a lower bound technique of Raz (JACM 2009) using ε-biased spaces.

In this talk we will see recent optimization based algorithms for the null-cone problem and the orbit closure intersection problem for the left-right action, and how these problems from invariant theory relate to a Polynomial Identity Testing for a restricted class of arithmetic circuits.