Abstract Logarithmic space-bounded complexity classes such as $$\textbf{L} $$ L and $$\textbf{NL} $$ NL play a central role in space-bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the structure of computational problems such as computing the determinant and counting paths in directed acyclic graphs. Though parameterised complexity theory was initiated roughly three decades ago by Downey and Fellows, a satisfactory study of parameterised logarithmic space-bounded computation was developed only in the last decade by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space-bounded models developed by Elberfeld, Stockhusen and Tantau. They defined the operators $$\textbf{para}_{\textbf{W}}$$ paraW and $$\textbf{para}_\beta $$ paraβ for parameterised space complexity classes by allowing bounded nondeterminism with multiple-read and read-once access, respectively. Using these operators, they characterised the parameterised complexity of natural problems on graphs. In the spirit of the operators $$\textbf{para}_{\textbf{W}}$$ paraW and $$\textbf{para}_\beta $$ paraβ by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, $$\textbf{para}_{{\textbf{W}}[1]}$$ paraW[1] and $$\textbf{para}_{\beta {\textbf{tail}}}$$ paraβtail . Then, we consider counting versions of all four operators and apply them to the class $$\textbf{L} $$ L . We obtain several natural complete problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0, 1)-matrices is $$\#\textbf{para}_{\beta {\textbf{tail}}}\textbf{L} $$ #paraβtailL -hard and can be written as the difference of two functions in $$\#\textbf{para}_{\beta {\textbf{tail}}}\textbf{L} $$ #paraβtailL . These problems exhibit the richness of the introduced counting classes. Our results further indicate interesting structural characteristics of these classes. For example, we show that the closure of $$\#\textbf{para}_{\beta {\textbf{tail}}}\textbf{L} $$ #paraβtailL under parameterised logspace parsimonious reductions coincides with $$\#\textbf{para}_\beta \textbf{L} $$ #paraβL . In other words, in the setting of read-once access to nondeterministic bits, tail-nondeterminism coincides with unbounded nondeterminism modulo parameterised reductions. Initiating the study of closure properties of these parameterised logspace counting classes, we show that all introduced classes are closed under addition and multiplication, and those without tail-nondeterminism are closed under parameterised logspace parsimonious reductions. Finally, we want to emphasise the significance of this topic by providing a promising outlook highlighting several open problems and directions for further research.

We consider the problem of obtaining parameterized lower bounds for the size of arithmetic circuits computing polynomials with the degree of the polynomial as the parameter. We consider the following special classes of multilinear algebraic branching programs: 1) Read Once Oblivious Branching Programs (ROABPs), 2) Strict interval branching programs, 3) Sum of read once formulas with restricted ordering. We obtain parameterized lower bounds (i.e., n Ω( t( k)) lower bound for some function t of k) on the size of the above models computing a multilinear polynomial that can be computed by a depth four circuit of size g( k) n O(1) for some computable function g. Further, we obtain a parameterized separation between ROABPs and read-2 ABPs. This is obtained by constructing a degree k polynomial that can be computed by a read-2 ABP of small size such that the rank of the partial derivative matrix under any partition of the variables is large.

Proving super-polynomial lower bounds on the size of syntactic multilinear Algebraic Branching Programs (smABPs) computing an explicit polynomial is a challenging problem in Algebraic Complexity Theory. The order in which variables in {x_1,...,x_n} appear along any source to sink path in an smABP can be viewed as a permutation in S_n. In this article, we consider the following special classes of smABPs where the order of occurrence of variables along a source to sink path is restricted: 1) Strict circular-interval ABPs: For every sub-program the index set of variables occurring in it is contained in some circular interval of {1,..., n}. 2) L-ordered ABPs: There is a set of L permutations (orders) of variables such that every source to sink path in the smABP reads variables in one of these L orders, where L <=2^{n^{1/2 -epsilon}} for some epsilon>0. We prove exponential (i.e., 2^{Omega(n^delta)}, delta>0) lower bounds on the size of above models computing an explicit multilinear 2n-variate polynomial in VP. As a main ingredient in our lower bounds, we show that any polynomial that can be computed by an smABP of size S, can be written as a sum of O(S) many multilinear polynomials where each summand is a product of two polynomials in at most 2n/3 variables, computable by smABPs. As a corollary, we show that any size S syntactic multilinear ABP can be transformed into a size S^{O(sqrt{n})} depth four syntactic multilinear Sigma Pi Sigma Pi circuit where the bottom Sigma gates compute polynomials on at most O(sqrt{n}) variables. Finally, we compare the above models with other standard models for computing multilinear polynomials.

We study limitations of polynomials computed by depth two circuits built over read-once formulas (ROFs). In particular, 1. We prove an exponential lower bound for the sum of ROFs computing the 2n-variate polynomial in VP defined by Raz and Yehudayoff [CC,2009]. 2. We obtain an exponential lower bound on the size of arithmetic circuits computing sum of products of restricted ROFs of unbounded depth computing the permanent of an n by n matrix. The restriction is on the number of variables with + gates as a parent in a proper sub formula of the ROF to be bounded by sqrt(n). Additionally, we restrict the product fan in to be bounded by a sub linear function. This proves an exponential lower bound for a subclass of possibly non-multilinear formulas of unbounded depth computing the permanent polynomial. 3. We also show an exponential lower bound for the above model against a polynomial in VP. 4. Finally we observe that the techniques developed yield an exponential lower bound on the size of sums of products of syntactically multilinear arithmetic circuits computing a product of variable disjoint linear forms where the bottom sum gate and product gates at the second level have fan in bounded by a sub linear function. Our proof techniques are built on the measure developed by Kumar et al.[ICALP 2013] and are based on a non-trivial analysis of ROFs under random partitions. Further, our results exhibit strengths and provide more insight into the lower bound techniques introduced by Raz [STOC 2004].

Euclidean optimization problems such as TSP and minimum-length matching admit fast partitioning algorithms that compute near-optimal solutions on typical instances. In order to explain this performance, we develop a general framework for the application of smoothed analysis to partitioning algorithms for Euclidean optimization problems. Our framework can be used to analyze both the running-time and the approximation ratio of such algorithms. We apply our framework to obtain smoothed analyses of Dyer and Frieze’s partitioning algorithm for Euclidean matching, Karp’s partitioning scheme for the TSP, a heuristic for Steiner trees, and a heuristic for degree-bounded minimum-length spanning trees.

In this paper, we study the isomorphism testing problem of formulas in the Boolean and arithmetic settings. We show that isomorphism testing of Boolean formulas in which a variable is read at most once (known as read-once formulas) is complete for log-space. In contrast, we observe that the problem becomes polynomial time equivalent to the graph isomorphism problem, when the input formulas can be represented as OR of two or more monotone read-once formulas. This classifies the complexity of the problem in terms of the number of reads, as read-3 formula isomorphism problem is hard for \co\NP. We address the polynomial isomorphism problem, a special case of polynomial equivalence problem which in turn is important from a cryptographic perspective[Patarin EUROCRYPT'96, and Kayal SODA'11]. As our main result, we propose a deterministic polynomial time canonization scheme for polynomials computed by constant-free read-once arithmetic formulas. In contrast, we show that when the arithmetic formula is allowed to read a variable twice, this problem is as hard as the graph isomorphism problem.