Slashback: Passports, Microscopes, IQ Points

Slashback tonight with updates and clarifications on recent Slashdot stories (and story arcs), including a downright Operatic end to Jon S. von Tetzchner's cross-oceanic attempt (or was that just in fun?), the status of post-death email privacy, minimizing the dangers of RFID passports, and more - read on for the details.

Actually, it's taking tests that reduces IQ. The guys at Mind Hacks have dissected the widely reported story that 'email destroys the mind faster than marijuana' [Posted on Slashdot a few days ago -- T.] and found that it is more spin than science. The results show simply that people do worse at IQ tests when distracted, although Hewlett-Packard are not releasing details of the experiment, so others cannot even evaluate if the research is sound. The use of psychobabble for marketing marches on.

One day this will all be commemorated as ... an opera. GreyPoopon writes "It looks like Jon's attempt at swimming the Atlantic has ended in early failure. Taking the blame once again is is PR Manager, Eskil Sivertsen. The raft he was using was somehow punctured this morning, and Jon had to abondon his trek to perform a heroic rescue. Perhaps someone should take on the task of sending our downtrodden adventurer a cup of Mom's hot chocolate."

PCP theorem simplified, still way over my head. Stridar writes "Sanjeev Arora's proof of the PCP theorem was a great acheivement. This theorem, a reduction of NP to PCP, allowed for many striking results on the difficulty of finding approximate solutions to NP-Hard problems. However, his original proof is long and technical, focusing on the arithmetization of booelan formulas. It has long been an open problem to simplify this result. Now Irit Dinur , a mathematician at the Hebrew University, has given a purely combinatorial proof of the PCP theorem, in her exciting paper "The PCP Theorem by Gap Amplification" ."

I think several other things end at death, too. microbee writes "The Register reports that Yahoo has complied with a court order to give a dead soldier's email account to his parents. It's not clear to me from the news whether they got direct access to the actual mail box, or just hard copy of those emails. If the former, it's a bit funny to read "the family complain they have only got emails received by Justin, not those he wrote." People have to wonder whether their privacy ends at death."

Haven't they ever seen The Killing Fields? valdean writes "Following up on past Slashdot stories, Wired News reports that the State Department is now considering adding a password to the new RFID passports, in response to 'criticism from computer security professionals and civil libertarians.' According to the article, 'The data... would be locked and unavailable to any reader that doesn't know a secret key or password to unlock the data. To obtain the key, a passport officer would need to physically scan the machine-readable text that's printed on the passport page beneath the photo... The reader would then hash the data to create a unique key that could be used to authenticate the reader and unlock the data on the RFID chip.'"

Anything with LEDs in it makes me happy. HunterD writes "Apparently a company called DigitalBlue purchased the rights to the Intel Play series, which included the Intel QX3 microscope. Well, DigitalBlue has released an upgrade called the QX5 that features an Ultrabright LED, a better camera, and a number of other upgrades."

Comments

The PCP Theorem

[cpeikert]

The PCP theorem is a beautiful piece of computer science and mathematics. What's it good for? Well, for starters:

• One can use it to show that not only are some problems very hard to get exact answers to, they are very hard to even get approximate answers to! In the most extreme case, it's hard to tell whether a graph has an enormous clique (taking up almost all the vertices), or just a very small one.
• PCPs can be used to build very low-communication zero-knowledge proofs. So you can prove a mathematical statement to someone, using much less communication than it takes to even write down that statement, and giving her no idea why the statement is true, even though she will be absolutely convinced that it really is true!
• PCPs can also be used to write down a (long) proof of a mathematical theorem, so that to check the theorem only requires you to look in a few random places. If the theorem is false, you'll detect it, otherwise you'll be convinced that it's true. It's as if there was a huge book of mathematics, and you opened to a random page, read a few characters, and said, "yep, it's definitely all true."

In short: amazing!

Re:The PCP Theorem

[Nitish]

Well, you don't need to feel bad about not understanding the PCP theorem. It's a difficult concept to grasp. For example, you could be an extremely intelligent and motivated high school student who can't "get it" even if you try, because you just haven't studied all the pre-requisite material you need. Though perhaps you can't go to the PCP theorem from where you are now, you might be able to understand it once you have all the background knowledge.

The original poster described the PCP theorem well, but it might not make a lot of sense to people who haven't studied algorithms or complexity theory. This might help:
A lot of problems people want to solve in practice are "optimization" problems. That is, given a problem, we want to find the optimum (minimum or maximum, as the case may be) solution. For example, if you have to travel to several cities, you might want to know the cost of the cheapest tour that visits all of them. Or you might want to know what the most efficient way of scheduling jobs on a machine is. These (and several other) problems, are what we call NP-Hard. That has a technical meaning, but in short, it takes a *really* long time (far more than is practical) to compute the best solutions for these problems. And so if you wanted a solution, instead of spending forever to find the best tour, you might settle for a tour that cost only 1% more, if you could find it quickly. Algorithms which do this are called approximation algorithms; they don't always find the best solution, but they approximate it - the solution they find is nearly as good... perhaps just a little more expensive or less inefficient.

Approximation algorithms are useful because people are often satisfied with solutions that are "good enough", even if not perfect. So for a hard problem, it's worth spending time trying to find a good approximate solution.

Enter the PCP theorem! You can use it to show that some problems can't even be approximately solved in a reasonable amount of time, and that's what the original poster was talking about.

Besides this, the theorem is important and loved because not only is it useful, it's non-obvious and beautiful