## Catching a FOCS

I just found out that our paper “On Basing Lower-Bounds for Learning on Worst-case Assumptions” was just accepted to FOCS! Yay! Guess this means that I’ll be visiting Philly in October. Too bad BA won’t be around!

Anyway I’m sure you’re all *dying* to know what exactly the title means. For the lay-person, computational hardness results typically come in two flavors, “worst-case” and “average-case”. “Worst-case” hardness means that no matter what algorithm you try to use to solve a problem, there exists at least one input on which the algorithm makes a mistake. “Average-case” hardness says that no mater what algorithm you try to use to solve a problem, there exist *many* inputs on which the algorithm makes a mistake. So average-case hardness implies worst-case hardness, but in most cases the reverse implication is unknown.

In general, when we want to prove a statement X and we can’t do it unconditionally, then we try to show that some kind of hardness implies X. We prefer to show that worst-case hardness implies X because worst-case hardness is a more reasonable assumption than average-case hardness.

However, in many situations we only know how to prove that average-case hardness implies X. In our case, we know that some versions of average-case hardness imply that the task of learning how to label (for example, label pictures as “landscape” or not) is difficult, but it’s unknown whether we can show that learning is hard based only on worst-case assumptions. Our paper tries to address this, and basically we show that a wide range of proof techniques, including all hardness of learning proof techniques known in the literature, cannot be used to resolve this question. I know, there’s a lot of double negatives going on, but trust me it makes sense!

Congratulations!

(Last sentence, second paragraph, should be the reverse.)

Moritz said this on June 21, 2008 at 11:26 am

yay! congratulations!

trust me. it’s hard to say its hard.

Sharon said this on June 22, 2008 at 6:40 pm

Thanks!

therandomoracle said this on June 23, 2008 at 11:23 pm