4

Fooling polynomials using invariant theory

 1 year ago
source link: https://ieeexplore.ieee.org/document/9996652
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Fooling polynomials using invariant theory

IEEE websites place cookies on your device to give you the best user experience. By using our websites, you agree to the placement of these cookies. To learn more, read our Privacy Policy.
Loading [MathJax]/extensions/MathMenu.js

Skip to Main Content

Abstract:
We revisit the problem of constructing explicit pseudorandom generators that fool with error ϵ degree-d polynomials in n variables over the field F q , in the case of large q. Previous constructions either have seed length ≥2dlogq, and thus are only non-trivial when d<logn, or else rely on a seminal reduction by Bogdanov (STOC 2005). This reduction yields seed length not less than d4logn+logq and requires fields of size q≥d6/ϵ2; and explicit generators meeting such bounds are known.Departing from Bogdanov’s reduction, we develop an algebraic analogue of the Bogdanov-Viola paradigm (FOCS 2007, SICOMP 2010) of summing generators for degree-one polynomials. Whereas previous analyses of the paradigm are restricted to degree d<logn, we give a new analysis which handles large degrees. A main new idea is to show that the construction preserves indecomposability of polynomials. Apparently for the first time in the area, the proof uses invariant theory.Our approach in particular yields several new pseudorandom generators. In particular, for large enough fields we obtain seed length O(dlogn+logq) which is optimal up to constant factors. We also construct generators for fields of size as small as O(d4). Further reducing the field size requires a significant change in techniques: Most or all generators for large-degree polynomials rely on Weil bounds; but such bounds are only applicable when q>d4
Date of Conference: 31 October 2022 - 03 November 2022
Date Added to IEEE Xplore: 28 December 2022
ISBN Information:
ISSN Information:
INSPEC Accession Number: 22448602
Publisher: IEEE
Conference Location: Denver, CO, USA

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK