tag:blogger.com,1999:blog-3722233Tue, 21 May 2019 09:51:04 +0000typecastfocs metacommentsComputational ComplexityComputational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarchhttps://blog.computationalcomplexity.org/noreply@blogger.com (Lance Fortnow)Blogger2684125tag:blogger.com,1999:blog-3722233.post-6282781001271163342Mon, 20 May 2019 14:14:00 +00002019-05-20T10:14:14.118-04:00Notorious L.A.H or Notorious LAH? OR You always need one more proofreadI noticed a while back that even on the nth proofread of a document there are still corrections. So I decided to keep track of how many corrections there are in a paper I was working on. I chose a non-technical paper so that errors-in-the-math would not be the issue. I chose<br />
<br />
Guest Column: The Third P =?NP Poll (see <a href="https://blog.computationalcomplexity.org/2019/03/third-poll-on-p-vs-np-and-related.html">here</a>)<br />
<br />
that appeared in Lane Hemaspaandra's SIGACT News Complexity Column.<br />
<br />
I kept track of the following:<br />
<br />
1) Number of corrections. Anything that I changed. Could be style, a new thought, need not be (though could be) an error.<br />
<br />
2) Errors. These are things that really need to be corrected, like having `think' instead of `thing' .<br />
<br />
Corrections vs Errors, an Example:<br />
<br />
If I refer to Lane Hemaspaandra as <i>Notorious L.A.N</i> that is a correction and an error, as he is Notorous <i>L.A.H.</i><br />
<br />
If I refer to Lane Hemaspaandra as<i> Notorious L.A.H</i> and decide to change it to <i>LAH </i>that is a correction that is not an error.<br />
<br />
I didn't keep track of serious errors vs typos, but after the first 3 proofreads there were no more serious errors--- sort of- --you'll see. Most serious was a f<b>onts-gone-wild thing where half the paper was in boldface.</b><br />
<br />
Here is a history of the number of corrections<br />
<br />
1) Lane proofread the first draft. κ corrections where κ is some cardinal between the cardinality of N and the cardinality of 2<sup>N</sup> . Its value depends on which model of set theory you are in. (My spellchecker thinks that cardinality is not a word. I checked and I am spelling it correctly but perhaps it's one of those things where I stare at it too much and keep misreading it.)<br />
<br />
Henceforth I omit the word <i>proofread</i> as it is understood<br />
<br />
<br />
2) Bill G: 81 corrections, 29 of which were errors.<br />
<br />
3) Clyde: 64 corrections, of which 17 were errors.<br />
<br />
4) Bill G: 40 corrections, of which 21 were errors (I had added a new section causing more errors)<br />
<br />
5) Clyde: 30 corrections of which 10 were errors.<br />
<br />
6) Bill G: 24 corrections of which 6 were errors.<br />
<br />
7) Clyde: 18 corrections of which 8 were errors.<br />
<br />
8) David Sekora (A CS grad student at Maryland who at one time wanted to be an English Major): f15 corrections of which 15 were errors. Really! Typos dagnabbit! (Spell check thinks that dagnabbit is spelled wrong. Um---in that case what is the correct spelling?)<br />
<br />
9) Nathan Grammel (A CS grad student at Maryland) :6 corrections of which 3 were errors.<br />
<br />
10) Bill G, proofreading backwards, a paragraph at a time: 29 corrections of which 5 were errors.<br />
<br />
11) Justin Hontz, an ugrad who TAs for me: 10 corrections of which 7 were errors.<br />
<br />
12) Karthik Abinav, a grad student in theory at Maryland: 2 corrections both of which were errors. Was this the end or are there still issues?<br />
<br />
13) Josh Twitty, an ugrad who TAs for me: 0 corrections. YEAH!<br />
<br />
14) Dan Smolyak, an ugrad CS and Eco major:4 corrections, all 4 errors. <i>Error </i>sounds too strong. For example, one of them was to replace ?. with ? Yes, its an error, but not that important. It DOES point to his carefulness as a proofreader.<br />
<br />
15) Clyde Kruskal :20 corrections, 10 of which were errors. To call them errors seems wrong when he corrects <i>Group theory' </i>to <i>Group Theory</i>. None of these corrections were caused by prior comments. I think all of the errors were in the paper early on, undetected until now!<br />
<br />
16) Backwards Bill G again: 28 corrections, 14 of which were errors. Again, the errors were minor. Most of the errors were relatively recent. As an example, if I list out topics in math like:<br />
<br />
a) Group Theory, Set Theory, and Ramsey Theory<br />
<br />
then I am supposed to use capital letters, but if I say in prose<br />
<br />
Lance Fortnow thinks that the techniques used will be group theory, set theory, and Ramsey theory<br />
<br />
then only the R in Ramsey Theory is in caps. Makes me glad I'm in math.<br />
<br />
17) Lane got penultimate proofread. Lane found 75 (yes 75 WOW) of which 66 (yes 66 WOW) were errors. Many of these were spacing and latex things that I would never have noticed (indeed- I didn't notice) and most readers would not have noticed (hmmm- how do I know that?) but only an editor could catch (hmmm- when I've edited the book review column and now the open problems column and I never found more than 10 errors). So when all is said and done: KUDOS to Lane! And My point was that you can never get all the errors out. On that I am correct. I wonder if there are still errors? Yeah, but at most 10. However, I said that BEFORE giving it to Lane.<br />
<br />
18) Stephen Fenner, the editor of SIGACT news got FINAL proofread. He found that I spelled his name wrong . How many errors are left? I would bet at most 10. I would bet that I would lose that bet.<br />
------------------------------------------------------------------------------------------------------------<br />
<br />
Why after multiple proofreadings are there still errors? (My spell check thinks proofreadings is not a word. Maybe my spell check is worried that if people get documents proofread a lot then they won't be needed anymore. This blog post refutes that thought.)<br />
<br />
1) An error can occur from a correction. This caused a massive problem with another paper. Lane's next column will be by me and co-authors on The Muffin Problem. We had all kinds of problems with the colors and sizes--- Massive Magenta Muffins or Miniature Magenta Muffins? Sizes gone wild! Again Kudos to my proofreaders and to Lane for catching this rather important error.<br />
<br />
2) If some passage is added late in the process it will surely have errors.<br />
<br />
3) An error correction may clear away the brush so you can see other errors.<br />
<br />
4) With LaTeX (or Word for some) we have the ability to get things perfect. So there is no cost to keeping on perfecting things. This lead so many corrections that are not errors.<br />
<br />
5) I know of an adviser who would first say change A to B, and later change B back to A. (None of that happened with the paper discussed above).<br />
<br />
Are errors inevitable? Clyde Kruskal tells me that his father Martin Kruskal, as a teenager, read Courant and Robbins book <i>What is Mathematics</i> and found some errors in it. Martin's mother didn't believe him and marched him over to Courant's house:<br />
<br />
MARTIN MOTHER: Martin claims to have found errors in your book.<br />
<br />
COURANT: (laughs) There are errors in every book.<br />
<br />
Courant was so impressed that ten (or so) years later Courant became Martin's PhD adviser.<br />
<br />
<br />https://blog.computationalcomplexity.org/2019/05/notorious-lah-or-notorious-lah-or-you.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-9175787683601603334Thu, 16 May 2019 12:46:00 +00002019-05-16T08:46:33.928-04:00Getting Through the ClutterMy daughter showed up at her doctor's office the other day and found it closed. She complained that she had received all these alerts, texts, emails, voicemails, reminding her of the appointment and then they weren't there when she showed up. She had stopped reading the alerts, the last of which said the appointment need to be rescheduled.<br />
<br />
We all get too many alerts. I just assume many of the emails I send to faculty never get read or remembered. I get many requests to mention conferences, workshop and other theory happenings on this blog because nobody knows how to get the word out through the clutter. If we followed through on all these requests, this blog would become clutter itself.<br />
<br />
Back in 2009, Nikhil Devanur and I wrote a <a href="https://doi.org/10.1145/1562814.1562830">paper</a> trying to capture this phenomenon using complexity. Building on Levin's notion of universal search, the unawareness of a string x in an environment E is the amount of time needed to generate x from a context c given an oracle for E. Levin showed that one can have a universal algorithm, only a constant time slower to generate x than any other algorithm. One should think of E as the sum total of all our knowledge including search engines on the Internet. Technically we should have used the term "attention" instead of "awareness".<br />
<br />
One example is using a calendar as part of your environment, E, that reminds you of an event, x, on that date, c. We use calendars, contact lists, emails searches and many other ways to keep strings we need to remember. Advertisers try to alter your E to get the unawareness of x down.<br />
<br />
One of these papers that didn't go far because we didn't have great applications for the definition. But it follows a good philosophy, when life seems complex, model it.https://blog.computationalcomplexity.org/2019/05/getting-through-clutter.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-3507110503322010708Mon, 13 May 2019 04:39:00 +00002019-05-15T14:01:34.489-04:00Ronald Graham's other large number. Well---- it was large in 1964 anyway.Graham's number (see <a href="https://en.wikipedia.org/wiki/Graham%27s_number">here</a>) was at one time the largest number to appear in a math proof.<br />
<br />
a) GN was an upper bound on a problem in Ramsey theory. There are now better upper bounds, see <a href="https://www.sciencedirect.com/science/article/pii/S0195669814000936?via%3Dihub">here</a>. These better upper bounds are still large- Hales-Jewitt-Large, but that's already much smaller than the original GN.<br />
<br />
b) Other proofs now have numbers even larger than GN. For example Harvey Friedman's work on the finite versions of Kruskal's Tree Theorem. (There may be other cases- if you know some then let me know in the comments.)<br />
<br />
Since my dept recently moved buildings I found old papers that I had not looked at in years. One of them was<br />
<br />
<i>Old and New Problems and Results in Combinatorial Number Theory</i><br />
<br />
by Erdos and Graham<br />
<br />
(see <a href="http://www.math.ucsd.edu/~ronspubs/79_09_combinatorial_number_theory.pdf">here</a>)<br />
<br />
So I began reading it and came across a result of Graham from 1964 that used large numbers. No where near as large as GN, but I found it interesting that Graham was involved with large numbers way back then.<br />
<br />
Here is the problem:<br />
<br />
A <i>Lucas Sequence</i> is a sequence that obeys<br />
<br />
a(n) = a(n-1) + a(n-2).<br />
<br />
Clearly such a sequence is determined by a(0) and a(1).<br />
<br />
QUESTION: Does there exists a(0) and a(1) that are rel prime such that the sequence has only composite numbers?<br />
<br />
By ingenuity and some computing power Graham found YES. For how the got the numbers see <a href="http://www.math.ucsd.edu/~ronspubs/64_06_fibonacci.pdf">here</a>. The numbers are of course in the paper, and how they got them is interesting, but I present them anyway. Hope I don't make a typo:<br />
<br />
a(0) = 1786772701928802632268715130455793<br />
<br />
a(1) = 1059683225053915111058164141686995<br />
<br />
The paper Old and New... says its open if there is a smaller pair of numbers, I do not know if it is still open. If you know, let us all know in the comments!<br />
<br />
These numbers seem small today since we have modern computers that can store and manipulate them easily. Were the considered large numbers in 1964? They were never called Graham Numbers which is probably just as well since that honor lay ahead.<br />
<br />
<br />https://blog.computationalcomplexity.org/2019/05/ronald-grahams-other-large-number-well.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-722419176401069744Thu, 09 May 2019 12:31:00 +00002019-05-09T08:31:57.559-04:00Multiple ProversJust over thirty years ago on May 5, 1989, I defended my PhD Thesis <a href="https://lance.fortnow.com/papers/files/thesis.pdf">Complexity-Theoretic Aspects of Interactive Proof Systems</a>. It's starts off with a parable for interactive proof systems.<br />
<blockquote class="tr_bq">
Victor, a venture capitalist, had everything a man could desire: money, women and power.
But he felt something missing. He decided he lacked knowledge. So Victor packed up his
bags and headed to the Himalayas in search of ultimate truths.
The natives pointed Victor to a tall mountain and mentioned rumors of a great man full of
wisdom. Victor, who smartly brought some climbing equipment, tackled the mountain until
he reached a small cave near the summit. Victor found the great Pulu, grand guru of all that
is known. Victor inquired to some ultimate truths and Pulu responded,
<i>I will teach you but you must not trust my words</i>.
Victor agreed and found he learned much even though he had to verify all the sayings
of the great Pulu. Victor though lacked complete happiness and he asked if he could learn
knowledge beyond what he could learn in this manner. The grand guru replied,
<i>You may ask and I will answer</i>.
Victor pondered this idea for a minute and said, "Since you know all that is known, why can you not predict my questions?" A silence reigned over the mountain for a short while until the guru finally spoke,
<i>You must use other implements, symbols of your past life</i>.
Victor thought for a while and reached into his backpack and brought out some spare
change he had unwittingly carried with him. Even the great Pulu can not predict the flip of
a coin. He started flipping the coins to ask the guru and wondered what can I learn now?</blockquote>
Without the coins, one gets the complexity class NP. My thesis didn't answer the last question, but by the end of the year, <a href="https://doi.org/10.1109/FSCS.1990.89519">Shamir</a> building on work of <a href="https://doi.org/10.1145/146585.146605">Lund, Fortnow, Karloff and Nisan</a> showed this class IP was equal to PSPACE, the problems we could solve in a polynomial amount of memory.<br />
<br />
Part of my thesis explored the class MIP where we had multiple Pulus (provers) on different mountain tops unable to communicate. The news was disappointing, we failed to get a PSPACE upper bound for MIP, only NEXP (nondeterministic exponential time) and our proof that two provers sufficed relied on a bad assumption on how errors get reduced when you run multiple protocols in parallel. Later Babai, Lund and myself showed <a href="http://doi.org/10.1007/BF01200056">MIP = NEXP</a> and Ran Raz <a href="https://doi.org/10.1137/S0097539795280895">showed</a> parallel repetition does reduce the error sufficiently.<br />
<br />
Back in the 80's we didn't even imagine the possibility that the Pulus had shared entangled quantum bits. Does the entanglement allow the provers to cheat or can the entanglement allow them to prove more things? Turns out to be much more, as a <a href="https://arxiv.org/abs/1904.05870">new result</a> by Anand Natarajan and John Wright shows that MIP*, MIP with classical communication, classical verifier and two provers with previously entangled quantum bits, can compute everything in NEEXP, nondeterministic double exponential time. This is only a lower bound for MIP*, possibly one can do even more.<br />
<br />
Neat to see my three-decade old thesis explored ideas that people are still thinking about today.https://blog.computationalcomplexity.org/2019/05/multiple-provers.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-2431469456247088523Tue, 07 May 2019 00:41:00 +00002019-05-06T20:41:19.956-04:00Thoughts on the recent Jeopardy streak (SPOILERS)James Holzhauer has won 22 consecutive games of Jeopardy and has made around 1.6 million dollars. Nice work if you can get it. Here are some thoughts no this<br />
<br />
1) Before James H the records for number of consecutive games was, and still is, Ken Jennings winning 74 in a row, and second place was 20. I was surprised that Ken was that much better than the competition.<br />
<br />
2) Before James H the record for amount of money in normal play (not extra from, say, tournament of champions or losing to a computer) was around 400,000. I was surprised that Ken was that much better than the competition.<br />
<br />
3) James is obliterating the records for most wins in a single game. He holds the top 12 records for this. This is due to his betting A LOT on the daily doubles and the final jeop, as well as of course answering so many questions right.<br />
<br />
4) One reason players in Jeopardy don't have long streaks is fatigue. The actually play<br />
5 games a day, two days of the week. James H is getting a break since he has two weeks off now since they will soon have the Teachers Tournament. This could work either way--- he gets a break or he loses being in-the-zone.<br />
<br />
5) James strategy is:<br />
<br />
a) Begin with the harder (and more lucrative) questions.<br />
<br />
b) Bet A LOT on the daily doubles (which are more likely to be in the more lucrative questions) and almost always go into final jeop with more than twice your opponent (He failed to do this only once.)<br />
<br />
c) Bet A LOT on Final Jeop- though not enough so that if you lose you lose the game. I think he's gotten every Final Jeop question right.<br />
<br />
For more on his strategy see this article by Oliver Roeder in Nate Silvers Blog: <a href="https://fivethirtyeight.com/features/the-man-who-solved-jeopardy/">here</a><br />
<br />
6) I tend to think of this as being a high-risk, high-reward strategy and thus it is unlikely he will beat Ken Jennings, but every time he wins that thought seems sillier and sillier. While we are here, how likely is it that someone will beat Ken Jennings? In an article before all of this Ben Morrison in Nate Silvers Blog wrote that it was quite likely SOMEONE would break Ken J's record, see <a href="https://fivethirtyeight.com/features/ken-jennings-has-nothing-on-joe-dimaggio/">here</a>.<br />
<br />
7) OKAY, how does James H compare to Ken J? According to Oliver Roeder in Nate Silvers Blog,<br />
<a href="https://fivethirtyeight.com/features/the-battle-for-jeopardy-supremacy/">here</a>, they are similar in terms of percent of questions answered right, but James H bets so much more (bets better?) which is why he is getting so much money. I'll be curious to see a head-to-head contest at some point. But to the issue at hand, they don't give James H that good a chance to break Ken J's record.<br />
<br />
8) Jeop used to have a 5-game limit. Maybe that was a good idea- its not that interesting seeing the same person with the same strategy win 22 in a row. Also, the short-talk-with-Alex T-- James is running out of interesting things to say. I wonder what Alex did with Ken J after 50 games.<br />
``So Ken, I hear you're good at Jeopardy''<br />
<br />
9) Misc: Ken J was the inspiration for IBM to do Watson.<br />
<br />
10) Will future players use James Strategy? Note that you have to be REALLY GOOD in the first place for it to help you. Maybe a modified version where you go for the lucrative questions and bet a lot on Daily Doubles (more than people have done in the past) when its an area you know really well (I'll take Ramsey Theory for $2000.)<br />
<br />
11) I used to DVR and watch Jeop but didn't mind if I was a few behind. Now I have to stay on top of it so articles like those pointed to above don't give me a spoiler.<br />
<br />
12) My prediction: He will beat Ken Jenning for money but not for number-of-games. I have no real confidence in these predictions.https://blog.computationalcomplexity.org/2019/05/thoughts-on-recent-jeopardy-streak.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-3204953698007493895Thu, 02 May 2019 12:20:00 +00002019-05-02T08:20:52.726-04:00The Next Chapter<div class="separator" style="clear: both; text-align: center;">
<a href="https://4.bp.blogspot.com/-R3cQu_-p5K8/XMhzxr-ZDrI/AAAAAAABnYQ/4tXefV5yICMHnD_U4g8QmFFftzHzeOWTQCLcBGAs/s1600/COS_stacked_blk_red.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="478" data-original-width="1600" height="95" src="https://4.bp.blogspot.com/-R3cQu_-p5K8/XMhzxr-ZDrI/AAAAAAABnYQ/4tXefV5yICMHnD_U4g8QmFFftzHzeOWTQCLcBGAs/s320/COS_stacked_blk_red.jpg" width="320" /></a></div>
<div>
<br /></div>
I've <a href="https://news.iit.edu/stories/2019/05/lance-fortnow-designated-new-college-science-dean">accepted a position</a> as Dean of the <a href="https://science.iit.edu/">College of Science</a> at the Illinois Institute of Technology in Chicago starting in August. It's an exciting opportunity to really build up the sciences and computing in the city that I have spent the bulk of my academic career and grew to love.<br />
<div>
<br /></div>
<div>
I had a fantastic time at Georgia Tech over the last seven years working with an incredible faculty, staff and students in the School of Computer Science. This is a special place and I enjoyed watching the school, the institute and the City of Atlanta grow and evolve.<br />
<br />
After I <a href="https://twitter.com/fortnow/status/1123644799825907712">tweeted</a> the news yesterday, Bill Cook reminded me that<br />
<blockquote class="tr_bq">
Illinois Tech was the long-time home of Karl Menger, the first person to pose the problem of determining the complexity of the TSP. Now you can settle it!</blockquote>
I wouldn't bet on my settling the complexity of traveling salesman even if I didn't have a college to run. But it goes to remind us that wherever you go in life, P and NP will be right there waiting for you. </div>
https://blog.computationalcomplexity.org/2019/05/the-next-chapter.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-6025884855508893027Mon, 29 Apr 2019 02:26:00 +00002019-04-28T22:26:12.748-04:00 x3 + y3 + z3 = 33 has a solution in Z. And its big!Consider the following problem:<br />
<br />
Given k, a natural number, determine if there exists x,y,z INTEGERS such that x<sup>3</sup>+y<sup>3</sup>+z<sup>3</sup>=k.<br />
<br />
It is not obvious that this problem is decidable (I think it is but have not been able to find an exact statement to that affect; however, if it was not solvable, I would know that, hence it is solvable. If you know a ref give it in the comments.)<br />
<br />
<br />
If k≡ 4,5 mod 9 then mod arguments easily show there is no solution. <a href="https://arxiv.org/pdf/1604.07746.pdf">Huisman</a> showed that if k≤ 1000, k≡1,2,3,6,7,8 mod 9 and max(|x|,|y|,|z|) ≤ 10<sup>15</sup> and k is NOT one of<br />
<br />
33, 42, 114, 165, 390, 579, 627, 633, 732, 795, 906, 921, 975<br />
<br />
then there was a solution. For those on the list it was unknown.<br />
<br />
Recently <a href="https://people.maths.bris.ac.uk/~maarb/papers/cubesv1.pdf">Booker</a> (not Cory Booker, the candidate for prez, but Andrew Booker who I assume is a math-computer science person and is not running for prez) showed that<br />
<br />
x<sup>3</sup> + y<sup>3</sup> + z<sup>3</sup> =33<br />
<br />
DOES have a solution in INTEGERS. It is<br />
<br />
x= 8,866,128,975,287,528<br />
<br />
y=-8,778,405,442,862,239<br />
<br />
z=-2,736,111,468,807,040<br />
<br />
<br />
does that make us more likely or less likely to think that<br />
<br />
x<sup>3</sup> + y<sup>3</sup> + z<sup>3</sup> =42<br />
<br />
has a solution? How about =114, etc, the others on the list?<br />
<br />
Rather than say what I think is true (I have no idea) here is what I HOPE is true: that the resolution of these problems leads to some mathematics of interest.<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2019/04/x-3-y-3-z-3-33-has-solution-in-z-and.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-8078353386966881451Thu, 25 Apr 2019 12:12:00 +00002019-04-25T08:13:14.850-04:00Geo-Centric ComplexityAn interesting discussion during Dagstuhl last month about the US-centric view of theory. Bad enough that all talks and papers in an international venue are in English but we also have<br />
<ul>
<li><a href="https://en.wiktionary.org/wiki/Manhattan_distance">Manhattan Distance</a>. How are foreigners supposed to know about the structure of streets in New York? What's wrong with grid distance?</li>
<li><a href="https://en.wikipedia.org/wiki/Las_Vegas_algorithm">Las Vegas Algorithms</a>. I found this one a little unfair, after all Monte Carlo algorithms came first. Still today might not Macau algorithms make sense?</li>
<li><a href="https://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol">Arthur-Merlin Games</a>. A British reference by a Hungarian living in the US (László Babai who also coined Las Vegas algorithms). Still the Chinese might not know the fables. Glad the Europeans don't remember the <a href="https://blog.computationalcomplexity.org/2017/04/alice-and-bob-and-pat-and-vanna.html">Pat and Vanna</a> terminology I used in my first STOC talk. </li>
<li>Alice and Bob. The famous pair of cryptographers but how generically American can you get. Why not Amare and Bhati?</li>
</ul>
<div>
I have two minds here. We shouldn't alienate or confuse those who didn't grow up in an Anglo-American culture. On the other hand, I hate to have to try and make all terminology culturally neutral, you'd just end up with technical and ugly names, like P and NP.</div>
https://blog.computationalcomplexity.org/2019/04/geo-centric-complexity.htmlnoreply@blogger.com (Lance Fortnow)13tag:blogger.com,1999:blog-3722233.post-8139226761048070665Tue, 23 Apr 2019 03:24:00 +00002019-04-22T23:25:25.907-04:00Quiz Show Scandals/Admissions Scandal/Stormy Daniels/Beer names:being a lawyer would drive me nuts!!!!!!0) Charles van Doren (see <a href="https://en.wikipedia.org/wiki/Charles_Van_Doren">here</a>) passed away recently. For those who don't know he he was (prob most of you) he was one of the contestants involved in RIGGED quiz shows in the 1950's. While there was a Grand Jury Hearing about Quiz Shows being rigged, nobody went to jail since TV was new and it was not clear if rigging quiz shows was illegal. Laws were then passed to make them it illegal.<br />
<br />
So why are today's so-called reality shows legal? I ask non-rhetorically.<br />
<br />
(The person he beat in a rigged game show- Herb Stempel (see <a href="https://en.wikipedia.org/wiki/Herb_Stempel">here</a>) is still alive.)<br />
<br />
1) The college admissions scandal. I won't restate the details and how awful it is since you can get that elsewhere and I doubt I can add much to it. One thing I've heard in the discussions about it is a question that is often posted rhetorically but I want to pose for real:<br />
<br />
There are people whose parents give X dollars to a school and they get admitted even though they are not qualified. Why is that legal?<br />
<br />
I ask that question without an ax to grind and without anger. Why is out-right bribery of this sort legal?<br />
<br />
Possibilities:<br />
<br />
a) Its transparent. So being honest about bribery makes it okay?<br />
<br />
b) My question said `even though they are not qualified' - what if they explicitly or implicitly said `having parents give money to our school is one of our qualifications'<br />
<br />
c) The money they give is used to fund scholarships for students who can't afford to go. This is an argument for why its not immoral, not why its not illegal.<br />
<br />
But here is my question: Really, what is the legal issue here? It still seems like bribery.<br />
<br />
2) Big Oil gives money to congressman Smith, who then votes against a carbon tax. This seems like outright bribery<br />
<br />
Caveat:<br />
<br />
a) If Congressman Smith is normally a anti-regulation then he could say correctly that he was given the money because they agree with his general philosophy, so it's not bribery.<br />
<br />
b) If Congressman smith is normally pro-environment and has no problem with voting for taxes then perhaps it is bribery.<br />
<br />
3) John Edwards a while back and Donald Trump now are claiming (not quite) that the money used to pay off their mistress to be quiet is NOT a campaign contribution, but was to keep the affair from his wife. (I don't think Donald Trump has admitted the affair so its harder to know what his defense is). But lets take a less controversial example of `what is a campaign contribution'<br />
<br />
I throw a party for my wife's 50th birthday and I invite Beto O'Rourke and many voters and some Dem party big-wigs to the party. The party costs me $50,000. While I claim it's for my wife's bday it really is for Beto to make connections to voters and others. So is that a campaign contribution?<br />
<br />
4) The creators of HUGE ASS BEER are suing GIANT ASS BEER for trademark infringement. I am not making this up- see <a href="https://thetakeout.com/huge-giant-ass-beer-lawsuit-new-orleans-1832989913">here</a><br />
<br />
---------------------------------------------------------<br />
<br />
All of these cases involve ill defined questions (e.g., `what is a bribe'). And the people arguing either side are not unbiased. The cases also illustrate why I prefer mathematics: nice clean questions that (for the most part) have answers. We may have our biases as to which way they go, but if it went the other way we would not sue in a court of law.https://blog.computationalcomplexity.org/2019/04/quiz-show-scandalsadmissions.htmlnoreply@blogger.com (GASARCH)1tag:blogger.com,1999:blog-3722233.post-2053726780224405945Thu, 18 Apr 2019 11:40:00 +00002019-04-18T07:40:18.207-04:00Physics of Everday LifeBased on <a href="https://www.scottaaronson.com/blog/?p=3654">Scott's review</a>, I read through Stephen Pinker's <a href="https://www.amazon.com/Enlightenment-Now-Science-Humanism-Progress-ebook/dp/B073TJBYTB/ref=as_li_ss_tl?crid=2O1U6VZR84R2Q&keywords=enlightenment+now&qid=1554897483&s=gateway&sprefix=engligh,aps,597&sr=8-1&linkCode=ll1&tag=computation09-20&linkId=8f668f77297b7cd8b57a85dca27802b0&language=en_US">Enlightenment Now</a>. I can't top Scott's exposition of the book, but it is pretty incredible how far humanity has gone when you step back to look at the big picture.<br />
<br />
One line intrigued me, one that Pinker credits to a book called <a href="https://www.amazon.com/Big-Picture-Origins-Meaning-Universe/dp/1101984252/ref=as_li_ss_tl?ie=UTF8&linkCode=ll1&tag=computation09-20&linkId=6c644c72e1d0c1f818a5907f9b221ce1&language=en_US">The Big Picture</a> by Sean Carroll<br />
<blockquote class="tr_bq">
The laws of physics underlying everyday life (that is excluding extreme values of energy and gravitation like black holes, dark matter and the Big Bang) are <i>completely known.</i></blockquote>
Hasn't this statement almost always been true, in the sense that the leading minds would make this claim at many times in history. The ancient Greeks probably believed they understood physics that underlies everyday life. So did physicists after Newton. Life back then not today. My everyday life involves using a GPS device that requires understanding relativistic effects and computer chips that needed other scientific advances.<br />
<br />
Is it possible we could do more in everyday life if we knew more physics? I'd certainly use a teleporter in everyday life.<br />
<br />
And is the statement even true today? We all use public key cryptography, even to read this blog. It's not completely clear if we understand the physics enough to know how or if large-scale quantum computers capable of breaking those systems can be built.<br />
<br />
Everday life is relative.https://blog.computationalcomplexity.org/2019/04/physics-of-everday-life.htmlnoreply@blogger.com (Lance Fortnow)6tag:blogger.com,1999:blog-3722233.post-3262168094346690140Mon, 15 Apr 2019 04:08:00 +00002019-04-15T00:08:14.146-04:00Good article, terrible headlineAbout a month ago (after my P NP poll appeared) I got email from Jacob Aron asking me some questions about it. One thing he was excited about was that the number of people who thought P vs NP would be solved in the next decade had increased from 11% to 22%. I told him that this also surprised me and <i>there had been no major advances to warrant that increase.</i><br />
<i><br /></i>
Then the article came out. Here is the pointer to the headline and the first few lines, the rest is behind a paywall<br />
<br />
<a href="https://www.newscientist.com/article/2198151-we-could-solve-the-biggest-problem-in-maths-in-the-next-decade/">here</a><br />
<br />
You may notice that the headline is<br />
<br />
<i>We could solve the biggest problem in math in the next decade</i><br />
<i><br /></i>
I emailed Jacob to send me the article, which he did. The article was fine, even quoting me as saying that the increase of people who thought it would be solved soon was unwarranted.<br />
<br />
1) So, article fine, headline terrible.<br />
<br />
2) A more honest headline would be<br />
<br />
<i>The Complexity Theory Community slightly more optimistic about when P vs NP will be resolved for no apparent reason.</i><br />
<i><br /></i>
3) More bad science:<a href="https://www.newscientist.com/article/mg22329780-400-turings-oracle-the-computer-that-goes-beyond-logic/">here</a><br />
<br />
Headline is<br />
<br />
<i>Turing's Oracle: The computer that goes beyond logic</i><br />
<br />
I think the article was about how a Turing Machine with an oracle for HALT can solve HALT. (If I am wrong about this let me know in the comments and I'll correct it.)<br />
<br />
4) More bad science:<a href="https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/">here</a><br />
<br />
Headline<br />
<br />
<i>Finally, a problem that only Quantum Computers will ever be able to solve.</i><br />
<i><br /></i>
This was about the oracle such that BQP is not in PH. Really!<br />
<br />
5) I invite you to add your own.<br />
<br />
6) OKAY, so why is the press SO BAD at reporting on our field? And is it just our field? I have one explanation, though I am sure there are many.<br />
<br />
Our field is about showing the LIMITS of computation. Its hard to make that sexy so they ... lie? exaggerate. They themselves don't really understand our field? Note:<br />
<br />
To explain to someone who does not really know CS why its important to have an oracle where BQP is not in PH is hard<br />
<br />
To explain this to someone IN CS but not in Theory is still hard!<br />
<br />
To explain this to someone IN CS and even in CS Theory, but not complexity (e.g., algorithms) might be hard, though it may depend on the person.<br />
<br />
7) The old saying is `I don't care if you get the story wrong so long as you spell my name right' And indeed, they did spell my name right. So there is that! But more seriously and less about me or even the article that refers to my poll--- is it bad that science reporting is often wrong?<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2019/04/good-article-terrible-headline.htmlnoreply@blogger.com (GASARCH)7tag:blogger.com,1999:blog-3722233.post-721449905698588127Thu, 11 Apr 2019 22:13:00 +00002019-04-11T18:13:22.769-04:00Elwyn Berlekamp Died April 9, 2019Elwyn R. Berlekamp entered this world on Sept 6, 1940, and left it on April 9, 2019. <a href="https://en.wikipedia.org/wiki/Elwyn_Berlekamp">Wikipedia</a> calls him <i>An American Mathematician</i> which seems to narrow to me. He worked on a variety of topics which were Math, Comp Sci, finance, and likely others --- if you know any that I missed leave comments.<br />
<br />
Here are some of the things he worked on:<br />
<br />
1) Factoring Polynomials over large finite fields (See <a href="https://www.jstor.org/stable/2004849?seq=1#metadata_info_tab_contents">here</a> from 1970)<br />
<br />
I quote the abstract<br />
<blockquote class="tr_bq">
This paper reviews some of the known algorithms for factoring polynomials over finite fields and presents a new deterministic procedure for reducing the problem of factoring an arbitrary polynomial over the Galois field GP(p<sup>m</sup>) to the problem of finding roots in GF(p) of certain other polynomials over GP(p). The amount of computation and the storage space required by these algorithms are algebraic in both the degree of the polynomial to be factored and the log of the order of the field.</blockquote>
<blockquote class="tr_bq">
Certain observations on the application of these methods to factorization of polynomials over the rational integers are also included. </blockquote>
I think he meant what we would call polynomial time when he says algebraic.<br />
<br />
2) Combinatorial Games. He co-wrote the classic Winning Ways For your Mathematical Plays with John Conway and Richard Guy. These books are like NIM on steroids. They are FUN and have some serious math in them. (My blog system thinks Combinatorial is not a word. It is wrong)<br />
<br />
3) Combinatorial Games. He was very interested in Go via Combinatorial Games. I have an article (alas, not online) by him entitled Introductory Overview of Mathematical Go Endgames. There has been further work on this that is on the web, see <a href="http://web.stanford.edu/~wqy/research/Honor%20Thesis.pdf">here</a>. I wonder what ERB would think of the ALPHAGO program.<br />
<br />
4) Berlekamp-Massey Algorithm finds the shortest linear feedback shift register for a given binary output sequence.<br />
<br />
5) Berlekamp-Welch Algorithm efficiently corrects errors in Reed-Solomon codes. (Berlekamp also wrote a book on Algebraic Coding Theory.)<br />
<br />
6) I didn't know about his work in finance until I began writing this, but the following quote from Wikipedia is impressive<br />
<blockquote class="tr_bq">
In 1989, Berlekamp purchased the largest interest in a trading company named Axcom Trading Advisors. After the firm's futures trading algorithms were rewritten, Axcom's Medallion Fund had a return (in 1990) of 55%, net of all management fees and transaction costs. The fund has subsequently continued to realize annualized returns exceeding 30% under management by James Harris Simons and his Renaissance Technologies Corporation.</blockquote>
https://blog.computationalcomplexity.org/2019/04/elwyn-berlekamp-died-april-9-2019.htmlnoreply@blogger.com (GASARCH)6tag:blogger.com,1999:blog-3722233.post-5672867789279325982Mon, 08 Apr 2019 03:02:00 +00002019-04-07T23:06:05.779-04:00Problems with a point- NOT a plug, just some thoughts on books and book writingProblems with a Point: Exploring Math and Computer Science by Gasarch and Kruskal, available on amazon <a href="https://www.amazon.com/Problems-Point-Exploring-Computer-Science/dp/9813279974/ref=sr_1_1?keywords=gasarcj&qid=1553111113&s=gateway&sr=8-1-spell">here</a>, came out a while back and I plugged it in my blog post <a href="https://blog.computationalcomplexity.org/2019/02/problems-with-point-exploring-math-and.html">here</a>. Regan-Lipton reviewed it <a href="https://rjlipton.wordpress.com/2019/03/10/problems-with-a-point/">here</a>.<br />
<br />
This post is NOT a plug, its random points about the book and book writing<br />
<br />
1) On Feb 28 I checked my Amazon ranking twice. At noon it was at 400,000 and at 4:00PM it was at roughly 80,000. Either (a) someone bought a copy, or (b) the number of sales of such books is so small that amazon does rankings arbitrarily. A counter argument to that: Bounded Queries in Recursion Theory, which I wrote in 1998 and, despite an awesome review on amazon that I wrote, sold literally 0 copies last year, is ranked 5,000,000. So even within the low numbers there is SOME logic to the rankings. (Update- Today, April 7, PWAP is at 800,000 and BQIRT is at 12,000,000. I suspect that nothing has changed with BQIRT and the 5,000,000 or 12,000,000 is arbitrary. As for PWAP--- since its still a new book the ranking might mean something. Oh well- fame is fleeting!)<br />
<br />
1.5) At one time my book was 29th in the category <i>Teen and Young Adult Computer Programming. </i>Really? While teens and young adults might read it, I don't think of it as geared towards them (only one use of <i>OMG</i> and two uses of <i>awesome</i> in the entire book). And as for Computer Programming... uh... no.<br />
<br />
2) I emailed many people about it and many people are buying it. Some tell me that the cover looks great so YES, they are judging a book by its cover. My mom asked how it was selling. I told her that (a) about 20 people told me they bought it, and (b) I doubt that's how JK Rowling responds when she's asked how her Harry Potter books are selling.<br />
<br />
3) Many people could actually read this book and would care about its content. When I wrote Bounded Queries in Recursion Theory (with Georgia Martin) I didn't email a lot of people about it since it was rather specialized.<br />
<br />
4) Some people said `Gee bill, we didn't know you were working on a book'. That's true- I didn't talk about it much. Clyde knew (my co-author, so he had to know), Lance knew. Darling knew. Mom Knew. That might be about it. Why so few? see next point.<br />
<br />
5) I had heard there are two kinds of people:<br />
<br />
<i>Those that talk about writing a book but don't do it</i><br />
<br />
<i>Those that write a book instead of talking about it</i>.<br />
<br />
I chose to be the second type.<br />
<br />
6) When I got an advanced copy I couldn't stop reading it. Ego? Disbelieve? Some of each?<br />
<br />
7) ADVICE for book writers: just get it done. You can polish it later but first get it done so you have something to polish.<br />
<br />
8) More advice: You can never have too many proofreaders. Even though its been gone over a lot I still read it and find minor things to fix OR think `gee why didn't I include BLAH in the book'<br />
<br />
9) Title: `Problems with a Point' I came up with very early and I liked it a lot. World Scientific (our publisher) pointed out, correctly, that we need a subtitle since PWAP didn't really tell the reader whats in it. I wanted to make it alliterative but it was hard. Here were some possibilities<br />
<br />
PWAP: Mathematical Musing Made Magnificent (can replace Musings with Morsels)<br />
<br />
PWAP: Mathematical Meditations and Computer Science Cogitations<br />
<br />
PWAP: Mathematical Musings and the Math that Makes those Musings Matter<br />
<br />
All in all I am happy with the non-alliterative, but informative<br />
<br />
PWAP: Exploring Math and Computer Science.<br />
<br />
10) Odd thing I learned- if I quote someone who made a comment on my blog or emailed me I needed permission. Actually I doubt I NEEDED it but the laws here are murky so I got it just to make sure. That explains this blog from a while back: <a href="https://blog.computationalcomplexity.org/2018/10/john-sidles-mike-roman-matt-howell.html">here</a><br />
<br />
11) ADVICE for book writers: Write the preface last since then you have a better idea of why you wrote the book.https://blog.computationalcomplexity.org/2019/04/problems-with-point-not-plug-just-some.htmlnoreply@blogger.com (GASARCH)1tag:blogger.com,1999:blog-3722233.post-6372871065307387905Thu, 04 Apr 2019 11:50:00 +00002019-04-04T07:50:48.257-04:00Cuckoo Cycles<span style="font-weight: normal;"><i>Guest Blog by John Tromp (Thanks for the opportunity, Lance)</i></span><br />
<br />
In the past few months, cycle finding has become one of the most widely run
graph theory problems. An estimated quarter-to-half million GPUs are constantly
looking for 42-cycles in random bipartite graphs on a billion or more nodes.
Customized chips have been designed to perform this specific application an
order of magnitude more efficiently, thanks to integrating as much as 1GB of
SRAM on a single chip, where Intel/AMD CPUs top out at 64 MB.
<br />
<br />
The purpose of all this? To compete for block rewards in various
cryptocurrencies using the <a href="https://github.com/tromp/cuckoo">Cuckoo Cycle Proof of Work</a>.
<br />
<br />
It is named after the Cuckoo Hashtable, in which each data item can be stored
at two possible locations, one in each of two arrays. A hash function maps the
pair of item and choice of array to its location in that array. When a newly
stored item finds both its locations already occupied, one is kicked out and
replaced by the new item. This forces the kicked-out item to move to its
alternate location, possibly kicking out yet another item. Problems arise
if the corresponding Cuckoo graph, a bipartite graph with array locations as
nodes and item location pairs as edges, has cycles.
While n items, whose edges form a cycle, could barely be stored in the table,
any n+1st item mapping within the same set of locations (a chord in the cycle)
would not fit, as the pigeonhole principle tells us.
<br />
In the Proof-of-Work problem, we typically set n ≥ 29, and use edge indices
(items) 0 .. N-1, where N = 2<sup>n</sup>. The endpoints of edge i are (siphash(i|0) % N, siphash(i|1) % N), with
<a href="https://en.wikipedia.org/wiki/SipHash">siphash</a> being a popular keyed hash function.
A solution is a cycle of length L in this Cuckoo graph, where typically L = 42.<br />
<br />
While looking for cycles takes a lot of time and memory, solutions can be instantly verified.
This sets Cuckoo Cycle apart from many other memory hard proofs of work that require computing a memory hard hash function, such as scrypt,
both for proving and verifying.
Some luck is also required to find a 42-cycle;
Slides 18 and 19 of this <a href="https://github.com/mimblewimble/grin-pm/blob/master/presentations/grinconUS0/12-Tromp-Proof_of_Work.pdf">Grincon.US presentation</a> sketch a proof of the
<br />
<br />
<b>Cuckoo Cycle Theorem</b>:
The expected number of L-cycles tends to 1/L
<br />
<br />
While there is a known linear time-memory trade-off, it suffers from a large constant factor penalty.
A large bounty is offered on the project webpage for better trade-offs.
<br />
<br />
Cuckoo Cycle solvers spend nearly all cycles on edge trimming; identifying and
removing edges that end in a leaf node (of degree 1), as such edges cannot be
part of a cycle. Trimming rounds alternate between the two node
partitions. This can be done using N bits for the edge bitmap, and N log<sub>2</sub>(3) bits
for the (truncated) node degrees. The random accesses to the latter,
while not a problem for custom chips using enough SRAM, cause large memory latencies
on commodity hardware. These can be mostly avoided by storing remaining edges explicitly
and (bucket) sorting them to determine node degrees.
Despite using an order of magnitude more memory than the edge bitmap, this is still over 4x faster.<br />
<br />
The fraction f<sub>i</sub> of remaining edges after i trimming rounds (in the limit as N
goes to infinity) appears to obey the
<br />
<div style="text-align: center;">
<b>Cuckoo Cycle Conjecture:</b>
f<sub>i</sub> = a<sub>i-1</sub> * a<sub>i</sub>, where a<sub>-1</sub> = a<sub>0</sub> = 1, and a<sub>i+1</sub> = 1 - e<sup>-a<sub>i</sub></sup></div>
f<sub>i</sub> could equivalently be defined as the fraction of edges whose first endpoint is the middle of a (not necessarily simple) path of length 2i.<br />
<br />
So far I have only been able to prove the conjecture for i ≤ 3.
For instance, for i = 1, the probability that an edge endpoint is not the endpoint
of any other edge is (1-1/N)<sup>N-1</sup> ~ 1/e.
Here's hoping someone finds an elegant proof...
https://blog.computationalcomplexity.org/2019/04/cuckoo-cycles.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-5766992926243003607Mon, 01 Apr 2019 16:43:00 +00002019-04-01T12:43:19.930-04:00An Interdisciplinary approach to P vs NPI have a grant with some brain scientists on the following exciting approach to P vs NP.<br />
<br />
We want to prove:<br />
<br />
There is no algorithm for SAT in P<br />
<br />
This seems hard. So lets scale down our goals to:<br />
<br />
Lance cannot find an algorithm for SAT in P<br />
<br />
You can replace Lance with someone else, but Lance has volunteered to have brain scans done. The idea is to scan the P vs NP part of his brain and see what we can discern.<br />
<br />
I know what you are thinking. Lance truly believes that SAT is NOT in P so perhaps even if SAT is in P, he would have a mental block. Hence I am hoping to also get some serious theorists that think SAT is in P to participate. This might also shed light on the following conjecture: is it easier to prove a theorem if you believe it is true.<br />
<br />
Lance has proposed another line of research. Barriers. Try to establish<br />
<br />
Lance cannot prove that SAT is NOT in P<br />
<br />
using brain scans and he volunteered.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-w0aJgcjWXp0/XI-8jhzGnlI/AAAAAAABmv4/xmXbmb5HDy4zahASbPwc-RjOqeRjLD0DgCLcBGAs/s1600/mribrain.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="397" data-original-width="322" height="320" src="https://1.bp.blogspot.com/-w0aJgcjWXp0/XI-8jhzGnlI/AAAAAAABmv4/xmXbmb5HDy4zahASbPwc-RjOqeRjLD0DgCLcBGAs/s320/mribrain.jpg" width="259" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Brain Scan of Lance's Proving Ability</td></tr>
</tbody></table>
<br />
For this one the mental block problem is gone; however, as you can clearly see from his brain scan, Lance will never prove that SAT is not in P. Seven years as department chair has caused irreversible damage to his ability to reason logically.<br />
<br />
We hope to recruit other theorists to the project. The sticking point might be privacy: if we prove that professor X cannot solve P vs NP will the affect their being hired? For this reason we will restrict the study to professors with Tenure. But this is a weakness of the study since we had wanted to study if younger people have a better chance to resolve P vs NP. So we need to find very young tenured professors.<br />
<br />
After we get the technology working on Theorists and P vs NP we will try to expand it for home use. For example, if a spouse claims <i>I could never learn to cook </i>or <i>I could never learn to drive (that's me) </i>their partner will be able to verify the statement. It is not clear if this will make the divorce rate go up or down. Or if a child says <i>I just can't do algebra</i> the parents can test the child and say <i>Oh yes you can</i>!https://blog.computationalcomplexity.org/2019/04/an-interdisciplinary-approach-to-p-vs-np.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-2959222585780083759Thu, 28 Mar 2019 11:26:00 +00002019-03-28T07:26:54.282-04:00ScoopedAt Dagstuhl I got a few ideas for future posts but then...<br />
<br />
We had some discussions about STOC allowing program committee members to submit papers that I planned to post about. But then Suresh wrote a <a href="http://blog.geomblog.org/2019/03/on-pc-submissions-at-soda-2020.html">fine post</a> on the same issue for SODA. My thoughts: PC members should not submit--no matter how you try to avoid the conflict of interest, there will always be a cloud on the process. Suresh suggest blind reviews that other non-theory conferences use, but I prefer the tiered PC system. It's fine to have PC members submit papers if the top of the tier, a senior PC or the PC chairs, makes the final calls.<br />
<br />
I was also going to post about Yann LeCun's <a href="https://www.facebook.com/story.php?story_fbid=10152719972317143&id=722677142">Facebook rant</a> about stodgy CS departments but then Yann goes ahead and <a href="https://www.nytimes.com/2019/03/27/technology/turing-award-ai.html">wins a Turing award</a> with Geoffrey Hinton and Yoshua Bengio for their work on machine learning. I knew Yann from when we worked together at NEC Research in the early 2000's and let's just congratulate him and the others and let them bask in glory for truly transforming how we think of computing today. I'll get back to his post soon enough.https://blog.computationalcomplexity.org/2019/03/scooped.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-2572656159267507055Sun, 24 Mar 2019 21:13:00 +00002019-03-24T22:22:36.543-04:00Random Thoughts on the admissions scandalIn light of the recent academic scandal I am going to list ways I've heard to help get your kid into college and thoughts on how ethical they are (hint: bribing a coach to claim your kid is on the rowing team is not ethical).<br />
<br />
1) Your kid likes (1) helping the homeless and (2) Ramsey Theory and (3) helping the homeless learn Ramsey Theory. Or perhaps they like rowing or Latin or fencing or Pig Latin or.... Great! encourage them, get them books and tutors, and whatever they need. You have an eye towards how this will look on for college admissions; however, it is your kids choice as to what they like. Also note that these activities are in addition to doing well in school, SATs, etc, not instead of it. Perfectly ethical, though I note that this avenue is not open to poor families and in some cases even middle class families.<br />
<br />
2) Item 1 is the extreme on a spectrum in terms of how much are the extra things the kid does there idea OR planned by you to GET INTO A GOOD COLLEGE. This item will be the other extreme, but realize there is a continuum (actually I doubt there are a continuum number of options here, but there are many in between. Maybe its omega + omega*.) You have heard that being on the <a href="https://en.wikipedia.org/wiki/Chess_boxing">chess boxing</a> teams is good on a college application so you TELL YOUR KID that they likes both Chess AND Boxing and should be on the team. You also hear this about being on the fencing team and knowing <a href="https://en.wikipedia.org/wiki/Pig_Latin">pig latin</a>, so your kid can taunt their opponents like this:<br />
<br />
youah, aint-kay ence-fay orth-way eans-bay<br />
<br />
This might not be as bad as it sounds if the kid learns to like Chess-Boxing. But it may be worse than it sounds if the kid rebels against all of this and becomes a crack whore.<br />
<br />
Is this ethical? It may be bad for the kid, but it may push him into things he ends up liking. One drawback: you've HEARD that being on the chess boxing team is good for college admissions, but is it true?<br />
<br />
And again, not open to some families.<br />
<br />
3) Item 2 (or even 1) but with an addition: Hire a college adviser to help you. Someone who knows (or claims to know) what colleges look for- Trombone, Latin, Chess-boxing, whatever. Still ethical but I again worry about the kids future rehab bills.<br />
<br />
4) Here is where it gets murky. The college adviser helps:<br />
<br />
a) Polish the kids essay (my parents, who are both in English, helped polish my essay to get into graduate school (I don't recall if there was one for ugrad). They told me to use lots of `ing' words so it sounds like I am actively doing things. They also helped me figure out when recursion-theoretic is hyphenated. I got into Harvard but not MIT, so make of that what you will.) Polishing, proofreading, that could be okay. But it can slip into b or c below.<br />
<br />
b) The adviser (or the parents) talk to the kids to find out what to write, but then writes it. Maybe the kid proofreads and polishes. Maybe not even. The adviser is a ghostwriter. Clearly unethical but the line between helping-to-polish and adviser-wrote-it is again a continuum.<br />
<br />
c) Adviser writes it and it is completely fictional. I once heard a rumor that a particular sample of an essay to get into med school was used by several med school applicant. Gee,they can't all have gotten inspired by watching their grandfather in his pajamas die of cancer. This is awful of course, but I wonder- what if the student writes a fictional essay all by themselves! Some combination of how much the essay is true and how much help you got on it is unethical. But some might be okay. Is it bad to polish stories that are basically true to make them flow more easily? Prob not. But there is a 2-dim continuum based on both accuracy and how much help the student got.<br />
<br />
As a side note- how much does the personal statement matter for admissions? I suspect that if an elite school gets LOTS of REALLY QUALIFIED applicants, the essay may be all that distinguishes them.So it can be important. I also wonder if people on admissions can tell if an essay is not written by the applicant. Or maybe if there is an interview that can help detect it.<br />
<br />
5) Parents give X amount of money to the college and the kid gets in. This is talked about a lot though I don't know how common it is for someone NOT qualified to GET IN based on money. College admissions has many factors so its not quite so clear cut what NOT qualified means. Even so, if seems odd that this is not in any way shape or form illegal. It IS transparent, so I guess thats a plus. The argument I've heard is that the money is used for scholarships to fund students who get in but can't afford to go. I do not know if this is true. And this one is only available to the top Z %, not sure what Z is, but there are people who can do 1,2,3,4 who can't do 5. I would call this unethical though colleges don't seem to think so. Or they do but they do it anyway.<br />
<br />
6) Before I list the current scandal I want to list another issue: having a psychologist (or whoever it is who judges these things) say your kid is Learning Disabled so they get more time on the SATs. Perhaps bribing them, or perhaps its understood what you want. Again, I do not know how common this is. An alternative if you can't afford some of the above options, or done in conjunction with a lot of the above options.<br />
<br />
7) The current scandal. Obviously unethical. A few things I wonder about:<br />
<br />
a) One story was that they bribed someone to say their daughter was Learning Disabled and had to take the SAT (or whatever it was) in a separate room, making it easier to change the answers to the correct ones. So twice unethical.<br />
<br />
b) Some of the students were clearly NOT qualified.<br />
<br />
c) A parent does unethical things to get the kid into college.<br />
<br />
The kid later lies to the parents about their grades or their plans<br />
<br />
The parents are SHOCKED that their kids lie and wonder where the learned such behaviour!<br />
<br />
8) Actually Item 2 --Parent has kid do things to plan to get into college-- is interesting for another reason. Are you your resume?<br />
<br />
Imagine that Alice helps the homeless her Sophmore year in High School NOT because she cares about the homeless but because its good for college admissions.<br />
<br />
Alice goes on to do other things that look good for college, NOT because she likes them or cares, but just to get into a good college.<br />
<br />
She gets into an elite college<br />
<br />
Did they take her in the hope she would KEEP doing these things or because she is the KIND OF PERSON who does these things?<br />
<br />
And it gets weirder- she DOES keep doing these things since she's heard its good for Business School (disclaimer- I do not know if its good for B-school)<br />
<br />
More generally, she keeps doing things she doesn't care about to advance. So her outward self really is doing good deeds and such, but her heart is not in it. So if her college or B-school or Job hired her because she DOES these things, that is NOT a lie. If they hired her because they want this KIND OF PERSON then... its a lie but I'm not sure what to make of that.<br />
<br />
9) Is there ANY reason to have legacy matter for admissions? This seems like the dumbest and most easily fixed aspect of the whole process. I have never heard a good argument for it. Ever.<br />
<br />
10) College Sports--- that's an entire blog post or book all by itself, so I won't go there.<br />
<br />
11) One can argue whether helping the homeless, or being on the rowing team, or teaching the homeless how to row, should matter for college anyway. But lets assume that its legit to want people at your college who have lead interesting lives. So charity work or sports might be a MEASURE of that. But beware Goodhart's law:<br />
<br />
<i> When a measure becomes a target is ceases to be a measure.</i><br />
<i><br /></i>
The recent scandal is Goodhart's law on steroids.<br />
(NOTE- I had in earlier version `Goodwin's law' but a commenter corrected me and reminded me that Goodwin's law is that if an internet discussion goes on long enough someone will be compared to Hitler. I wonder if that also applies in discussions by Nazi's.)<br />
<br />
12) Does getting into an Elite College really increase your income or happiness (these are two very different questions) over the course of your life? I do not know-- if you do, please comment.<br />
<br />
13) (ADDED LATER) A commenter pointed out that one could also go to a school outside of the USA that values proficiency in the chosen discipline over the items above. Excellent question that raises a few more:<br />
<br />
Do schools outside of the USA hold Americans (or for that matter any non-citizen of their country) to a higher standard for admissions? I ask non-rhetorically.<br />
<br />
If you get a degree from outside of the USA will that help or hurt your job prospects in the USA? Of course this depends on the school you goto, but even with that I do not know the answer.<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2019/03/random-thoughts-on-admissions-scandal.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-2570215373323645628Thu, 21 Mar 2019 10:11:00 +00002019-03-21T06:11:18.378-04:00Back at Dagstuhl<div class="separator" style="clear: both; text-align: center;">
<a href="https://www.dagstuhl.de/Gruppenbilder/19121.01.l.jpg" imageanchor="1"><img border="0" data-original-height="533" data-original-width="800" height="212" src="https://www.dagstuhl.de/Gruppenbilder/19121.01.l.jpg" width="320" /></a></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-GEp5KM-SUA4/XJJZrdR0SrI/AAAAAAABmzo/-77gRJWCTY814teJFCINLxABFNIohHF8QCKgBGAs/s1600/IMG_20190320_090009.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="1200" data-original-width="1600" height="240" src="https://4.bp.blogspot.com/-GEp5KM-SUA4/XJJZrdR0SrI/AAAAAAABmzo/-77gRJWCTY814teJFCINLxABFNIohHF8QCKgBGAs/s320/IMG_20190320_090009.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Participants and Their Research Interests</td></tr>
</tbody></table>
<br />
This week I'm in Germany for the Dagstuhl workshop on <a href="https://www.dagstuhl.de/en/program/calendar/semhp/?semnr=19121">Computational Complexity of Discrete Problems</a> well timed for Georgia Tech spring break. No Bill, so no <a href="https://blog.computationalcomplexity.org/2018/09/still-typecasting-from-dagstuhl.html">typecast</a>, no <a href="https://blog.computationalcomplexity.org/2017/03/the-dagstuhl-family.html">family</a>, just a bunch of fellow theorists. New this year, beer.<br />
<br />
Dagstuhl always had bottled beer (and wine), after all this is Germany. However, Ronen Shaltiel is living his lifelong dream of bringing a keg to Dagstuhl. Turns out Dagstuhl had a refrigerator/tap for a beer keg, one only needs to order and pay for the beer. Ronen's daughter designed a special logo, though the keg contains Bitburger, a fine German pilsner. Prost to Ronen and thanks for the beer.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://3.bp.blogspot.com/-L7gbzTPK6t8/XJIeFNgMlwI/AAAAAAABmyU/8HxYbP69pVI91P9I-m3y4aXhlYEzwWqxwCKgBGAs/s1600/MVIMG_20190318_181047.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1600" data-original-width="1200" height="200" src="https://3.bp.blogspot.com/-L7gbzTPK6t8/XJIeFNgMlwI/AAAAAAABmyU/8HxYbP69pVI91P9I-m3y4aXhlYEzwWqxwCKgBGAs/s200/MVIMG_20190318_181047.jpg" width="150" /></a><a href="https://1.bp.blogspot.com/-3yFv9qZFvkM/XJIeFPPmYSI/AAAAAAABmyU/iF8pnxyAO7wh8owT8A3RhFnMsCmvlzySgCKgBGAs/s1600/IMG_20190318_193159.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1200" height="200" src="https://1.bp.blogspot.com/-3yFv9qZFvkM/XJIeFPPmYSI/AAAAAAABmyU/iF8pnxyAO7wh8owT8A3RhFnMsCmvlzySgCKgBGAs/s200/IMG_20190318_193159.jpg" width="150" /></a><a href="https://2.bp.blogspot.com/-XLdHqofvmbQ/XJIfEQ3YBSI/AAAAAAABmyg/sfQphG1tRLQruYk30IytbJ_yKYYxpWAdQCLcBGAs/s1600/shaltieliner.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1600" height="200" src="https://2.bp.blogspot.com/-XLdHqofvmbQ/XJIfEQ3YBSI/AAAAAAABmyg/sfQphG1tRLQruYk30IytbJ_yKYYxpWAdQCLcBGAs/s200/shaltieliner.jpg" width="200" /></a></div>
<br />
Of course the fun is hanging with colleagues old and new. Talking about open problems old and new. Used to solve more of them back in the day, now it seems harder.<br />
<br />
I did learn a new old theorem, planarity testing, whether you can embed a given graph in the plane so no two edges cross, is computable in log space. In 2000 Eric Allender and Meena Mahajan <a href="https://doi.org/10.1016/j.ic.2003.09.002">showed</a> that you can test for planarity in symmetric log space, basically the complexity class whose complete problem is undirected connectivity. In 2005, Omer Reingold <a href="https://doi.org/10.1145/1391289.1391291">famously showed</a> that undirected connectivity is computable in log-space. Thus planarity testing is in log-space, a result you might have missed if you didn't know both papers.<br />
<br />
This came out in Eric's talk on his work with Archit Chauhan, Samir Datta and Anish Mukherjee <a href="https://eccc.weizmann.ac.il/report/2019/039/">showing</a> that checked whether there is a directed path from a given node s to a given node t in planar graphs can be computed by concurrent-read exclusive-write on parallel random-access machines in logarithmic time, and thus likely weaker than directed s-t paths on general graphs.https://blog.computationalcomplexity.org/2019/03/back-at-dagstuhl.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-4318994903152354716Sun, 17 Mar 2019 22:55:00 +00002019-03-17T18:55:24.462-04:00Third Poll on P vs NP and related Questions is out now! And the winner is Harambe!<br />
I took a poll of the theory community (and others) about P vs NP and related issues in 2002, 2012, and 2019 (sorry its not an arithmetic sequence --- read the third poll article to see why). The 2002 and 2012 polls are on the web (see <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper1.pdf">here</a> and <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper2.pdf">here</a> ), and now the third poll is out and its <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf">here</a> or <a href="https://dl.acm.org/citation.cfm?doid=3319627.3319636">here</a> . All three appear in Lane's Complexity Column in SIGACT News.<a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper1.pdf"></a><br />
<br />
I'll give some highlights and thought about the third poll, but for more read the article. Or read all three and see how opinions have changed over time.<br />
<br />
0) How many respondents: 100 the first time, and 152 the second time, 124 the third time.<br />
<br />
1) P≠NP is at about 80%. When restricted to people who have thought about the problem a lot (my judgement) then it goes to 99%. The strongest P≠NP is by Lance who says<br />
<br />
People who think P=NP are like people who believe Elvis is alive.<br />
<br />
I disagree. I think Elvis is alive and is trying to prove P=NP.<br />
<br />
2) When will it be solved? 66% thought it would be solved before 2100, a bit more than in prior years. But also more thought it would never be solved. Some commented that a computer might solve it. I doubt that, but I do think this poll will be done by a computer in 10 years.<br />
<br />
3) Because I used Survey monkey (1) each question got more answers, and (2) most questions got a forced YES or NO so less funny comments or room for creative answers. People could still leave comments, and some did.<br />
<br />
4) Related to point (3): The last time I did the poll P=BPP was thought by everyone <i>who answered</i> <i>the question</i>. This year far more people answered it and quite a few thought P≠BPP. This may be because Survey monkey had a psychological affect of making people vote even if they didn't really know (people who have thought a lot about P vs NP all thought P=BPP). Has there been evidence that P≠BPP that I am unaware of? Or since there has not been that much progress on it maybe they are unequal. 10 years ago I would have thought we would have L=RL by now.<br />
<br />
5) The last time I did the poll 10 people thought factoring IS in P and the NSA or the KGB knows that. This time around nobody thought that. Why? Those 10 people have vanished mysteriously.<br />
<br />
6) Five people thought P vs NP will be resolved by Harambe. That is more than any person got.<br />
<br />
7) Is this poll worth doing? I would say yes (gee, I have to having done his poll three times) because it is good to have an objective record of subjective opinion. <br />
<br />
8) I'll give some of my answers: P≠NP, Elvis is dead, and both will be proven in the year 2525. For more about the future see <a href="https://www.youtube.com/watch?v=yesyhQkYrQM">this</a>.<br />
<br />https://blog.computationalcomplexity.org/2019/03/third-poll-on-p-vs-np-and-related.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-7275002484261338073Thu, 14 Mar 2019 14:08:00 +00002019-03-14T10:08:04.425-04:00Captain EinsteinIf the president of the United States uses "complexity" in a tweet, I can't leave it alone.<br />
<blockquote class="twitter-tweet" data-lang="en">
<div dir="ltr" lang="en">
Airplanes are becoming far too complex to fly. Pilots are no longer needed, but rather computer scientists from MIT. I see it all the time in many products. Always seeking to go one unnecessary step further, when often old and simpler is far better. Split second decisions are....</div>
— Donald J. Trump (@realDonaldTrump) <a href="https://twitter.com/realDonaldTrump/status/1105468569800839169?ref_src=twsrc%5Etfw">March 12, 2019</a></blockquote>
<script async="" charset="utf-8" src="https://platform.twitter.com/widgets.js"></script>
<br />
<blockquote class="twitter-tweet" data-lang="en">
<div dir="ltr" lang="en">
....needed, and the complexity creates danger. All of this for great cost yet very little gain. I don’t know about you, but I don’t want Albert Einstein to be my pilot. I want great flying professionals that are allowed to easily and quickly take control of a plane!</div>
— Donald J. Trump (@realDonaldTrump) <a href="https://twitter.com/realDonaldTrump/status/1105471621672960000?ref_src=twsrc%5Etfw">March 12, 2019</a></blockquote>
I got my MIT degree in Applied Mathematics so I don't count, but I know plenty of MIT computer scientists and the one undeniable truth is that I don't want any of them flying my plane.<br />
<br />
I also agree with the Donald that a complex environment can often lead to confusion, especially in an emergency. HCI matters.<br />
<br />
But that's where it stops. Better technology in the plane and on the ground, combined with better procedures have all but eliminated deadly major commercial airplane crashes in the US and quite rare in the world at large. I'll call that more than a "little gain". I remember the "old and simpler" days where we had deadly airline crashes every few months. No thanks.<br />
<br />
I've had great discussions with some of the aerospace engineering professors at Georgia Tech. The amount of effort to get the "front-of-the-plane" software right via formal methods and rigorous testings has become harder to engineer than the plane itself. The "back-of-the-plane" software that controls the video screens and WiFi gets less attention. I can live with safety over movies.<br />
<br />
When technology makes things much safer, whether it be planes or self-driving cars, the rare accidents become far more noticeable. while we should use these opportunities to learn and make things safer, the rare accidents help us realize just how much more safer technology can make us.<br />
<script async="" charset="utf-8" src="https://platform.twitter.com/widgets.js"></script>
https://blog.computationalcomplexity.org/2019/03/captain-einstein.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-5113460714750651988Sun, 10 Mar 2019 21:26:00 +00002019-03-10T17:26:17.902-04:00Richard Karp: His influence and how to honor himWhen I first saw the definition of NP-Complete I first thought<i> if there are NP-complete problems I suspect they are contrived. </i>When I saw the proof that SAT is NP-complete I thought <i>okay, so there is one natural problem NP-complete by a trick of encoding, but I suspect there aren't any more.</i> I then read Karp's article that had 22 NP-complete problems. I thought <i>okay, there are 22, but I suspect there are no more. </i>No I didn't think that. But the point is that Cook and Karp together birthed modern complexity theory by introduction NP-completeness and showing that there are MANY natural problems that are NP-complete.<br />
<br />
How many people has Richard Karp inspired? I don't know but I suspect it's a cardinal between countable and the reals so it may depend on your model of set theory. Later in this post I will present Samir Khuller's story of how Richard Karp inspired him.<br />
<br />
How to honor him? The Simons inst. is currently welcoming contributions to the Richard M Karp Fund, which honors the scientific contributions of Founding Director Dick Karp. The fund will provide vital support for the mission and activities of the Simons institute. They have a deadline of Pi-Day. You can go <a href="https://simons.berkeley.edu/support/donate">here</a> to contribute and/or <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/goldwasserkarp.txt">here</a> for a letter from Shafi Goldwasser, Prabhakar Raghavan, and Umesh Vazirani about the fund.<br />
<br />
OKAY, Samir's story:<br />
<br />
<div>
<b>Mentoring and Influence via a Train Journey...</b></div>
<div>
<br /></div>
<div>
Almost to the day, 33 years ago I was running from my dorm room to catch an unreliable bus to the train station as I headed home for a mid-semester break. On the way,I stopped by the mailroom, and not knowing where to put the CACM that had just arrived, stuffed it into the side of my bag and in the process, dropping my notebook in the process. On the train, when I looked for my notebook to go over some material I realized it was missing! All I had was a CACM and a very long train ride. Skimming through the journal, I found Karp’s Turing Award article “Combinatorics, Complexity, and Randomness“. I started reading this article, and was riveted! It was one of those life changing moments for me, when my immediate future became clear - I wanted to study Theoretical Computer Science and specifically the complexity of combinatorial problems. Without ever having met Dick Karp, he changed my life forever.</div>
<div>
<br /></div>
<div>
I met Dick long after he influenced me via his Turing Award Lecture and it was a real privilege to have had the opportunity to interview him via a fireside chat at Simons. See <a href="https://www.youtube.com/watch?v=g1DT_UeJwps">here</a>.</div>
<div>
<br /></div>
<div>
I am delighted about the fund Bill mentions above as the money that goes to it will help inspire others as Karp inspired me.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<br />
<br />https://blog.computationalcomplexity.org/2019/03/richard-karp-his-influence-and-how-to.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-5011417931001574576Fri, 08 Mar 2019 15:05:00 +00002019-03-08T10:05:52.288-05:00QEDVia <a href="https://www.scottaaronson.com/blog/?p=4133">Scott</a>, John Horgan wrote a <a href="https://blogs.scientificamerican.com/cross-check/the-horgan-surface-and-the-death-of-proof/">blog post</a> following on his 1993 Scientific American article <a href="https://blogs.scientificamerican.com/cross-check/the-horgan-surface-and-the-death-of-proof/">The Death of Proof</a>. The article talked about computer-generated proofs, experimental mathematics and even mentioned some of our work on <a href="https://doi.org/10.1145/103418.103428">transparent proofs</a> (basically time-efficient probabilistically checkable proofs). I got (sarcastically I think) accused of killing mathematics after that article but of course we had traditional proofs about probabilistically check proofs. Andrew Wiles got a sidebar titled "A Splendid Anachronism?" for merely solving the most famous open problem in all of mathematics. Somehow traditional mathematical proofs survived the article.<div>
<br /></div>
<div>
Meanwhile in CACM, Moshe Vardi writes <a href="https://cacm.acm.org/magazines/2019/3/234913-lost-in-math/fulltext">Lost in Math?</a> </div>
<blockquote class="tr_bq">
TCS is surely blessed with mathematical beauty. As a graduate student a long time ago, it was mathematical beauty that attracted me to TCS, and continued to lead my research for many years. I find computational complexity theory (or complexity theory, for short), with its theorems (for example, the time-hierarchy and space-hierarchy theorems) and its open questions (for example, P vs NP), to be hauntingly beautiful. Beauty, yes; but what about truth?</blockquote>
Here here on the beauty of complexity. So what about truth? I cover much of this in my <a href="https://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext">P v NP survey</a>. In short the P v NP captures the most critical aspects of what is efficiently computable but it is not the endpoint. Nevertheless P v NP captures both truth and beauty and that's why the problem has so captivated and guided me throughout my research career.https://blog.computationalcomplexity.org/2019/03/qed.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-7118957481360007833Mon, 04 Mar 2019 20:58:00 +00002019-03-05T21:09:16.473-05:00How are there 20 copies of my new book through other booksellers and why are they so highly priced(This is about my book PROBLEMS WITH A POINT: exploring Math and computer science<br />
by Gasarch and Kruskal, <a href="https://www.amazon.com/Problems-Point-Exploring-Computer-Science/dp/9813279974/ref=sr_1_1?keywords=gasarch&qid=1551731760&s=gateway&sr=8-1">here</a>. This post is NOT a plug.)<br />
<br />
I often see weird pricing on amazon but don't have enough inside information to explain it. This time I have seen some weird pricing on amazon but DO have enough information to be truly baffled.<br />
<br />
My book is on amazon. You can buy it<br />
<br />
Softcover new: $38.00<br />
<br />
Hardcover new: $68.00<br />
<br />
Okay, that all makes sense.<br />
<br />
OR you can buy it from some other source.<br />
<br />
There are 10 copies of the softcover, they claim new, ranging from $38.00 to $57.00.<br />
<br />
There are 2 copies of the softcover, they claim used (how used could it be?), $49 and $53<br />
<br />
There are 9 copies of the hardcover, they claim new, ranging from $68.00 to $91.00<br />
<br />
There are 2 copies of the hardcover, they claim used, $84.00 and $88.00<br />
<br />
This raises two questions<br />
<br />
1) I have a copy, Clyde got a copy, and two copy's were send to reviewers. Neither Clyde nor I have sold our copy. So how did 20 or so copies get out there?<br />
<br />
2) Why do they cost MORE than list price.<br />
<br />
I've asked around and got some answers, but I INVITE you to give more possible answers. If your answer is not just speculation (e.g., `I used to be in the black market book business and here's the real scoop') then that would be great; however, I will take specuation<br />
<br />
POSSIBLE EXPLANATIONS FOR HOW SOMEONE GOT COPIES<br />
<br />
1) Clyde and I haven't gotten our free copies yet. Hijacked? Here's hoping the hijackers read it and enjoyed it before posting it. However, this theory is unlikely since I inquired with World Scientific (our publisher) and found out we'll be getting our free copies in 2 weeks. So this theory will either be confirmed or denied in 2 weeks. I would bet against OR those are some really bad hijackers.<br />
<br />
2) Complete ripoff. You pay the money and get NOTHING. I think this was more likely in the early days of amazon (or e-bay or....) but now things are pretty well monitored. I have sold books on amazon and am very impressed with how foolproof it is. Still --- could be.<br />
<br />
3) Someone hacked my computer. Really? Where did they get the orange covers? Why would they bother? This is not Harry Potter. Plus I asked our staff and NO this could not happen.<br />
<br />
4) Some of the shipment dates are fairly far in the future, so they plan to get an order, then<br />
order the book, and have it send to the buyer, at a profit. Seems like too much sugar for a satoshi, BUT could be profitable if its a bot and its automated to do this with lots of books.<br />
<br />
5) My publisher also send the book to other sellers. That does not explain the higher prices.<br />
<br />
WHY THE HIGHER PRICES?<br />
<br />
1) They are counting on people assuming that other sellers are cheaper without checking. Would people do that? People still fall for the Nigerian billionaire scam, so maybe yes.<br />
<br />
2) The seller themselves, which is possibly an army of bots, didn't bother checking but priced it<br />
similar to other books. This is plausible since $38.00 is fairly cheap, so looking at similar books may get you a higher price.<br />
<br />
-----<br />
Any speculation is welcome so long as it does not involve space aliens or astrology.<br />
<br />
<br />https://blog.computationalcomplexity.org/2019/03/how-are-there-20-copies-of-my-new-book.htmlnoreply@blogger.com (GASARCH)6tag:blogger.com,1999:blog-3722233.post-4197054057663794908Thu, 28 Feb 2019 13:50:00 +00002019-02-28T08:50:40.970-05:00Flying Pigs Unsafe at Any SpeedTake a moment and imagine a flying pig. Do you see a pig with tiny wings lazily guiding along. But pigs are not particularly slow animals as anyone has seen a <a href="https://youtu.be/-eMV1jxfl40?t=73">pig race</a> at a county fair can attest to that. So why not in the air shouldn't a pig go faster than an unladen African swallow?<br />
<br />
I have a point discussing the fastness of a flying pig. Consider my favorite flying pig, P = NP. I would put more probability on an actual flying pig (thanks CRISPR) than polynomial-time algorithms for traveling salesman.<br />
<br />
Sometimes I get in the following conversation:<br />
<br />
<b>AI person</b>: The P v NP problem is irrelevant as we have machine learning and SAT solvers and we can for all practical purposes solve NP-complete problems.<br />
<b>Me</b>: If P = NP we can solve AI!<br />
<b>AI</b>: If P = NP it's likely to have a very slow poly-time algorithm with high exponents and constants and be for all practical purposes useless.<br />
<br />
Let's break that down. The claim is E(running time of SAT|running time of SAT is poly) = cn<sup>k</sup> for some large c and k. First of all you are conditioning on a probability zero event. Beyond that nearly all the known problems we know that sit in polynomial time have practical efficient solutions. So under the assumption that SAT is one of these problems, why shouldn't the same rule apply. You've already made the assumption we can reduce its running time from exponential to polynomial, so why would it stop at some high polynomial?<br />
<br />
If we are going to talk about the hypothetical flying pig P = NP world, let my algorithms run fast.https://blog.computationalcomplexity.org/2019/02/flying-pigs-unsafe-at-any-speed.htmlnoreply@blogger.com (Lance Fortnow)6tag:blogger.com,1999:blog-3722233.post-4283341625722054774Tue, 26 Feb 2019 17:20:00 +00002019-02-27T00:20:10.380-05:00Problems with a Point: Exploring Math and Computer Science<br />
As you can see from Lance's tweet<br />
<br />
<br />
Problems with a Point: Exploring Math and Computer Science<br />
by Gasarch and Kruskal<br />
<br />
(ADDED LATER- the World scientific website has more info than amazon and has a table of contents, so here it is: <a href="https://www.worldscientific.com/worldscibooks/10.1142/11261#t=toc">here</a>)<br />
<br />
is now available! The tweet says its $68.00 but that's hardcover- paperback is $38.00 (are covers that expensive) and if you like your books already broken in, there are some used copies for $89.00. Makes sense to me (no it doesn't!). Could be the topic of a blog post (probably already was).<br />
<br />
Okay, so whats in the book? One of my favorite types of blog posts is when I make a point ABOUT math and then do some math to underscore that point. I went through all of my blogs (all? No, I doubt I did that) and picked out blogs of that type. With Clyde's help we EXPANDED and POLISHED and GOT THE MATH RIGHT (in some cases I didn't have any math so we had to supply it).<br />
<br />
When I first got a copy (about a month ago) I just couldn't stop reading it. I really like it! This is a non-trivial remark -- often authors get tired of their book, or after a while and wonder things like ``why did I write 300 page on the muffin problem? What was I thinking?'' So the fact that I am very pleased with it is not obvious. Does it mean you will?<br />
<br />
If you ever thought `I wish bill would clean up his posts spelling and grammar AND expand on the math AND make it a more cohesive whole' then buy the book!<br />
<br />
I will in future posts describe more about writing the book, but this is probably my last post where I plug the book.<br />
<br />
bill g.https://blog.computationalcomplexity.org/2019/02/problems-with-point-exploring-math-and.htmlnoreply@blogger.com (GASARCH)6