Extreme-point fallacy

First, some administrative notes. Thanks to the readers for the feedback. I got requests for research advice and explanations of techniques from my thesis; I promise to post on both topics shortly.

Do take a look at Daniel's problem in this comment thread. It combines the features of being theoretically interesting and challenging while also being of great practical importance. If anyone has thoughts or literature pointers, please do share them with me or Daniel!

And here's a little teaser to see who's awake. Let D be a subset of R^n of the nicest possible kind: a finitely generated compact convex polytope. Thus, D is nothing more than the convex hull of finitely many points. Let f and g be two convex functions mapping D to R. A mathematician (let's call him Hermann) would like to prove that
f(x) <= g(x)
for all x in D. Now Hermann reasons as follows. He knows (from reading Papadimitriou and Steiglitz, for example) that an affine function achieves its extreme values on the extreme points of a convex domain. From this he concludes that a convex function achieves its maximal values on the extreme points of a convex domain (can you also make this deduction? Hint: the epigraph of a convex function lies above its derivative.). "Aha!" he exclaims. "All I need to do is check that f(x) <= g(x) on the extreme points of D. But there are finitely many of these -- they're just the corners of the polytope!"

You'll agree that verifying f(x)<=g(x) on the finitely many corners of D is, in general, a much simpler task than doing this for all of D. Is there something wrong with Hermann's reasoning, however?

[This is in no way meant to imply that any mathematician named Hermann ever claimed anything of this sort!]

Blog update & open thread

After months of cluelessness, I finally figured out how to make recent comments appear in that tab you now see on the right; many thanks to the anonymous commenter! No more digging through old posts to see who's left a comment (I've occasionally discovered comments on several week old posts.) Any idea how to make that "recent comments" list longer than 5 (blogger doesn't seem to give me that option)?

Following Daniel's suggestion, I'll make this an open thread. Post your problems (open or solved), tell some jokes, start flamewars -- it's all good! [I've never had to remove a comment or "moderate" in general, but don't push me...]

A CMU undergrad (CS) asks for some generic research advice and I promise to devote a post to this shortly.

Trip report + misc.

Back in Israel; it's good to be home. Now that the travels are over, I can look back and say "it wasn't that bad" -- but that's not what I would've told you when I was within a hair of getting arrested for refusing to give up my toothpaste at an airport security screening.

My submission got a "distinguished contribution" award at MLG (in lieu of "best paper" since these are extended abstracts). The analysis and probability workshop at Texas A&M was very intense, reminding me yet again how little of my so-called field I know.

"Meaty" content has been sparse here but I have a good excuse. I'm trying to switch gears from a problem-solving to a paper-writing mode. This requires less creativity and more discipline, but is absolutely indispensable -- both for one's career and for keeping oneself honest.

There's no shortage of high-quality, educational and entertaining material on the web (check out the links on the right), thus I feel no pressure to "deliver" to any readership. Speaking of which, if you're a regular reader of this blog, how about leaving a comment? Just so I know the blog has regular (or any) readers. [Not that a lack of readers has ever discouraged me from writing.] Also, feel free to use the comments to make suggestions regarding what you'd be interested in seeing here. Well enough chit-chat. Back to work.

Blogging from the road

I'm writing from Florence, Italy, where I'm attending the Mining and Learning with Graphs workshop. The paper I'm presenting is the Universal Kernel one. On the off-chance you're reading this and attending the workshop, say hi!

Then it's off to Texas for Concentration Week, namely: "Probability Inequalities with Applications to High Dimensional Phenomena". My talk: Obtaining measure concentration from Markov contraction. Slides will be online soon. [I'm intentionally blurring the distinction between Leonid and Aryeh (they're really the same name); hopefully, this won't cause confusion. Rule of thumb: if we're speaking English, use Leo. If we're speaking Hebrew, Aryeh. If we're speaking Russian, you know what to call me.]