A better-than-3n lower bound for the circuit complexity of an explicit function.
Magnus Gausdal FindAlexander GolovnevEdward A. HirschAlexander S. KulikovPublished in: Electron. Colloquium Comput. Complex. (2015)
Keyphrases
- lower bound
- worst case
- upper bound
- objective function
- np hard
- complexity analysis
- branch and bound algorithm
- computational complexity
- high speed
- optimal solution
- lower and upper bounds
- branch and bound
- decision problems
- linear programming relaxation
- circuit design
- average case complexity
- convergence rate
- piecewise linear
- lower bounding