Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-314 | 9th November 2026 17:27

Polynomial-size hitting sets for multilinear any-order read-once algebraic branching programs and for set-multilinear depth-$3$ circuits with constant-size variable sets

RSS-Feed




TR26-314
Authors: Amir Shpilka
Publication: 9th November 2026 17:32
Downloads: 57
Keywords: 


Abstract:

In this paper we give polynomial-size hitting sets for multilinear any-order read-once oblivious algebraic branching programs and for depth-$3$ set-multilinear circuits where each variable set has constant size. Our results also extend to the border of both classes and hold over fields of any characteristic.

The proof combines the approach of Forbes, Saptharishi and Shpilka (STOC 2014) with the recent results of Bhardwaj and Saptharishi (2026) and of Bal and Ghosh (2026) that gave polynomial-size hitting sets for polynomials with small partial derivative dimension.



ISSN 1433-8092 | Imprint