On the correlation between parity and modular polynomials

DOI10.1007/S00224-011-9332-9MaRDI QIDQ692898zbMATHOpenAlexFDO

Authors Anna Gál, Vladimir Trifonov

Publication date 6 December 2012

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-011-9332-9

zbMATH Keywords

correlationmodular polynomialscircuit complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the Correlation Between Parity and Modular Polynomials
• The correlation between parity and quadratic polynomials mod \(3\)
• Uniqueness of optimal mod 3 polynomials for parity
• Correlation lower bounds from correlation upper bounds
• Lower bounds for depth-three circuits with equals and Mod-gates

Cites work

• scientific article; zbMATH DE number 3131973 (Why is no real title available?)
• scientific article; zbMATH DE number 4023423 (Why is no real title available?)
• A note on the power of majority gates and modular gates
• A weight-size trade-off for circuits with MOD \(m\) gates
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds on an exponential sum arising in Boolean circuit complexity
• Estimation of certain exponential sums arising in complexity theory
• Exponential sums and circuits with a single threshold gate and mod-gates
• Lower Bounds for (MOD_p - MOD_m) Circuits
• Mathematical Foundations of Computer Science 2004
• On the computational power of depth 2 circuits with threshold and modulo gates
• On the correlation of symmetric functions
• On the power of small-depth threshold circuits
• Parity, circuits, and the polynomial-time hierarchy
• Threshold circuits of bounded depth
• Upper and lower bounds for some depth-3 circuit classes
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom

Cited in

(6)

• Estimation of certain exponential sums arising in complexity theory
• Block-symmetric polynomials correlate with parity better than symmetric
• On the Correlation Between Parity and Modular Polynomials
• The correlation between parity and quadratic polynomials mod \(3\)
• scientific article; zbMATH DE number 7250146 (Why is no real title available?)
• Uniqueness of optimal mod 3 polynomials for parity

This page was built for publication: On the correlation between parity and modular polynomials

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