On the correlation between parity and modular polynomials
From MaRDI portal
Publication:692898
DOI10.1007/s00224-011-9332-9zbMath1279.68098MaRDI QIDQ692898
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
68Q25: Analysis of algorithms and problem complexity
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- 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 (MODp - MODm) Circuits
- Mathematical Foundations of Computer Science 2004
- Unnamed Item
- Unnamed Item
