Umm... I thought it was a pretty good introductory article, listing well-known and uncontroversial stuff. Yes, a polynomial algorithm might not be actually practical. Everybody knows this, and pointing it out every time P=NP comes up is bordering on cliche. Yes, NP-hard combinatorial optimization problems can have easy instances in practice. Why is that a reason for outrage?
Also, the paper was eager to assume that a polynomial algorithm that showed P = NP would be fast and that the world would then get big savings in airlines, manufacturing, etc., and that's nonsense. Generally we can get all but the last pennies of savings now.
Net, the paper is increasing the high confusion about the problem P versus NP.
These claims are false. We can get savings on a small number of "low-hanging fruit" problems, which are easy to approximate on practical instances - bin packing with many small items, scheduling with many short jobs, 2D Euclidean Hamiltonian cycles. What about, for example, the learning applications that Fortnow mentions? Try your C-PLEX on the problem "find the minimal size circuit that explains this big set of observations". You will not get anywhere. There are many other examples.
It makes sense for the industry to concentrate on making a buck out of the easy instances, and leaving the hard stuff to the academics. However, that is different from claiming that hard instances don't exist.
"However, that is different from claiming that hard instances don't exist."
but I didn't claim that there were no hard instances. Again, even showing P = NP does not guarantee to provide a fast algorithm for "hard instances" in NP. Net. the question P versus NP is a bit far from practice.
Again, a big example is the simplex algorithm: In practice, the algorithm finds optimal solutions in about 3m iterations where m is the number of rows, and we get to forget about the number of columns. So in practice simplex is terrific as a 'polynomial' algorithm: It's faster than a degree 1 polynomial since we get to ignore the number of columns. But, simplex, worst case, is exponential. So, there are polynomial algorithms to replace simplex, but they are all far too slow: If simplex takes too long, then the polynomial algorithms take still longer.
Linear programming is one of the best examples we have for where we had an exponential algorithm and found a polynomial one. The result: The polynomial algorithm sucked.
You wrote:
"find the minimal size circuit that explains this big set of observations".
I tried to skip over that part of the paper to keep my response simple.
First it is not clear what he means by "explains", but I fear that I do know. Basically he wants a 'fit', but this is dangerous. In practice, a good approach to finding such fits is classification and regression trees (CART) complete with a book by L. Breiman and others.
But for a 'fit', commonly that's easy: For some positive integer n and, for i = 1, 2, ..., n, we are given real numbers x(i) and y(i). The x(i) are distinct. Now we want a polynomial p of degree n - 1 so that p(x(i)) = y(i). Okay, how to find p? Easy. I leave it as an exercise. Problem is, p doesn't provide much as 'explanation'.
Generally, 'explanation' is tough to get at in part because it tries to get at causality which, just from data, as in the paper, is super tough to get at.
I mentioned C-PLEX for optimization problems. Not all problems in NP are optimization problems. But, curiously, integer linear programming bites off a lot of NP, and C-PLEX with associated techniques is one of the best approaches to integer linear programming.
The author points out something he may not have even intended: that parenting might not matter at all, despite the raging discussions about which parenting style is better.
In fact, lots of research on twins and adopted children suggests that parenting matters very little in shaping a child's personality and skills, while biology and peer groups matter a lot. Identical twins turn out quite similar regardless of whether they grow up in the same family, while adopted siblings are as different as any random people. (Check "How the Mind Works" by Pinker for a great overview.) People have a hard time accepting this, since most would like to believe that they have a power to shape their children, but this does not make it any less true.
> the Immigration Act of 1965... didn't just abolish racial quotas, it also created preference categories for science, math and engineering-trained immigrants to come over.
Ah, so Asian immigrants to the US are far from an unbiased sample of their original populations! This explains a lot more than bitter fights over parenting.
This is an argument that is hard to convey convincingly in a comment, but for those who are curious (including those who call "BS"), I recommend reading:
From what I could tell, the links you posted are no evidence to the contrary.
First, child abuse is beyond what most would call "parenting"; that term is mostly applied to things like strictness with respect to school homework, video games, pressure to choose certain careers, etc. My argument was that those of us that care about giving their children the best should not sweat too much over where precisely to draw the lines, because the effect of these decisions on the child's personality and life outcome is minimal.
Second, it is very possible that the same genes that increase the chance of a person being a child abuser also increase the chance of their child being, say, an alcoholic or criminal.
"Lulu handed me her 'surprise', which turned out to be a card,"
writes Chua in her explosive new memoir... "More accurately, it was
a piece of paper folded crookedly in half, with a big happy face on
the front. Inside, 'Happy Birthday, Mummy! Love, Lulu' was scrawled
in crayon above another happy face. I gave the card back to Lulu. 'I
don't want this,' I said. 'I want a better one – one that you've put
some thought and effort into. I have a special box, where I keep all
my cards from you and Sophia, and this one can't go in there.' I
grabbed the card again and flipped it over. I pulled out a pen and
scrawled 'Happy Birthday Lulu Whoopee!' I added a big sour face. …
'I reject this.'"
I would certainly call that child abuse, although I suppose Chua would call it "parenting"? To coerce Lulu into piano practice, Chua prevented her from using the washroom, and withheld food and affection until she could perform to her mother's satisfaction. That would qualify as abuse according the Adverse Childhood Experience Study. A lot of child abuse is rationalized by the perpetrator as just "strictness".
You are comparing top startups to mediocre Ph.D.'s. Top academia is very high-risk and very competitive. You take on very difficult research problems in the hope of becoming famous (but you may never be able to solve them). The rewards are accordingly high - having a large impact on the world, getting tenure to do what you love for the rest of your life, being surrounded by the best people in your field.
The premise that Ph.D. degrees are supposed to be mainly training for academic careers is wrong, at least in technical/engineering fields.
It is very common for people to enter e.g. CS or EE programs with no intention of pursuing an academic career, and instead planning to find an industry job afterwards. Indeed, there were some people I met in grad school that left well-paying jobs at (say) Microsoft with the intention of getting a Ph.D. and going back to industry to work on more interesting stuff. As far as I know, they usually succeeded.
Does a Ph.D. increase your expected salary, if you get an industry job afterwards? Probably not enough to be worth it. Does it raise the level of problems you will be solving, and the quality of people you will be surrounded with? Absolutely.
I would expect that an oversupply of lawyers would make them cheaper to hire and nicer to deal with. If we instead have a small group of lawyers that are expensive and unpleasant, while a lot of younger graduates cannot find jobs, I'd expect there must be some powerful artificial barriers of entry created by the group of insiders, though I have no idea what they could be...
I'm guessing it's because when you are hiring a lawyer it often means that at best millions of dollars or your entire livelihood is at stake and, at worst, your freedom or literally your life is at stake. In those situations most people aren't in a mood to bargain-hunt or take a risk with an unknown and untested product, if they have an option.
> It would make a lot of sense to have something like StarLisp or APL for CUDA right now. Trying to do data parallelism in C is about the most brain-damaged idea ever. I don't know if anyone is working or interested in that, though.
You may well be right, but I challenge you to prove it. I myself am very interested in whether this would work. I have spent many sleepless nights programming GPU algorithms, and wondered if ideas from other programming languages and paradigms (especially functional programming) could be applied to make it easier and more elegant.
The nested data-parallelism approach does look promising on paper, and many people are well aware of the theoretical possibility of this working on GPUs (including people at Nvidia itself), but so far nobody succeeded to make it practical.
So, doing data parallelism in CUDA may be brain-damaged, but the flexibility and performance it delivers is mind-blowing. If you can achieve something comparable using a higher-level functional approach, I will be among your first users, and I'll tell everyone I know.
MultiLisp (AFAIK) is traditional task-parallelism rather than data-parallelism, and would not work well on a GPU.
I am not disagreeing with you, I am saying that I would love to see a better data-parallel language than C (or CUDA to be precise), but it does not exist right now (at least not a practical one that would run on a real GPU with reasonable performance and allow non-trivial nested and hierarchical algorithms).
I suspect that the inability to bring down power isn't just "laziness" on Intel's part. Decreasing power consumption is (more or less) equivalent to increasing performance per watt - an area where Nvidia and ARM designs may simply be better.
You'd be surprised how many people walk around with terrible vision, without knowing it. My guess is that computer-related jobs require good vision, so people in these jobs are more likely to discover and treat their vision problems.
Also, until relatively recently glasses were uncool and unfashionable. Computer geeks generally pay less attention to such norms and choose function over form, so a geek with marginally poor eyesight would perhaps be more likely to go for glasses than a non-geek, who would survive without for appearance purposes.
I think jobs with computers are, in many ways, more forgiving to those with bad eyesight than other jobs. I have bad vision (just enough so I can't drive) but thanks to Gtk / Compiz, I can arbitrarily change the font size to be as big as I like it, and Orca and other screenreaders would help if I were completely blind. However, if I were a scientist or a taxicab driver or at a factory or throwing darts for a living, I'd be much worse off because I couldn't make those accommodations.
