Mihir Bellare, Oded Goldreich, et al.
Information and Computation
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, Oded Goldreich, et al.
Information and Computation
Mihir Bellare, Phillip Rogaway
Mathematical Programming
Mihir Bellare, David Cash, et al.
CCS 2011
Michel Abdalla, Mihir Bellare, et al.
Journal of Cryptology