On the correlation between parity and modular polynomials

DOI10.1007/S00224-011-9332-9zbMATH Open1279.68098OpenAlexW2015506363MaRDI QIDQ692898FDOQ692898

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

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

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)

Cites Work

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

Cited In (6)

• Block-symmetric polynomials correlate with parity better than symmetric
• Uniqueness of optimal mod 3 polynomials for parity
• Estimation of certain exponential sums arising in complexity theory
• Title not available (Why is that?)
• The correlation between parity and quadratic polynomials mod \(3\)
• On the Correlation Between Parity and Modular Polynomials

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)