A method for obtaining more than quadratic effective lower estimates of complexity of schemes
From MaRDI portal
Publication:1103591
zbMATH Open0645.94022MaRDI QIDQ1103591FDOQ1103591
Authors: Alexander E. Andreev 
Publication date: 1987
Published in: Moscow University Mathematics Bulletin (Search for Journal in Brave)
Cited In (20)
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- A super-quadratic lower bound for depth four arithmetic circuits
- On almost bad Boolean bases
- Tighter connections between Formula-SAT and shaving logs
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- On convex complexity measures
- Improving \(3N\) circuit complexity lower bounds
- Natural proofs
- On the shrinkage exponent for read-once formulae
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- Cubic Formula Size Lower Bounds Based on Compositions with Majority
- Circuit lower bounds from learning-theoretic approaches
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- Title not available (Why is that?)
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- Title not available (Why is that?)
- Small bias requires large formulas
- Matrix rigidity of random Toeplitz matrices
- Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
This page was built for publication: A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1103591)
