Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-158 | 8th December 2006 00:00

Representing Boolean OR function by quadratic polynomials modulo 6

RSS-Feed




TR06-158
Authors: Gyula Gyôr
Publication: 16th December 2006 20:21
Downloads: 1620
Keywords: 


Abstract:

We give an answer to the question of Barrington, Beigel and Rudich, asked in 1992, concerning the largest n such that the OR function of n variable can be weakly represented by a quadratic polynomial modulo 6. More specially,we show that no 11-variable quadratic polynomial exists that is congruent to zero modulo 6 in the all-0 input and non-zero modulo 6 anywhere else on the {0,1} input.



ISSN 1433-8092 | Imprint