Hard functions for low-degree polynomials over prime fields

DOI10.1145/2493246.2493248MaRDI QIDQ5892189zbMATH OpenOpenAlexFDO

Authors Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka

Publication date 24 September 2015

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2493246.2493248

zbMATH Keywords

property testinglow-degree polynomialshardness amplification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Hard functions for low-degree polynomials over prime fields
• Testing low-degree polynomials over prime fields
• Inverse conjecture for the Gowers norm is false
• Optimal testing of multivariate polynomials over small prime fields
• Low-degree tests at large distances

Cited in

(2)

• Improved Extractors for Recognizable and Algebraic Sources
• Hard functions for low-degree polynomials over prime fields

This page was built for publication: Hard functions for low-degree polynomials over prime fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892189)