On the correlation of symmetric functions
From MaRDI portal
Publication:4879208
DOI10.1007/BF01201278zbMath0858.94033OpenAlexW1982026196MaRDI QIDQ4879208
Frederic Green, Jin-Yi Cai, Thomas Thierauf
Publication date: 9 September 1996
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01201278
Symmetric functions and generalizations (05E05) Boolean functions (06E30) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10)
Related Items (25)
Correlation lower bounds from correlation upper bounds ⋮ The correlation between parity and quadratic polynomials mod \(3\) ⋮ Generalized Walsh transforms of symmetric and rotation symmetric Boolean functions are linear recurrent ⋮ Walsh-Hadamard transforms of generalized \(p\)-ary functions and \(C\)-finite sequences ⋮ Hamming weights of symmetric Boolean functions ⋮ Generalized exponential sums and the power of computers ⋮ Block-symmetric polynomials correlate with parity better than symmetric ⋮ Quantum and classical query complexities for generalized Deutsch-Jozsa problems ⋮ Asymptotic behavior of perturbations of symmetric functions ⋮ Short \(k\)-rotation symmetric Boolean functions ⋮ Unnamed Item ⋮ Hadamard matrices and the spectrum of quadratic symmetric polynomials over finite fields ⋮ Modular periodicity of exponential sums of symmetric Boolean functions ⋮ Recursions associated to trapezoid, symmetric and rotation symmetric functions over Galois fields ⋮ Uniqueness of optimal mod 3 polynomials for parity ⋮ On the correlation between parity and modular polynomials ⋮ Estimation of certain exponential sums arising in complexity theory ⋮ Sensitivities and block sensitivities of elementary symmetric Boolean functions ⋮ Value distribution of elementary symmetric polynomials and its perturbations over finite fields ⋮ Unnamed Item ⋮ Closed formulas for exponential sums of symmetric polynomials over Galois fields ⋮ Certificate complexity of elementary symmetric Boolean functions ⋮ A Lifting Theorem with Applications to Symmetric Functions ⋮ Certificate complexity and symmetry of nested canalizing functions ⋮ Incomplete quadratic exponential sums in several variables
Cites Work
- Unnamed Item
- An oracle separating \(\oplus P\) from \(PP^{PH}\)
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Random oracles separate PSPACE from the polynomial-time hierarchy
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- Equations over finite fields. An elementary approach
- Representing Boolean functions as polynomials modulo composite numbers
- Parity, circuits, and the polynomial-time hierarchy
This page was built for publication: On the correlation of symmetric functions
