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-125 | 24th July 2026 11:13

Lifting Polynomial Complexity Measures Using Error-Correcting Codes

RSS-Feed




TR26-125
Authors: Ivan Hu, Dieter van Melkebeek
Publication: 24th July 2026 11:14
Downloads: 49
Keywords: 


Abstract:

We describe a method that lifts an arbitrary polynomial $f$ with sparsity $s$ to a polynomial that requires a read-once oblivious algebraic program of width $s$ for every variable order. To do so, we introduce a technique for constructing a gadget based on erasure codes over finite fields, where each variable in $f$ is substituted with a monomial that encodes a codeword into the exponents of the monomial. To the best of our knowledge, our construction represents the first use of error-correcting codes in the context of lifting. As an application, we consider factor complexity, which studies how much the complexity of a polynomial can increase under factorization. Our result allows us to lift any gap in sparsity to the same gap in width in a generic manner.



ISSN 1433-8092 | Imprint