On the correlation of symmetric functions

DOI10.1007/BF01201278zbMath0860.68045OpenAlexW1982026196MaRDI QIDQ4717052

Jin-Yi Cai, Zi-Cheng Liu

Publication date: 1 December 1996

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01201278

zbMATH Keywords

bounded membership problem

Mathematics Subject Classification ID

Matrix equations and identities (15A24) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Matrices of integers (15B36)

Related Items (3)

All \(\operatorname{SL}_{2}\)-tilings come from infinite triangulations ⋮ Recursions for modified Walsh transforms of some families of Boolean functions ⋮ Testing Boolean Functions Properties

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