We associate to each Boolean language complexity class \mathcal{C} the algebraic class a\cdot\mathcal{C} consisting of families of polynomials \{f_n\} for which the evaluation problem over the integers is in \mathcal{C}. We prove the following lower bound and randomness-to-hardness results:

1. If polynomial identity testing (PIT) is in NSUBEXP then $a\cdot ... more >>>

Suppose f is a univariate polynomial of degree r=r(n) that is computed by a size n arithmetic circuit.
It is a basic fact of algebra that a nonzero univariate polynomial of degree r can vanish on at most r points. This implies that for checking whether f is identically zero, ... more >>>

For two polynomials f \in \mathbb{F}[x_1, x_2, \ldots, x_n, y] and p \in \mathbb{F}[x_1, x_2, \ldots, x_n], we say that p is a root of f, if f(x_1, x_2, \ldots, x_n, p) \equiv 0. We study the relation between the arithmetic circuit sizes of f and p for general circuits ... more >>>

An algebraic branching program (ABP) is given by a directed acyclic graph with source and sink vertices s and t, respectively, and where edges are labeled by variables or field constants. An ABP computes the sum of weights of all directed paths from s to t, where the weight of ... more >>>

In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. Given a permutation \pi of n variables, for a \pi-ordered ABP (\pi-OABP), for any directed path p from source to sink, a variable can appear at ... more >>>