Depth-first search (DFS) is a very well-known graph traversal method which confers a number of structural properties that causes DFS to have numerous applications. These properties are captured in the DFS tree (forest), and are used to design efficient algorithms for many basic and fundamental algorithmic graph problems, namely, biconnectivity, 2-edge connectivity, topological sorting and planarity testing among many others. Recently, Chakraborty and Sadakane (MFCS 2019) studied the problem of compactly indexing the lexicographic DFS tree, and they showed various applications of this by designing an efficient index for shortest path, strongly connected component etc. Here, lexicographical means that the DFS algorithm chooses at every step the vertex that is unvisited and smallest in the lexicographical order of the vertices. Chakraborty and Sadakane presented their solution in two well-known models: The indexing and encoding models. In the indexing model, we wish to build an index$I$after preprocessing the input graph$G$such that queries can be answered using both$I$and$G$whereas in the encoding model, we seek to build a data structure$E$after preprocessing$G$such that the following queries have to be answered using only$E, (\mathrm{i})$return true if$t_{1}$is visited before$t_{0}$in the lexicographic DFS tree$T$rooted at$s$, and false otherwise, and (ii) return the number of children of any given node$v\in T$.

If $k

We define a theory of parameterized algebraic complexity classes in analogy to parameterized Boolean counting classes. We define the classes VFPT and VW[t], which mirror the Boolean counting classes #FPT and #W[t], and define appropriate reductions and completeness notions. Our main contribution is the VW[1]-completeness proof of the parameterized clique family. This proof is far more complicated than in the Boolean world. It requires some new concepts like composition theorems for bounded exponential sums and Boolean-arithmetic formulas. In addition, we also look at two polynomials linked to the permanent with vastly different parameterized complexity.

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth Δ + 1 to one of product-depth Δ in the multilinear setting. We show that for every positive Δ = Δ(n) = o(log n/log log n), there is an explicit multilinear polynomial P(Δ) on n variables that can be computed by a multilinear formula of product-depth Δ + 1 and size O(n), but not by any multilinear circuit of product-depth Δ and size less than exp(nΩ(1/Δ)). This result is tight up to the constant implicit in the double exponent for all Δ = o(log n/log log n). This strengthens a result of Raz and Yehudayoff (Computational Complexity 2009) who prove a quasipolynomial separation for constant-depth multilinear circuits, and a result of Kayal, Nair and Saha (STACS 2016) who give an exponential separation in the case Δ = 1. Our separating examples may be viewed as algebraic analogues of variants of the Graph Reachability problem studied by Chen, Oliveira, Servedio and Tan (STOC 2016), who used them to prove lower bounds for constant-depth Boolean circuits.

We construct a hitting set generator for sparse multivariate polynomials over the reals. The seed length of our generator is O(log^2 (mn/epsilon)) where m is the number of monomials, n is number of variables, and 1 - epsilon is the hitting probability. The generator can be evaluated in time polynomial in log m, n, and log 1/epsilon. This is the first hitting set generator whose seed length is independent of the degree of the polynomial. The seed length of the best generator so far by Klivans and Spielman [STOC 2001] depends logarithmically on the degree. From this, we get a randomized algorithm for testing sparse black box polynomial identities over the reals using O(log^2 (mn/epsilon)) random bits with running time polynomial in log m, n, and log(1/epsilon). We also design a deterministic test with running time ~O(m^3 n^3). Here, the ~O-notation suppresses polylogarithmic factors. The previously best deterministic test by Lipton and Vishnoi [SODA 2003] has a running time that depends polynomially on log delta, where $delta$ is the degree of the black box polynomial.