A Simple Inclusion-Exclusion Based Algorithm for ( <i>k, n</i> )-MLC and Related Problems

We present a simple algorithm based on the inclusion-exclusion principle for computing the sum of the coefficients of all multilinear monomials in a polynomial computed by an arithmetic circuit over any field F . This problem is formally denoted as (k,n) -MLC and is defined as follows: — Given an arithmetic circuit computing a homogeneous polynomial \(f \in \mathbb {F}[x_1,\ldots ,x_n]\) of degree k , where \(\mathbb {F}\) is any field, compute the sum of the coefficients of all multilinear monomials in f . We provide a deterministic algorithm for the ( k,n )-MLC problem with a running time of \(O(n^{k/2} \cdot 2^{O(k)} \cdot s^{O(1)})\) , where s is the size of the circuit. Our algorithm is also polynomial space-bounded. The ( k,n )-MLC problem was first studied by Koutis and Williams [ 15 , 16 , 17 , 22 ] and later studied by Arvind et al., [ 3 ], where they obtain a deterministic algorithm with a running time of \(O^*({n\atopwithdelims (){\downarrow k/2}}\cdot s^{O(\log k)})\) 1 \(^,\) 2 using Hadamard product of polynomials. Pratt [ 18 ] proposed a deterministic algorithm that runs in \(O^*(n^{k/2})\) time, but this approach relies on a non-trivial Waring decomposition of symmetric polynomials over the rationals, which does not extend to small finite fields. Our method is notable for its simplicity and general applicability to all fields. In contrast to existing works, we introduce the complement of the ( k,n )-MLC problem, which we call the ( k,n )-NMLC problem. This approach looks at finding the sum of the coefficients of all non-multilinear monomials, which gives us a new way to think about the ( k,n )-MLC problem. This new method results in a simple algorithm and helps explain where the leading exponent \(k/2\) comes from. We develop a deterministic algorithm for the ( k,n )-NMLC problem that runs in \(O(n^{k/2} \cdot 2^{O(k)} \cdot s)\) time and uses polynomial space. The algorithm for the ( k,n )-MLC problem is straightforward: it subtracts the sum of the coefficients of all non-multilinear monomials (the result from the ( k,n )-NMLC problem) from the total sum of all monomial coefficients in the polynomial, which includes both multilinear and non-multilinear monomials. We apply these results to obtain a deterministic algorithm for the exact counting version of the r -simple k -path problem, as introduced in References [ 1 , 13 ], and also to a generalization of the ( k,n )-MLC problem, which we call the \((r,k,n)\) -MLC problem. This involves computing the sum of the coefficients of all monomials in the polynomial produced by the given arithmetic circuit, where the degree of each variable is at most r .