Budapest Problem Exchange in Mathematics                                    Problem No. 1

Area: Theoretical Computer Science, Complexity Theory, Combinatorics, Algebra

Title: MOD 6 polynomial representation of the OR function

Problem Description: Let d=d(n) denote the smallest integer, such that there exists a degree-d polynomial tex2html_wrap_inline65, which is 0 modulo 6 if tex2html_wrap_inline69, and non-zero modulo 6, if tex2html_wrap_inline71.

How large is d(n)?

Background: It is easy to prove, that for prime moduli, instead of modulus 6, tex2html_wrap_inline75.

By [1], tex2html_wrap_inline77, and by [4], tex2html_wrap_inline79. The upper bound is known to be optimal if P is a symmetric polynomial [1].

If we were able to construct a P with degree less than tex2html_wrap_inline85, then it would yield a larger Ramsey-graph construction than is currently known [3].

Contact person: Vince Grolmusz (grolmusz@cs.elte.hu)

Posted by: Vince Grolmusz (grolmusz@cs.elte.hu)
 
 

Originated from: [2], [1]



References

1
 D. A. M. Barrington, R. Beigel, and S. Rudich. Representing Boolean functions as polynomials modulo composite numbers. Comput. Complexity, 4:367-382, 1994. Appeared also in Proc. 24th Ann. ACM Symp. Theor.\ Comput., 1992.
2
 D. A. M. Barrington, H. Straubing, and D. Thérien. Non-uniform automata over groups. Information and Computation, 89:109-132, 1990.
3
 V. Grolmusz. On set systems with restricted intersections modulo a composite number. In Lecture Notes in Computer Science Vol. 1276, pages 82-90, August 1997. Presented at COCOON'97, Shanghai, China.
4
 G. Tardos and D. A. M. Barrington. A lower bound on the MOD 6 degree of the OR function. In Proceedings of the Third Israel Symosium on the Theory of Computing and Systems (ISTCS'95), pages 52-56, 1995.