Counting Small Induced Subgraphs: Hardness via Fourier Analysis

For a fixed graph property Phi and integer k ≥ 1, consider the problem of counting the induced k-vertex subgraphs satisfying Phi in an input graph G. This problem can be solved by brute-force in time O(nk). Under ETH, we prove several lower bounds on the optimal exponent in this running time: If Phi is edge-monotone (i.e., closed under deleting edges), then ETH rules out no(k) time algorithms for this problem. This strengthens a recent lower bound by D"oring, Marx and Wellnitz [STOC 2024]. Our result also holds for counting modulo fixed primes. If at most (2-varepsilon)^binomk2 graphs on k vertices satisfy Phi, for some varepsilon > 0, then ETH also rules out an exponent of o(k). This holds even when the graphs in Phi have arbitrary individual weights, generalizing previous results for hereditary properties by Focke and Roth [SIAM J. Comput. 2024]. If Phi is non-trivial and excludes β_Phi edge-densities, then the optimal exponent under ETH is Omega(β_Phi). This holds even when the graphs in Phi have arbitrary individual weights, generalizing previous results by Roth, Schmitt and Wellnitz [SIAM J. Comput. 2024]. In all cases, we also obtain mathsf#W[1]-hardness if k is part of the input and considered as the parameter. We also obtain lower bounds on the Weisfeiler-Leman dimension. As opposed to the nontrivial techniques from combinatorics, group theory, and simplicial topology used before, our results follow from a relatively straightforward ``algebraization'' of the problem in terms of polynomials, combined with applications of simple algebraic facts, which can also be interpreted in terms of Fourier analysis.