Mihir Bellare, Moti Yung
Journal of Cryptology
We consider the problem of finding the maximum of a multivariate polynomial inside a convex polytope. We show that there is no polynomial time approximation algorithm for this problem, even one with a very poor guarantee, unless P = NP. We show that even when the polynomial is quadratic (i.e. quadratic programming) there is no polynomial time approximation unless NP is contained in quasi-polynomial time. Our results rely on recent advances in the theory of interactive proof systems. They exemplify an interesting interplay of discrete and continuous mathematics-using a combinatorial argument to get a hardness result for a continuous optimization problem. © 1995.
Mihir Bellare, Moti Yung
Journal of Cryptology
Michel Abdalla, Mihir Bellare, et al.
Journal of Cryptology
Mihir Bellare, Don Coppersmith, et al.
IEEE Trans. Inf. Theory
Mihir Bellare, John Rompel
FOCS 1994