\(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
type: Item
instance of: scholarly article
title: \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
zbMATH Open document ID: 1398.68159
author: Mahdi Cheraghchi
author: Elena Grigorescu
author: Brendan Juba
author: Karl Wimmer
author: Ning Xie
published in: Journal of Computer and System Sciences
publication date: 2018-09-07T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 6934097
zbMATH Keywords: Boolean analysis
zbMATH Keywords: circuit complexity
zbMATH Keywords: lower bounds
MaRDI profile type: Publication
full work available at URL: j.jcss.2018.04.006
OpenAlex ID: W2805951067
cites work: Q5601153
cites work: Q3994331
cites work: Q4228451
cites work: Threshold circuits of bounded depth
cites work: Reducing the seed length in the Nisan-Wigderson generator
cites work: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
cites work: On Graph Complexity
cites work: Efficient learning algorithms yield circuit lower bounds
cites work: Certifying polynomials for AC^0(parity) circuits, with applications
cites work: Constant depth circuits, Fourier transform, and learnability
cites work: Approximate inclusion-exclusion
cites work: Pseudorandom bits for constant depth circuits
cites work: On the degree of Boolean functions as real polynomials
cites work: Hardness vs randomness
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Q3997537
cites work: Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
cites work: Simple extractors for all min-entropies and a new pseudorandom generator
cites work: Hardness Amplification Proofs Require Majority
cites work: Pseudo-random generators for all hardnesses
cites work: Q4164821
cites work: On Learning, Lower Bounds and (un)Keeping Promises
DOI: 10.1016/J.JCSS.2018.04.006
description: scientific article; zbMATH DE number 6934097