A method for obtaining more than quadratic effective lower estimates of complexity of schemes
From MaRDI portal
Publication:1103591
Cited in
(20)- On almost bad Boolean bases
- Improving \(3N\) circuit complexity lower bounds
- Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
- scientific article; zbMATH DE number 5077418 (Why is no real title available?)
- Matrix rigidity of random Toeplitz matrices
- Circuit lower bounds from learning-theoretic approaches
- Cubic Formula Size Lower Bounds Based on Compositions with Majority
- 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
- Small bias requires large formulas
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- Natural proofs
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- Tighter connections between Formula-SAT and shaving logs
- On the shrinkage exponent for read-once formulae
- On convex complexity measures
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- scientific article; zbMATH DE number 6007880 (Why is no real title available?)
- A super-quadratic lower bound for depth four arithmetic circuits
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
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)
