On the correlation between parity and modular polynomials
type: Item
instance of: scholarly article
title: On the correlation between parity and modular polynomials
zbMATH Open document ID: 1279.68098
author: Anna Gál
author: Vladimir Trifonov
published in: Theory of Computing Systems
publication date: 2012-12-06T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6113526
zbMATH Keywords: correlation
zbMATH Keywords: circuit complexity
zbMATH Keywords: modular polynomials
MaRDI profile type: Publication
full work available at URL: s00224-011-9332-9
OpenAlex ID: W2015506363
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: Upper and lower bounds for some depth-3 circuit classes
cites work: Estimation of certain exponential sums arising in complexity theory
cites work: On the correlation of symmetric functions
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Exponential sums and circuits with a single threshold gate and mod-gates
cites work: Bounds on an exponential sum arising in Boolean circuit complexity
cites work: A note on the power of majority gates and modular gates
cites work: A weight-size trade-off for circuits with MOD \(m\) gates
cites work: Lower Bounds for (MODp - MODm) Circuits
cites work: Threshold circuits of bounded depth
cites work: Mathematical Foundations of Computer Science 2004
cites work: On the power of small-depth threshold circuits
cites work: On the computational power of depth 2 circuits with threshold and modulo gates
cites work: Q3765876
cites work: \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
cites work: Q3248055
DOI: 10.1007/S00224-011-9332-9
description: scientific article; zbMATH DE number 6113526