Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > GIL KALAI:
All reports by Author Gil Kalai:

TR26-326 | 16th November 2026
Gil Kalai, Mrinal Kumar, Ben Lee Volk

Möbius-Pseudorandomness for Algebraic Circuits

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 ... more >>>




ISSN 1433-8092 | Imprint