License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.3
URN: urn:nbn:de:0030-drops-182734
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18273/
Go to the corresponding LIPIcs Volume Portal

Ivanov, Peter ; Pavlovic, Liam ; Viola, Emanuele

On Correlation Bounds Against Polynomials

pdf-format:
LIPIcs-CCC-2023-3.pdf (0.8 MB)

Abstract

We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over ?₂. Our main contributions include:
1) In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their technique generalizes to higher degree polynomials as well. We give a counterexample to their conjecture, in fact ruling out weaker parameters and showing what they prove is essentially the best possible.
2) We propose a new approach for proving correlation bounds with the central "mod functions," consisting of two steps: (I) the polynomials that maximize correlation are symmetric and (II) symmetric polynomials have small correlation. Contrary to related results in the literature, we conjecture that (I) is true. We argue this approach is not affected by existing "barrier results."
3) We prove our conjecture for quadratic polynomials. Specifically, we determine the maximum possible correlation between quadratic polynomials modulo 2 and the functions (x_1,… ,x_n) → z^{∑ x_i} for any z on the complex unit circle, and show that it is achieved by symmetric polynomials. To obtain our results we develop a new proof technique: we express correlation in terms of directional derivatives and analyze it by slowly restricting the direction.
4) We make partial progress on the conjecture for cubic polynomials, in particular proving tight correlation bounds for cubic polynomials whose degree-3 part is symmetric.

BibTeX - Entry

@InProceedings{ivanov_et_al:LIPIcs.CCC.2023.3,
  author =	{Ivanov, Peter and Pavlovic, Liam and Viola, Emanuele},
  title =	{{On Correlation Bounds Against Polynomials}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{3:1--3:35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18273},
  URN =		{urn:nbn:de:0030-drops-182734},
  doi =		{10.4230/LIPIcs.CCC.2023.3},
  annote =	{Keywords: Correlation bounds, Polynomials}
}

Keywords: Correlation bounds, Polynomials
Collection: 38th Computational Complexity Conference (CCC 2023)
Issue Date: 2023
Date of publication: 10.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI