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!


~ by therandomoracle on June 21, 2008.

3 Responses to “Catching a FOCS”

  1. Congratulations!

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

  2. yay! congratulations!
    trust me. it’s hard to say its hard.

  3. Thanks!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: