On the correlation between parity and modular polynomials

DOI10.1007/s00224-011-9332-9zbMath1279.68098OpenAlexW2015506363MaRDI QIDQ692898

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

correlationcircuit complexitymodular polynomials

Mathematics Subject Classification ID

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

Related Items

Unnamed Item

Cites Work

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

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