More tender nuggets

You asked for ‘em, you got ‘em. (Do you want fries with that?)

  1. Suppose a baby is given some random examples of grammatical and ungrammatical sentences, and based on that, it wants to infer the general rule for whether or not a given sentence is grammatical. If the baby can do this with reasonable accuracy and in a reasonable amount of time, for any “regular grammar” (the very simplest type of grammar studied by Noam Chomsky), then that baby can also break the RSA cryptosystem.
  2. Oded Regev recently invented a public-key cryptosystem with an interesting property: though it’s purely classical, his system only known to be secure under the assumption that certain problems are hard for quantum computers. The upside is that, if these problems are hard for quantum computers, then Regev’s system (unlike RSA) is also secure against attack by quantum computers!
  3. Suppose N boys and N girls join a dating service. We write down an N-by-N matrix, where the (i,j) entry equals 1 if the ith boy and the jth girl are willing to date each other, and 0 if they aren’t. We want to know if it’s possible to pair off every boy and girl with a willing partner. Here’s a simple way to find out: first rescale every row of the matrix to sum to 1. Then rescale every column to sum to 1. Then rescale every row, then rescale every column, and so on N5 times. If at the end of this scaling process, every row and column sum is between 1-1/N and 1+1/N, then it’s possible to pair off the boys and girls; otherwise it isn’t.
  4. If two graphs are isomorphic, then a short and simple proof of that fact is just the isomorphism itself. But what if two graphs aren’t isomorphic? Is there also a short proof of that — one that doesn’t require checking every possible way of matching up the vertices? Under a plausible assumption, we now know that there is such a proof, for any pair of non-isomorphic graphs whatsoever (even with the same eigenvalue spectrum, etc). What’s the plausible assumption? It has nothing to do with graphs! Roughly, it’s that a certain problem, which is known to take exponential time for any one algorithm, still takes exponential time for any infinite sequence of algorithms.
  5. Suppose we had a small “neural network” with only three or four layers of neurons between the input and output, where the only thing each neuron could do was to compute the sum of its input signals modulo 2. We can prove, not surprisingly, that such a neural net would be extremely limited in its power. Ditto if we replace the 2 by 3, 4, 5, 7, 8, 9, or 11. But if we replace the 2 by 6, 10, or 12, then we no longer know anything! For all we know, a three-layer neural network, composed entirely of “mod 6 neurons,” could solve NP-complete problems in polynomial time.

34 Responses to “More tender nuggets”

  1. Osias Says:

    >> For all we know, a three-layer neural network, composed entirely of “mod 6 neurons,” could solve NP-complete problems in polynomial time.

    So why aren’t people …?

  2. Scott Says:

    For one thing, our neurons aren’t mod 6. :)

  3. Anonymous Says:

    Mmmm, those be some tasty nuggets

  4. chris Says:

    system only known to be secure under the assumption that certain problems are hard for quantum computers. The upside is that, if these problems are hard for quantum computers, then Regev’s system (unlike RSA) is also secure against attack by quantum computers!

    What’s the difference between being “secure under the assumption that certain problems are hard for QCs” and being “secure against attack by QCs” ?

  5. Osias Says:

    I mean… why aren’t people researching neural networks mod 6 to solve NP-complete problems? ^.^

  6. Scott Says:

    What’s the difference between being “secure under the assumption that certain problems are hard for QCs” and being “secure against attack by QCs” ?

    It’s a subtle point: the reduction from the problem in question to breaking the cryptosystem is a quantum reduction. So, even if all you wanted was security against classical attacks, you would still need to assume the problem was hard for QC’s. That you also get security against quantum attacks is sort of a free bonus.

  7. Scott Says:

    I mean… why aren’t people researching neural networks mod 6 to solve NP-complete problems?

    No one believes they actually exist. People have been trying to rule them out — that’s been an open problem since the 80’s, and is sometimes invoked as an example of how meager our circuit lower bounds really are.

    If you’re planning to look for these things, I suggest you first prove NP is in P/poly — that would be a necessary first step! :)

  8. Osias Says:

    actually, there is a zero-th step: understand what P/poly is. I’ll read again this night the 6th chapter of Sanjeev Arora and Boaz Barak and try to understand this time. ^.^

  9. Johan Says:

    Is not the claim in point 1 based on the assumption that babies brains are a particular sort of computer model? A assumption that is, how shall we say it, wrong?

  10. Craig Says:

    No, Johan, you miss the point.

    The point is that any given RSA cryptosystem problem can be translated into a regular grammar problem. So if the baby can always solve regular grammar problems correctly, you take the RSA problem you want to solve, translate it into a regular grammar problem, and hand it to the baby.

  11. Anonymous Says:

    Language acquisition does not mean to infer a set of production rules from a small set of examples. It is possible precisely because of the fact that human languages are not generated by arbitrary context-free grammars, but only by very special ones with a limited set of parameters that can be varied.

    I doubt very much that a baby could learn an arbitrary regular language at the same rate as it might acquire a human language.

  12. Scott Says:

    anonymous: Yes, that’s exactly the upshot!

  13. Andy D Says:

    Along the lines of the bin-packing nugget.. has anyone tried to make a really appealing demo of the NP-completeness concept, in the form of, say, a video game, which if you could beat it would generate as a byproduct a solution to a meaningful and seemingly unrelated math problem?

    As distributed computing projects go it would probably be wasteful, but as PR.. who knows?

    Or, reduce the problem of finding a 100-line proof of P != NP to a huge jigsaw problem, and offer a million dollars (via Clay Inst.) to solve. I recall that another jigsaw prize challenge created lots of interest (link?).

  14. GASARCH Says:

    The MOD 6: There is a difference
    between what we can PROVE and
    what we thing is TRUE.

    We can PROVE stuff for mod p
    where p is prime.

    Although we can’t PROVE stuff for
    mod 6, I don’t know of anyone
    who really things SAT is in
    Neural net with MOD 6 ops.

    Then again, I would have told you
    20 years ago that OF COURSE
    bounded width branching programs
    form a hierachy, they don’t all
    collpase to width 5. (poly length)

    bill g.

  15. Scott Says:

    andy d: That’s a fantastic idea! Let’s (as a community) put it on our to-do list!

  16. snehit Says:

    @the videogame idea
    Thats a totally kickass suggestion Andy. I dont know about the jigwaw, but Luis von Ahn has done something along these lines with captcha or one of its sister projects.
    In fact, if the P=NP space is too large to be feasible, one could try the NP-but-not-known-NP-complete variety. Proof/Disproof by witness can ensue.

    Scott – any comment on size of the combinatorial space for popular problems like factorization? How many players would need to make how many moves for how long before we strike gold?

  17. snehit Says:

    Sorry, correction. Factorization is known to be P thanks to Agrawal and company.
    Yea scott i know i have footinmouthitis :)

  18. Gil Says:

    Great choice, Scott
    can you add some links/references?

  19. Andy D Says:

    Uh, thanks for the feedback.. any volunteers?

    Just so everyone’s clear, the challenge isn’t to show a video game can be NP-hard–that’s been accomplished: Minesweeper, Tetris, Sokoban… you could do it for Mario Bros.

    The challenge would making a game where the source math problems are substantial, yet the game instances they reduce to are entertaining and potentially solvable given human abilities. As with the babies example, even crack gamers can’t just beat anything you hand to them in the form of a game.

    One additional point: ideally the source problem would be an optimization problem and the reduction would be a robust one, where higher and higher (not necessarily perfect) scores in the game bring better and better solutions to the source problem. There are examples of this kind of reduction.

  20. Anonymous Says:

    what do you think, scott:

    Assumed NP-complete problems have polynomial size- circuits. Doesn’t it seem to be impossible to proove P!=NP then? Because a TM that actually produces the circuits (in P) might be arbitrary long.

  21. Cheshire Cat Says:

    Andy, the suggestion of reducing math problems to video games for the sake of PR is a great one, but you seem to be going even further and suggesting this may actually be an approach to solving those problems? Hoping that a heuristic for a problem can benefit by throwing the structure of the problem away… Way to go – that’s the kind of counter-intuitive thinking that makes it such fun to be a computer scientist!

    Of course, the worst-case scenario would be if someone takes the suggestion seriously and actually solves P vs NP that way. Time then for complexity theorists to commit hara-kiri…

  22. Anonymous Says:

    if the circuits have no structure whatsoever (besides being polynomial)

  23. Andy D Says:

    Cheshire Cat–I’ve thought about the kind of project you refer to, but I wouldn’t bank on it anytime soon. (And for the record, I don’t think humans can reliably solve NP-hard problems, in any format.)

    I would really just like to see a game where you can view, and possibly pose, modest-sized but not trivial math problems in some domain, and then have them translated into something more entertaining. Hopefully it would enable skilled gamers to solve problems that would otherwise stump them or appear too tedious.

  24. Scott Says:

    Assumed NP-complete problems have polynomial size- circuits. Doesn’t it seem to be impossible to proove P!=NP then? Because a TM that actually produces the circuits (in P) might be arbitrary long.

    No. Assuming NP is in P/poly, it’s still consistent with everything we know that P!=NP and that that’s provable. The proof would just have to make essential use of uniformity.

  25. Anonymous Says:

    Can you give references for these claims? (Not because I doubt you, but because I want to read about them.)

  26. Anonymous Says:

    I’m a little confused about claim 1. So, presuming that babies do in fact learn correct grammar (before starting formal study of grammar in school) what are we left to conclude?
    – Language ruless are simpler than regular grammars?
    – The sentences parents speak to their child are more structured than we think?
    – Babies can break the RSA cryptoystem?

  27. Scott Says:

    Alright, alright:

    1. Kearns & Valiant (see also de Wolf)
    2. Regev

    3. Lecture by Avi Wigderson. See also paper by Linial, Samorodnitsky, and Wigderson

    4. Klivans & van Melkebeek

    5. Many papers have discussed the mod 6 gates issue; see this one for example

  28. snehit prabhu Says:

    @andy d
    Im a little confused.
    Are you thinking of using the game as some kind of Genetic Algo that searches for the globally optimum solution to a problem? Lots of players making “noisy”, possibly illogical moves and scanning a huge search space which would otherwise be mostly unexplored?

  29. Scott Says:

    I’m a little confused about claim 1. So, presuming that babies do in fact learn correct grammar (before starting formal study of grammar in school) what are we left to conclude?
    – Language ruless are simpler than regular grammars?
    – The sentences parents speak to their child are more structured than we think?
    – Babies can break the RSA cryptoystem?

    This question was discussed and answered earlier. The key point is that human beings share a universal grammar — i.e. one that’s hardwired into the brain — with only a small number of “parameter settings” that need to be learned. For more, see Ronald de Wolf’s master’s thesis (linked to above), or read The Language Instinct by Steven Pinker.

  30. Ambitwistor Says:

    Linial, Samorodnitsky, and Wigderson give an approximate algorithm for calculating matrix permanents. Do you know if this (or a related) algorithm has been used to numerically calculate quantum statistical properties of bosonic systems, which involve matrix permanents?

    P.S. Do you know why Citeseer seems to be down every other time I try to use it? With multiple mirrors being down at the same time? I don’t understand why computer scientists can’t achieve the same reliability as the physics arXiv.

  31. craig Says:

    Snehit, that’s not true.

    Agrawal etc. proved PRIMES is in P, not FACTORIZATION. Different problem.

  32. Anonymous Says:

    Regarding the idea discussed here of getting humans to solve NP-hard problems — not exactly the same, but along similar lines:

    http://www.cis.upenn.edu/~mkearns/papers/ScienceFinal.pdf

    Best
    Michael Kearns

  33. Depth First Search » Blog Archive » Finished Says:

    […] I just discovered a new blog, Shtetl-Optimized, for your consideration. […]

  34. trigman Says:

    So, although, I appreciate these ‘insites’, i also realize this is a blog, and to be credited in any fashion, cite sources of any ideas or related concepts.

    I am familiar with a few of these nuggets, but it’s not the point for a person not knowing. Citing also adds further research one could do on the subjects as they find interesting. it’s win-win…