2026-09-10T09:44:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27781 2026-09-09T12:19:38Z ddc:004 open_access

Lifting Polynomial Complexity Measures Using Error-Correcting Codes Hu, Ivan van Melkebeek, Dieter lifting lower bound error-correcting code read-once oblivious algebraic branching program polynomial factorization 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. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ivan Hu and Dieter van Melkebeek 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.64 urn:nbn:de:0030-drops-277813 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.64 eng https://creativecommons.org/licenses/by/4.0/legalcode