A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs
Farid M. AblayevMarek KarpinskiPublished in: Electron. Colloquium Comput. Complex. (1998)
Keyphrases
- lower bound
- max sat
- floating point
- randomized algorithms
- integer arithmetic
- upper bound
- randomized algorithm
- branch and bound algorithm
- branch and bound
- lower and upper bounds
- np hard
- optimal solution
- worst case
- objective function
- vc dimension
- upper and lower bounds
- linear programming relaxation
- lower bounding
- np complete
- sufficiently accurate
- arithmetic operations