Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BOOLEAN DERIVATIVES:
Reports tagged with Boolean derivatives:
TR26-083 | 27th April 2026
Nicholas Smirnov

Boolean Derivative Certificates and Maximal ANF Terms

For a Boolean function $f:\{0,1\}^n\to\{0,1\}$, the higher-order Boolean derivative $D_S f$ computes the parity of $f$ over each $S$-dimensional subcube. We prove that $D_S f\equiv 1$ exactly when $S$ is a maximal monomial support in the algebraic normal form of $f$. This correspondence motivates the derivative certificate depth $\Delta_\partial(f)$, defined ... more >>>




ISSN 1433-8092 | Imprint