A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
From MaRDI portal
Publication:1103591
zbMath0645.94022MaRDI QIDQ1103591
Publication date: 1987
Published in: Moscow University Mathematics Bulletin (Search for Journal in Brave)
Related Items
Natural proofs, A satisfiability algorithm and average-case hardness for formulas over the full binary basis, On convex complexity measures, On almost bad Boolean bases, On the shrinkage exponent for read-once formulae, Matrix rigidity of random Toeplitz matrices, Super-logarithmic depth lower bounds via the direct sum in communication complexity, \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom, Circuit lower bounds from learning-theoretic approaches, $$P\mathop{ =}\limits^{?}NP$$, Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound, Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation