Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
type: Item
instance of: scholarly article
title: Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
zbMATH Open document ID: 1376.03043
DOI: 10.1137/15M1048045
author: Ilan Komargodski
author: Ran Raz
author: Avishay Tal
published in: SIAM Journal on Computing
publication date: 2017-02-15T00:00:00Z
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6684738
zbMATH Keywords: Boolean formulas
zbMATH Keywords: average-case lower bound
zbMATH Keywords: shrinkage
MaRDI profile type: Publication
cites work: A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
cites work: Quantum lower bounds by polynomials
cites work: On the construction of affine extractors
cites work: A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
cites work: Mining circuit lower bound proofs for meta-algorithms
cites work: Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
cites work: The Shrinkage Exponent of de Morgan Formulas is 2
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Pseudorandomness from Shrinkage
cites work: The effect of random restrictions on formula size
cites work: Boolean function complexity. Advances and frontiers.
cites work: Q5629239
cites work: Average-case lower bounds for formula size
cites work: Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
cites work: Q4856179
cites work: Shrinkage of de Morgan formulae under restriction
cites work: Q5365063
cites work: Q3281059
full work available at URL: 15m1048045
OpenAlex ID: W2585952665
description: scientific article