15
$\begingroup$

Larry Wasserman has a recent post where he talks about the "p-value police". He makes an interesting point (all emphasis mine) (the premise in italics that I added, and his response below it):

The most common complaint is that physicists and journalists explain the meaning of a p-value incorrectly. For example, if the p-value is 0.000001 then we will see statements like “there is a 99.9999% confidence that the signal is real.” We then feel compelled to correct the statement: if there is no effect, then the chance of something as or more extreme is 0.000001.

Fair enough. But does it really matter? The big picture is: the evidence for the effect is overwhelming. Does it really matter if the wording is a bit misleading? I think we reinforce our image as pedants if we complain about this.

Which got me thinking -

Are there good examples of pedantry in TCS ? Such an example would consist of

  • A claim that is commonly made in the popular press
  • A standard correction that people insist on making
  • The correct "big picture" that the claim does capture even while being imprecise.

where the claim is mathemtically wrong but "morally right" and the correction is technically correct but doesn't change the intuitive understanding.

To lead things off, my example would be:

  • Claim - NP-complete problems take exponential time to solve
  • Correction - No in fact we just don't know if they can be solved in polynomial time
  • Big picture - NP-complete problems are HARD

Caution: I know there are many on this forum whose head will explode at the idea of claims that are wrong but "morally correct" :). Remember that these are statements targeted towards the public (where some degree of license can be permitted), rather than statements made in a research paper.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Not sure about this, but might "true randomness" qualify? People might often claim that something is (truly) random, when in fact we don't know. Since $K(x)$ of a string $x$ is uncomputable, we can't verify the claim of randomness. Nevertheless, many sources of generating randomness are often random enough in practice. $\endgroup$
    – Juho
    Jul 11, 2012 at 16:51
  • $\begingroup$ It's an interesting idea, but is there much talk about true randomness in the popular press ? $\endgroup$
    – Suresh Venkat
    Jul 11, 2012 at 16:53
  • $\begingroup$ I guess that's a bit subjective -- maybe as much as the popular press talks about NP-completeness? But yes, I guess randomness comes up in different contexts, but usually there is no distinction made between pseudorandomness and (true) randomness. $\endgroup$
    – Juho
    Jul 11, 2012 at 17:02

5 Answers 5

Reset to default
17
$\begingroup$

Hm, its tough even to think of examples of claims about TCS that make it to the popular press.

One thing I have seen occasionally is the claim that factoring is NP-hard, when explaining cryptography. This is related to the less innocuous error of claiming that quantum computers can solve NP hard problems, but restricted to the context of cryptography, this is a relatively mild error. The point is just that we (users of cryptography) seem to believe that there is no efficient algorithm for solving the problem. The particular conjectures we use to justify this assertion are besides the point.

Improve this answer
$\endgroup$
12
$\begingroup$

  • claim by press: about things that grow "exponentially" ie claim of O(k^n)

  • actually true: often, a constant power O(n^k)

  • big picture: it grows fast enough, all right

Improve this answer
$\endgroup$
5
  • $\begingroup$ That's a nice one. I was thinking about that as well. $\endgroup$
    – Suresh Venkat
    Jul 11, 2012 at 18:20
  • 8
    $\begingroup$ I actually keep one of these on my webpage: cg.scs.carleton.ca/~morin/misc/nortel $\endgroup$
    – Pat Morin
    Jul 11, 2012 at 19:09
  • 1
    $\begingroup$ Except in that case it DID make a difference :) $\endgroup$
    – Suresh Venkat
    Jul 11, 2012 at 20:40
  • 4
    $\begingroup$ exponential has taken the meaning of anything that grows superlinearly $\endgroup$
    – ratchet freak
    Jul 12, 2012 at 9:21
  • $\begingroup$ The word "exponential" is one of the most abused. Here are some examples I've seen: "The number of goals scored by [some soccer player] has been growing exponentially from each season to the next","I've been able to improve my team working attitude in an exponential manner along the years","The number of channels available through satellite TV is exponential". $\endgroup$
    – Giorgio Camerani
    Oct 19, 2012 at 13:22
12
$\begingroup$
  • Claim by press: First polynomial time algorithm for an important practical problem will necessarily change our lives, will be the next best thing after sliced bread, etc.

For examples, take any press article about the ellipsoid algorithm from the time it was discovered (great account of the story: http://www.springerlink.com/content/vh32532p5048062u/). The press claimed that this new great mathematical discovery will affect everyone's lives, solve TSP (which they found especially ironic given how few traveling salesmen there were in the USSR!), turn crypto upside down, etc.

Then there is AKS, which in some reports was even implied to solve factoring..or at least to be an industry-changing innovation.

I am sure there are plenty more examples.

  • Actually true: Polynomial time does not mean practical! Case in point: ellipsoid algorithm, sampling from high-dimensional convex bodies. Worst-case exponential time does not mean impractical. Case in point: simplex algorithm. When the new algorithm is merely the first deterministic polytime algorithm for a problem, this has even less relevance to practice.

  • Big picture: these results are breakthroughs, and at least the press gets people excited about them, even if it is for the wrong reasons. And much of the time a polynomial time algorithm eventually turns into a reasonably efficient algorithm. For example Gentry's homomorphic encryption scheme is not practical yet, but its running time has been improved significantly. Near-linear time solvers for SDD systems of equations seem to be well on the way to practicality but started off with a $\log^5 n$ factor hidden in the soft-oh notation.

Improve this answer
$\endgroup$
6
$\begingroup$

The popular press often gives the impression that the primary, if not the only, reason that computers are succeeding at more and more tasks (beating Kasparov at chess, beating Jennings at Jeopardy, etc.) is increased raw processing power. Algorithmic advances are typically not given that much credit.

However, I'm ambivalent about whether insisting that algorithmic advances be given more weight is "pedantry." On the one hand, I think that those of us who are more theoretically inclined can sometimes overstate the importance of algorithmic advances and only grudgingly admit the importance of increased processing power. On the other hand, I do think the public should be better informed about the role of theoretical advances in solving practical problems.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think it could be argued that "pedantry" is accurate. Many people don't know the difference between hardware or software (really a surprising amount for me at least). To the uninitiated, where exactly the improvement comes from could be classified as pedantry, even though we know that there are huge structural and conceptual differences. $\endgroup$
    – SamM
    Jul 14, 2012 at 7:16
-8
$\begingroup$

Scott Aaronson, while a foremost authority, seems to regularly take the media to task for not hairsplitting accurately. eg his recent column in the NYT article "Quantum Computing Promises New Insights, Not Just Supermachines" [italics added]

Struggling to shoehorn that mathematics into newspaper-friendly metaphors, most popular writers describe a quantum computer as a magic machine that could process every possible answer in parallel, rather than trying them one at a time. Supposedly, it could do that because, unlike today’s computers that manipulate bits, a quantum computer would manipulate quantum bits, or qubits, which can be 0 and 1 simultaneously.

But that’s a crude way to visualize what a quantum computer does, and misses the most important part of the story. When you measure a quantum computer’s output, you see just a single, random answer — not a listing of all possible answers. Of course, if you had merely wanted a random answer, you could have picked one yourself, with much less trouble.

yet the metaphor of a quantum computer processing answers in parallel is widespread & a reasonable conceptual simplification of QM computing, and referred to in many QM computing textbooks. there are probably other examples from QM theory/computing.

there is a natural tension in TCS and other theoretical research in communicating with the public/media because it sometimes tends to emphasize critical distinctions/concepts as part of rigorous training that are not known or crucial to laymen. in other words in many cases research theory works against various conceptual "big picture" simplifications that are legitimate to laymen.

Improve this answer
$\endgroup$
9
  • 10
    $\begingroup$ You need to put your answer in the right format :). But I actually don't think your answer is appropriate. Because the "quantum computer can try all cases in parallel" argument is wrong in important ways, and is not helpful as intuition. So I don't think there's a higher "moral truth" $\endgroup$
    – Suresh Venkat
    Jul 11, 2012 at 18:58
  • 6
    $\begingroup$ I agree with @SureshVenkat a quantum computer processing all possibilities in parallel is about as close to the moral truth as a probabilistic computer processing all possibilities in parallel. It is completely useless for intuition and there is no "kind of true" thing it is approximating. $\endgroup$
    – Artem Kaznatcheev ♦
    Jul 11, 2012 at 19:01
  • 5
    $\begingroup$ When I run across people who insist that QC's can solve all possible inputs to a problem, I usually respond with: "OK, fine. You get one answer. At random. How do you ensure that it's probably the right one?" $\endgroup$
    – Josephine Moeller
    Jul 11, 2012 at 19:14
  • $\begingroup$ @ArtemKAznatcheev: I would definitely say there’s something meaningful in this simplification. In a quantum computation (unlike a probabilistic one), components of the state corresponding to different possibilities can (through further linear operations) cancel out, or otherwise “interfere”. I’d agree this intuition doesn’t go very far towards what’s really going on, but it does go a little way, and I’ve yet to see any way of going further without getting into the actual linear algebra, which for most lay readers would be a complete turnoff. $\endgroup$
    – PLL
    Jul 11, 2012 at 23:48
  • 4
    $\begingroup$ @PLL: in a nondeterministic machine, the branches don't interfere either. So while we suspect that BQP is strictly larger than BPP, this makes comparing a quantum computer to a nondeterministic Turing machine exactly the wrong sort of comparison to make. You could try to make a (still quite sloppy) comparison to Parity-P or Gap-P, but somehow I don't think that this will at all help you to convey what quantum computers do very much. $\endgroup$
    – Niel de Beaudrap
    Jul 12, 2012 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.