Paperlane

no. 16 · Tuesday 17 November 2026

Möbius-Pseudorandomness for Algebraic Circuits

Gil Kalai, Mrinal Kumar and Ben Lee Volk

math.NT · via cs.CC

Abstract

We define a notion of Möbius-pseudorandomness for integer sequences generated by multivariate polynomials computed by small and simple algebraic circuits. This mirrors a related definition of Kalai that concerns boolean functions computed by small boolean circuits. We then prove Möbius-pseudorandomness results for polynomials computed by algebraic circuits with few multiplication gates (of any depth), for polynomials with small-dimensional partial derivative space, and for the determinant and permanent. We conjecture that these results hold in general for polynomial-size algebraic circuits.

fields
Number Theory
pdf ↗ page arXiv:2611.21201 ↗