Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with GF(2) polynomial:
TR06-097 | 9th August 2006
Emanuele Viola

New correlation bounds for GF(2) polynomials using Gowers uniformity

We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following:

(I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the ... more >>>

TR20-104 | 12th July 2020
Oded Goldreich

On Counting $t$-Cliques Mod 2

Revisions: 3

For a constant integer $t$, we consider the problem of counting the number of $t$-cliques $\bmod 2$ in a given graph.
We show that this problem is not easier than determining whether a given graph contains a $t$-clique, and present a simple worst-case to average-case reduction for it. The ... more >>>

ISSN 1433-8092 | Imprint