How pleasantly surprised I am to find that the work of Amir Ali Ahmadi, a friend and former student at Maryland where I was his EE TA, appeared on Hacker News.

How pleasantly surprised I am to find that the work of Amir Ali Ahmadi, a friend and former student at Maryland where I was his EE TA, appeared on Hacker News. We both took the same graduate-level class on optimal control; despite being an undergrad, he was one of the best students in the class. The result is intriguing and reasonably accessible: for all (multivariate) polynomials whose degrees are even and at least four, determining convexity (of any type! strong, strict, regular, pseudo-, quasi-) is strongly NP-hard. To prove this, the authors equate the problem of determining convexity to the problem of determining the nonnegativity of biquadratic forms -- a known NP-hard problem. Find the paper here: http://aaa.lids.mit.edu/publications http://aaa.lids.mit.edu/publications. (Edit: direct PDF link http://mit.edu/~a_a_a/Public/Publications/convexity_nphard.pdf http://mit.edu/~a_a_a/Public/Publications/convexity_nphard.p...) See Table I on page 18 for a concise summary.