Symmetric polynomials over Z_m and simultaneous communication protocols

DOI10.1016/J.JCSS.2005.06.007MaRDI QIDQ2490262zbMATH OpenOpenAlexFDO

Authors Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Publication date 28 April 2006

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2005.06.007

Mathematics Subject Classification ID

Boolean functions (06E30) Network protocols (68M12)

Recommendations

• Symmetric polynomials over finite fields
• scientific article; zbMATH DE number 2113272
• Communication complexity and orthogonal polynomials
• Communication-avoiding symmetric-indefinite factorization
• Symmetric bilinear forms over finite fields with applications to coding theory
• On the Communication Complexity of Solving a Polynomial Equation
• On the complexity of symmetric polynomials
• Symmetric polynomials and some good codes
• Codes from symmetric polynomials
• Communication complexities of symmetric XOR functions

Cites work

• A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
• A lower bound on the MOD 6 degree of the OR function
• Communication Complexity
• scientific article; zbMATH DE number 1332656 (Why is no real title available?)
• scientific article; zbMATH DE number 1114507 (Why is no real title available?)
• scientific article; zbMATH DE number 2115025 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• scientific article; zbMATH DE number 3032896 (Why is no real title available?)
• Lower Bounds on Representing Boolean Functions as Polynomials in Z_m
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On an irreducibility theorem of I. Schur
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Representing Boolean functions as polynomials modulo composite numbers
• Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs

Cited in

(5)

• Block-symmetric polynomials correlate with parity better than symmetric
• A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
• A lifting theorem with applications to symmetric functions
• On the modulo degree complexity of Boolean functions
• Fourier conjectures, correlation bounds, and majority

This page was built for publication: Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2490262)