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)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (18)
\(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom ⋮ On almost bad Boolean bases ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Matrix rigidity of random Toeplitz matrices ⋮ On the shrinkage exponent for read-once formulae ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ Super-logarithmic depth lower bounds via the direct sum in communication complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ On convex complexity measures ⋮ Natural proofs ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Cubic Formula Size Lower Bounds Based on Compositions with Majority ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates
This page was built for publication: A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
