- Authors: I. Hu and D. van Melkebeek
- Reference: In Proceedings of the 30th International Conference on Randomization and Computation, pages 64:1-64:10, 2026.
- Other versions:
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.
