tag:blogger.com,1999:blog-3722233Tue, 04 Aug 2020 04:09:09 +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)Blogger2770125tag:blogger.com,1999:blog-3722233.post-1233384953933252805Mon, 03 Aug 2020 02:02:00 +00002020-08-03T00:32:26.968-04:00The Gauss story is false yet we still tell it. Should we?<br />
When teaching discrete math a while back I told the following story which some had already heard in High School: <br />
<i><br /></i>
<i>When Gauss was in 1st grade the class was being bad. So the teacher made them sit down and add up the numbers from 1 to 100. Gauss did it in 2 minutes by noting that if S was the answer then </i><br />
<i><br /></i>
<i>2S = (100+1) +(99+2) + ... + (1 + 100) = 100*101</i><br />
<i><br /></i>
<i>So S = 50*101. Then he went to Google and typed in 50*101 for the answer.</i><br />
<i><br /></i>
The class laughed because of course the last part about Google was false. But I then told them that the entire story was false and showed them the following slides: <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/gaussstory.pdf">here</a> Take a look at them (there are only 4 of them) before reading on.<div><br /></div><div>(ADDED LATER: here is an article by Brian Hayes that documents the history of the story.</div><div><br /></div><div><a href="http://bit-player.org/wp-content/extras/bph-publications/AmSci-2006-05-Hayes-Gauss.pdf" target="_blank">http://bit-player.org/wp-content/extras/bph-publications/AmSci-2006-05-Hayes-Gauss.pdf</a></div><div><br /></div><div>)<br />
<br />
<br />
So I told them the Gauss Story was false (I am right about this) and then told them a lie- that the story's progression over time was orderly. I then told them that that was false (hmmm- actually I might not of, oh well).<br />
<br />
One of my students emailed me this semester<br />
<br />
<i>Dr Gasarch- one of my Math professors is telling the Gauss story as if its true! You should make a public service announcement and tell people its false!</i><div><i><br /></i></div><div>I do not think this is needed. I also don't know how one goes about making a public service announcement I also suspect the teacher knew it was false but told it anyway.<div>
<br />
OKAY- what do you do if you have a nice story that has some good MATH in it but its not true?<br />
<br /><b>Options:</b></div><div><br /></div><div>Tell it and let the students think its true.</div><div><br /></div><div>Tell it and debunk it.</div><div><br /></div><div>Tell it and debunk it and tell another myth</div><div><br /></div><div>Tell it and debunk it and tell another myth and then debunk that</div><div><br /></div><div>Ask your readers what they would do. Which I do now: What do you do? <br /><br /></div></div></div>https://blog.computationalcomplexity.org/2019/04/the-gauss-story-is-false-yet-we-still.htmlnoreply@blogger.com (Unknown)7tag:blogger.com,1999:blog-3722233.post-3389282706697250678Mon, 27 Jul 2020 03:18:00 +00002020-07-26T23:18:26.463-04:00Do computers make us more safe or less safe?Norbert Weiner wrote a paper <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/moral.pdf">Some Moral and Technical Consequences of Automation</a> in 1960. It warns of the dangers of computers in two ways:<br />
<br />
1) If a chess program is only trained against expert chess players then it might get confused if its opponent makes a bad move. This is not dangerous. But imagine a nuclear missle system that assumes the opponent is rational. If the opponent is not rational then it might launch and have an accidental nuclear war. So <i>there must be a human component </i>so that this won't happen.<br />
<br />
I offer a story and a counter narrative. In the 5th season, 23rd episode of the TV show Castle,<br />
title <i>The Human Factor </i>a character had the following story to tell:<br />
<i><br />
The drone on its own was going to bomb a car. But the human noticed that there were red roses on the car, so it was a wedding couple, not a terrorist. If a human had not been involved the drone may have killed an innocent just married couple!</i><br />
<br />
This scene bothered me. It could EASILY be the other way around: the human wants to bomb and the drone (which has better vision) notices the roses. Or there may be many other ways that a computer could be BETTER than a human. I am not saying that a completely automated system is better, I am saying that its not obvious which way to go. Both in some combination? What combination? Who has the final say? And in the drone scenario there may not be time for a human to consider the options.<br />
<br />
2) The Sorcerer's apprentice scenario. In The Sorcerer's Apprentice segment of the (original) movie Fantasia, Mickey mouse tells a broom to get him a glass of water. The broom keeps bringing him water and Mickey almost drowns. Computers may take orders to literally and not stop. I wonder if automated stock-trading and automated auctions may have this problem. Is there a case known where this really did cause a problem?<div><br /></div><div>So what do you think?</div><div><br /></div><div>NOW- do computers (or, more generally technology) make us more safe or less safe?</div><div><br /></div><div>FUTURE- same question.</div>https://blog.computationalcomplexity.org/2020/07/do-computers-make-us-more-safe-or-less.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-8081773524220393104Fri, 24 Jul 2020 16:21:00 +00002020-07-24T12:23:39.872-04:00Virtual ComplexityThe <a href="https://computationalcomplexity.org/Archive/2020/fullsite/">Complexity Complexity Conference</a>, the conference that shares its name and URL with this blog, originally scheduled for Saarbrücken will be held virtually next week. Registration is free for non-authors. <a href="https://www.youtube.com/channel/UCXgNLnzWOP4bM2-xfHDHUrw">Talks</a> are already posted. Looking forward to seeing you at the business meeting and the social.<br />
<div>
<br /></div>
<div>
<div>
Award winners have already been announced: The Best Student Paper Award goes to Rahul Ilango for <a href="https://drops.dagstuhl.de/opus/volltexte/2020/12583/">Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas</a> and the Best Paper Award goes to Daniel Dadush and Samarth Tiwari for <a href="https://drops.dagstuhl.de/opus/volltexte/2020/12586/">On the Complexity of Branching Proofs</a>.</div>
</div>
<div>
<br /></div>
<div>
Virtual conferences give an opportunity for far more people to attend since you don't have the expense and time needed to go to Germany. On the other hand it's hard to dedicate time for a conference when you aren't there. I missed STOC which would have been walking distance from where I live but I did attend parts of the <a href="http://ec20.sigecom.org/">Economics and Computation</a> conference which was supposed to be in Budapest. EC made great use of <a href="http://gather.town/">gather.town</a> where you can wander around virtual rooms bumping into and talking to people. I caught up with a few people there. Complexity plans to use gather for its social meeting next week. Looking forward to the virtual beer.</div>
https://blog.computationalcomplexity.org/2020/07/virtual-complexity.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-2418581440113974615Sun, 19 Jul 2020 19:12:00 +00002020-07-20T17:26:04.931-04:00Erdos-Turan for k=3 is True! (All of the math in this post is summarized (without proofs) in a writeup by Erik Metz and myself which you can find <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/3apblog.pdf">here</a>. It is a pdf file so you can click on links in it to get to the papers it refers to. There have been posts on this topic by <a href="https://gilkalai.wordpress.com/2020/07/08/to-cheer-you-up-in-difficult-times-7-bloom-and-sisask-just-broke-the-logarithm-barrier-for-roths-theorem/">Gil Kalai</a> and <a href="https://lucatrevisan.wordpress.com/2020/07/08/silver-linings/">Luca Trevisan</a>. If you know of others then let me know so I can add them to this post.)<br />
<br />
<br />
<br />
This is a sequel to <a href="https://blog.computationalcomplexity.org/2010/12/breakthrough-result-on-density-and-3.html">A BREAKTHROUGH result on density and 3-AP's</a> and <a href="https://blog.computationalcomplexity.org/2017/06/big-news-on-w3r.html">Big news on W(3,r)!</a><br />
<br />
For this post N is large, and all inequalites have a big-O or a big-Omega.<br />
<br />
For this post [N] is {1,...,N}<br />
<br />
Let<br />
<br />
r(N) be the least w such that if A is a subset of [N] and |A| > w, then A has a 3-AP.<br />
<br />
There has been a long sequence of results getting smaller and smaller upper bounds on r(N).<br />
<br />
The motivation for getting these results is that if r(N) is < N/(log N)^{1+\delta} with delta>0 then the following holds:<br />
<br />
If sum_{x\in A} 1/x diverges then A has a 3-AP.<br />
<br />
This is the k=3 case of one of the Erdos-Turan Conjectures.<br />
<br />
Bloom and Sisack HAVE gotten N/(log N)^{1+delta} so they HAVE gotten ET k=3. Wow!<br />
<br />
1) I am NOT surprised that its true.<br />
<br />
2) I am SHOCKED and DELIGHTED that it was proven. Shocked because the results leading up to it (see the write up referenced at the beginning of this post) seemed Zeno-like, approaching the result needed got but not getting there. Delighted because... uh, as the kids say, just cause.<br />
<br />
I've heard that k=4 really is much harder (see my comments and Gil's response on his blog post, pointed to at the beginning of this post) and it is true that there has been far less progress on that case (the write up I pointed to at the beginning of this post says what is known). Hence I will again be <i>shocked </i>if it is proven. So, unlike The Who (see <a href="https://www.youtube.com/watch?v=UDfAdHBtK_Q">here</a>) I CAN be fooled again. That's okay--- I will be <i>delighted</i>. (ADDED LATER- there are more comments no Gil's website, from Thomas Bloom and Ben Green about what is likely to happen in the next 10 years.)<br />
<br />
Erdos offered a prize of $3000 for a proof that A has, for all k, a k-AP. The prize is now $5000. After Erdos passed away Ronald Graham became the Erdos-Bank and paid out the money when people solved a problem Erdos put a bounty on. What happens now? (If I have the facts wrong and/or if you know the answer, please leave a polite and enlightening comment.)<br />
<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2020/07/erdos-turan-for-k3-is-true.htmlnoreply@blogger.com (gasarch)3tag:blogger.com,1999:blog-3722233.post-127536327837647663Sun, 12 Jul 2020 20:18:00 +00002020-07-12T16:18:51.310-04:00Ronald Graham: A summary of blog Posts We had about his workTo Honor Ronald Graham I summarize the blog posts we had about his work.<br />
<br />
1) Blog post <a href="https://blog.computationalcomplexity.org/2016/05/new-ramsey-result-that-will-be-hard-to.html">New Ramsey Result that will be hard to verify but Ronald Graham thinks its right which is good enough for me</a>.<br />
<br />
Wikipedia (see <a href="https://en.wikipedia.org/wiki/Boolean_Pythagorean_triples_problem">here</a>) says that in the early 1980's (can't Wikipedia be more precise than that?) Ronald Graham conjectured the following:<br />
<br />
For all 2-colorings of N, there exists x,y,z all the same color such that (x,y,z) form a Pythagorean triple.<br />
<br />
I cannot imagine he did not also conjecture this to be true for all finite colorings.<br />
<br />
I suspect that when he conjectured it, the outcomes thought to be likely were:<br />
<br />
a) A purely combinatorial (my spell check says that combinatorial is not a word. Really? It gets 14,000,000 hits) proof. Perhaps a difficult one. (I think Szemeredi's proof of his density theorem is a rather difficult but purely combinatorial proof).<br />
<br />
b) A proof that uses advanced mathematics, like Roth's proof of the k=3 case of Sz-density, or Furstenberg's proof of Sz theorem.<br />
<br />
c) The question stays open though with some progress over the years, like R(5).<br />
<br />
What actually happened was<br />
<br />
d) A SAT Solver solves it AND gets exact bounds:<br />
<br />
For all 2-colorings of {1,...,7285} there is a mono Pythag triple.<br />
<br />
There exists a 2-coloring of {1,...,7284} with no mono Pythag triple.<br />
<br />
I wonder if this would have been guessed as the outcome back in the early 1980's.<br />
<br />
-------------------------------------------------------------------------------<br />
2) Blog Post <a href="https://blog.computationalcomplexity.org/2019/05/ronald-grahams-other-large-number-well.html">Ronald Graham's Other Large Number- well it was large in 1964 anyway</a><br />
<br />
Let<br />
<br />
a(n) = a(n-1) + a(n-2)<br />
<br />
I have not given a(0) and a(1). Does there exists rel prime values of a(0) and a(1) such that for all n, a(n) is composite.<br />
<br />
In 1964 Ronald Graham showed yes, though the numbers he found (with the help of 1964-style computing) were<br />
<br />
a(0) = 1786772701928802632268715130455793<br />
<br />
a(1) = 2059683225053915111058164141686995<br />
<br />
I suspect it is open to get smaller numbers, though I do not know.<br />
<br />
<br />
------------------------------------------------------------------------------<br />
3) Blog Post <a href="https://blog.computationalcomplexity.org/2011/12/solution-to-reciprocals-problem.html">Solution to the reciprocals problem</a><br />
<br />
Prove or disprove that there exists 10 natural numbers a,...,j such that<br />
<br />
2011= a+ ... + j<br />
1 = 1/a + ... + 1/j<br />
<br />
I had pondered putting this on a HS math competition in 2011; however, the committee thought it was too hard. I blogged on the problem asking for solutions, seeing if there was one that a HS student could have gotten. The following post (this one) gave those solutions. My conclusion is that it could have been put on the competition, but its a close call.<br />
<br />
All of the answers submitted had some number repeated.<br />
<br />
So I wondered if there was a way to do this with distinct a,...,j.<br />
<br />
I was told about Ronald Grahams result:<br />
<br />
For all n at least 78, n can be written as the sum of DISTINCT naturals, where the sum of<br />
the reciprocals is 1.<br />
<br />
This is tight: 77 cannot be so written.<br />
<br />
Comment on that blog DID include solutions to my original problem with all distinct numbers<br />
<br />
----------------------------------------------------------------------<br />
4) Blog Post <a href="https://blog.computationalcomplexity.org/2013/04/a-nice-case-of-interdisciplinary.html">A nice case of interdisplanary research</a> tells the story of how the study of history lead to R(5) being determined (see <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseykings.pdf">here</a> for the actual paper on the subject). One of the main players in the story is the mathematician<br />
<br />
Alma Grand-Rho.<br />
<br />
Note that this is an anagram of<br />
<br />
Ronald Graham.<br />
<br />
What is the probability that two mathematicians have names that are anagrams. I suspect very small. However, see <a href="https://blog.computationalcomplexity.org/2013/04/post-mortem-on-april-fools-day-joke.html">this</a> blog post to see why the probability is not as small as it might be.<br />
<br />
-----------------------------------------------------------------------<br />
5) Blog Post <a href="https://blog.computationalcomplexity.org/search?q=Meme">Winner of Ramsey Meme Contest</a> This post didn't mention Ronald Graham; however I think he would have liked it.<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2020/07/ronald-graham-summary-of-blog-posts-we.htmlnoreply@blogger.com (gasarch)2tag:blogger.com,1999:blog-3722233.post-713901807945793095Thu, 09 Jul 2020 15:57:00 +00002020-07-09T11:57:23.778-04:00Reflections on Ronald Graham by Steve Butler<div>
<i>Ronald Graham passed away on July 6 at the age of 84. We present reflections on Ronald Graham by </i><i>Steve Butler.</i></div>
<div>
<i><br /></i></div>
<hr />
<div>
<br /></div>
<div>
Getting to work with Ron Graham</div>
<div>
<br /></div>
<div>
Ron Graham has helped transform the mathematics community and in particular been a leader in discrete mathematics for more than 50 years. It is impossible to fully appreciate the breadth of his work in one sitting, and I will not try to do so here. Ron has put his papers online and made them <a href="http://www.math.ucsd.edu/~ronspubs/">freely available</a>, a valuable treasure; and there are still many a hidden gem inside of these papers that are waiting to be picked up, polished, and pushed further.</div>
<div>
<br /></div>
<div>
I want to share about how I got to know and work with Ron. To be fair I knew about Ron long before I ever knew Ron. He was that rare pop-star mathematician who had managed to reach out and become visible outside of the mathematical community. And so as a teenager I read about Ron in a book about Erdos. I thought to myself that this guy sounds really cool and someday I might even get to see him give a talk (if I was lucky).</div>
<div>
<br /></div>
<div>
I went to UC San Diego for graduate school and after a series of near-misses ended up studying under Fan Chung. I passed Ron in the stairwell once, and then also helped them move some furniture between their two adjoining homes (graduate students are great for manual labor). But I became determined to try and find a way to start a conversation with Ron and maybe work up to working on a problem. So I took the usual route: I erased the chalkboards for him.</div>
<div>
<br /></div>
<div>
Before his class on discrete mathematics would start, I would come in and clean the chalkboards making them pristine. It also gave me time to occasionally engage in some idle chat, and he mentioned that his papers list was far from complete. I jumped on it and got to work right away and put his papers online and have been maintaining that list for the last fifteen years. This turned out to be no small feat and required about six months of work. Many papers had no previous online version, and there were even a few papers that Ron had written that he had forgotten about! But this gave me a reason to come to Ron and talk with him about his various papers and then he would mention some problems he was working on with others and where they were stuck and thought I might give them a try.</div>
<div>
<br /></div>
<div>
So I started to work on these problems and started to make progress. And Ron saw what I was able to do and would send me more problems that fit my abilities and interests, and I would come back and show him partial solutions, or computations, and then he would often times fill in the gaps. He was fun to work with, because we almost always made progress; even when we didn't make progress we still understood things more fully. Little by little our publications (and friendship) grew and we now have 25+ joint publications, and one more book that will be coming out in the next few years about the enumerating juggling patterns.</div>
<div>
<br /></div>
<div>
After all of that though, I discovered something. I could have just gone to Ron's door and knocked and he would have talked to me, and given me problems (though our friendship would not become so deep if I had chosen the forthright method). But almost no graduate students in math were brave enough to do it; they were scared off by his reputation. As a consequence, Ron had far fewer math graduate students than you would expect. (To any math graduate student out there, don't let fear stop you from talking with professors; many of them are much nicer than you think, and the ones that are not nice are probably not that great to work with.)</div>
<div>
<br /></div>
<div>
So one of the most important lessons I learned from Ron was the importance of kindness. Ron was generous and kind to everyone (and I really stress the word everyone) that he met. It didn't matter what walk of life you were in, what age you were, or what level of math (if any) that you knew, he was kind and willing to share his time and talents. He always had something in reach in his bag or pocket that he could pull out and show someone and give them an unexpected sense of wonder.</div>
<div>
<br /></div>
<div>
Richard Hamming <a href="https://www.cs.virginia.edu/~robins/YouAndYourResearch.html">once said</a> "you can be a nice guy or you can be a great scientist", the implication being that you cannot do both. Ron showed that you can be a nice guy and a great scientist. And I believe that a significant portion of his success is owed to his being kind; all of us should learn from his examples and show more kindness towards others.</div>
<div>
<br /></div>
<div>
This is only one of many lessons I learned from Ron. Another thing I learned from Ron is the importance of data. I have seen multiple times when we would work on a problem and generate data resulting in what I thought were hopeless numbers to understand. But Ron looked at that same data and with a short bit of trial and error was able to make a guess of what the general form was. And almost inevitably he would be right! One way that Ron could do this was to start by factoring the values, and if all the prime factors were small he could guess that the expression was some combination of factorials and powers and then start to play with expressions until things worked out. Even when I knew what he did, I still am amazed that he was able to do it.</div>
<div>
<br /></div>
<div>
I will miss Ron, I will never have a collaboration as deep, as meaningful, and as personal. I am better for having worked with him, and learning from him about how to be a better mathematician and a better person.</div>
<div>
<br /></div>
<div>
Thank you, Ron.</div>
https://blog.computationalcomplexity.org/2020/07/reflections-on-ronald-graham-by-steve.htmlnoreply@blogger.com (gasarch)2tag:blogger.com,1999:blog-3722233.post-3270621784797289581Mon, 06 Jul 2020 02:19:00 +00002020-07-05T22:19:09.254-04:00A table for Matrix Mortality- what I wanted for Hilbert's 10th problemIn <a href="https://blog.computationalcomplexity.org/2020/05/why-is-there-no-dn-grid-for-hilberts.html">this post</a> I speculated on why I could not find anywhere a table of which cases of Hilbert's 10th problem were solvable, unsolvable, and unknown. (I then made such a table. It was very clunky, which may answer the question.)<br />
<br />
I told my formal lang theory class about Hilbert's 10th problem as a natural example of an undecidable question- that is, an example that had nothing to do with Turing Machines. On the final I asked<br />
<br />
<i>Give an example of an undecidable problem that has nothing to do with Turing Machines.</i><br />
<br />
Because of the pandemic this was a 2-day take home final which was open-book, open-notes, open-web. So they could have looked at my slides.<br />
<br />
And indeed, most of them did give Hilbert's 10 problem (more formally, the set of all polynomials in many vars over Z which have a Diophantine solution).<br />
<br />
But some did not. Some said there could never be such a problem (this is an incorrect answer), Some were incoherent. One just wrote ``Kruskal Trees'' (not sure if he was referring to MSTs or WQOs or to something that Clyde Kruskal did in class one day).<br />
<br />
One student said that the problem of, given a CFG G, is the complement of L(G) also CFG.<br />
This is indeed undecidable and does not have to do with TMs. I doubt the student could have proven that. I doubt I could have proven that. I do not doubt that my advisor Harry Lewis could have proven that, and indeed I emailed him asking for a proof and he emailed me a sketch, which I wrote out in more detail <a href="https://www.cs.umd.edu/users/gasarch/COURSES/452/S20/notes/undcfg.pdf">here</a>.<br />
<br />
The most interesting answer was given by some students who apparently looked at the web (rather than at my slides) for lists of problems and found the following called Matrix Mortality:<br />
<br />
{ (M_1,...,M_L) : such that some product of these matrices (you are allowed to use a matrix many times) is the 0 matrix}<br />
<br />
Why was this the most interesting? The TA did not know this problem was undecidable until he saw it on the exams and looked it up. I did not know it was undecidable until my TA told me.<br />
<br />
I then raised the question: How many matrices to you need and how big do their dimensions have to be?<br />
<br />
Unlike H10, there IS a table of this. In <a href="https://arxiv.org/abs/1404.0644">this paper</a> they have such a table. I state some results:<br />
<br />
Undecidable:<br />
6 matrices, 3x3<br />
4 matrices, 5x5<br />
3 matrices 9x9<br />
2 matrices 15x15<br />
<br />
Decidable<br />
2 matrices 2x2<br />
<br />
So there are some gaps to fill, but there is not the vast gulf that exists between dec and undec for Hilberts 10th problem. I also note that the paper was about UNDEC but mentioned the DEC results, where as the papers on H10 about UNDEC seem to never mention the DEC.<br />
<br />
I am glad to know another natural Undec problem and I will likely tell my students about it next spring. And much like H10, I won't be proving it.<br />
<br />
An open problem in education: how come some of my students got it wrong? gave an answer that was not in my notes or slides? One student told me it was easier to google<br />
<br />
<i>Natural Undecidable Questions</i><br />
<br />
then look through my slides. Another one said:<br />
<br />
<i>In class you said `this is a natural undecidable problem'.</i><br />
<i><br /></i>
<i>On the exam you said `a problem that does not mention Turing Machines'</i><br />
<i><br /></i>
<i>I did not know they were the same. </i><br />
<br />
That student submitted the Matrix problem stated above. It IS a fair point that `natural' is an<br />
undefined term. But the problem on the final used the well defined concept `does not mention Turing Machines'<br />
<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2020/07/a-table-for-matrix-mortality-what-i.htmlnoreply@blogger.com (GASARCH)6tag:blogger.com,1999:blog-3722233.post-7761235140481153504Mon, 29 Jun 2020 20:36:00 +00002020-06-29T16:36:34.607-04:00Can you name a famous living Chemist? Can anyone?<br />
I was re-watching the Greatest-of-all-time Jeopardy championship and the following happen (I paraphrase)<br />
<br />
----------------------<br />
Alex Trebek: The category is Chemistry and we have a special guest reading the clues.<br />
<br />
Darling: I wonder who that will be.<br />
<br />
Bill: Hmm. I assume some famous chemist.<br />
------------------------<br />
<br />
So who was it? Bryan Cranston, the actor who PLAYED chemist Walter White on <i>Breaking Bad.</i><br />
<br />
Why couldn't they get a famous living chemist to read the clues?<br />
<br />
My guess: there are no famous living chemists.<br />
<br />
The number of famous living scientists is fairly short and they are often known for things that are not quite their science. Some are famous because the popularize science (deGrasse Tyson, Dawkins) or because of something unusual about their life (Hawkings when he was alive) or for something else entirely that they did (Ted Kaczynski). Are any famous for the actual work that they do in the science?<br />
<br />
Andrew Wiles was famous for a brief time, and even made People Magazine's <i>25 most intriguing people of the year</i> list in the early 1990's (after he solved Fermat's Last Theorem). So he was famous but it was short lived.<br />
<br />
Terry Tao was on the Colbert Report (see <a href="http://www.cc.com/video-clips/6wtwlg/the-colbert-report-terence-tao">here</a>) after he won the Fields Medal, the MacAuthor Genius award, and the Breakthrough prize. And even that fame was short lived.<br />
<br />
I looked at the web page of Nobel Prize winners, <a href="https://www.nobelprize.org/prizes/lists/all-nobel-prizes">here</a>.<br />
<br />
The only Chemistry Nobel's I recognized were Marie Curie, Irene Joilet-Curie (Marie's Daughter), and Erst Rutherford.<br />
<br />
The only Physics Nobel's I recognized were<br />
<br />
Richard Feynman,<br />
<br />
Eugene Wigner (for writing about <a href="https://www.dartmouth.edu/~matc/MathDrama/reading/Wigner.html">The unreasonable effectiveness of mathematics in the natural sciences</a>),<br />
<br />
Richard Hofstadter (since he was the father of Douglas H and an uncle of Leonard H)<br />
<br />
Andrew Geim (since he won both an Ig-Noble prize and a Nobel prize, see <a href="https://blog.computationalcomplexity.org/2010/10/noble-and-ig-noble-prizes.html">here</a>)<br />
<br />
Wolfgang Pauli (I've heard the term `Pauli Principle" though I did not know what it was until I looked it up while preparing this blog. I prob still don't really know what it means.)<br />
<br />
Enrico Fermi<br />
<br />
Erwin Schrodinger<br />
<br />
Paul Dirac<br />
<br />
Robert Millikan<br />
<br />
Albert Einstein<br />
<br />
Max Karl Ernest Ludwig Planck (I thought his last name was `Institute')<br />
<br />
Johannes Diderik van der Waals<br />
<br />
Pierre Curie<br />
<br />
Marie Curie<br />
<br />
<br />
So, some questions:<br />
<br />
a) Am I wrong? Are there famous living chemists I never heard of? Are there any famous living scientists who are famous for their work in science?<br />
<br />
b) If I am right then was there ever a time when there were famous scientists?<br />
<br />
c) If there was such a time, what changed?<br />
<br />
(I ask all of this non-rhetorically and with no agenda to push.)<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2020/06/can-you-name-famous-living-chemist-can.htmlnoreply@blogger.com (GASARCH)15tag:blogger.com,1999:blog-3722233.post-5075242632528707140Mon, 22 Jun 2020 05:15:00 +00002020-06-22T01:15:12.979-04:00Winner of Ramsey Meme ContestMy REU program had a Ramsey Meme Contest.<br />
<br />
The winner was Saadiq Shaik with this entry:<br />
<br />
<a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/idont.jpg">I Don't Always...</a><br />
<br />
I challenge my readers to come up with other Ramsey Memes! or Complexity Memes! or point me to some that are already out there.<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2020/06/winner-of-ramsey-meme-contest.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-5834988441622500007Thu, 18 Jun 2020 13:57:00 +00002020-06-18T09:57:05.589-04:00On Chain Letters and Pandemics<div><i>Guest post by Varsha Dani.</i></div><div><br /></div><div>My 11-year-old child received a letter in the mail. "Send a book to the first person named," it said, "then move everyone's name up the list, add your own name and send copies of the letter to six friends. In a few weeks you will receive 36 books from all over the world!". Wow. When I first encountered chain letters in the mid eighties, it was postcards, but even then it hadn't taken me in. Since then I hadn't seen one of these in a long time, but I guess with a lot of people suddenly at home for extended periods, people crave both entertainment and a connection to others. </div><div><br /></div><div>What's wrong with chain letters? Well quite apart from the fact that they are illegal, even a child can comprehend that the number of books (or postcards or other gifts) received must equal the number sent, and that for every participant who does get a rich reward, there will be many who get nothing. </div><div><br /></div><div>But there is another kind of chain communication going around. It is an email, asking the recipient to send a poem or meditation to somebody, and later they will receive many communications of the same sort. How endearing. Poetry. Sweetness and Light. No get-rich-quick pyramid schemes here. What's wrong with that? </div><div><br /></div><div>Of course, it depends on what one means by "wrong". Maybe you like exchanging poetry with strangers. Maybe you don't find it onerous or wish that your spam filter would weed it out. But let's leave aside those issues and look at the math alone. You send the email to two friends, each of whom forwards it to two of their friends and so on. So the number of people the email reaches ostensibly doubles every step. Exponential growth. But in fact that is not what the graph of human connections looks like. Instead, what happens is that the sets of friends overlap, so that after a while the growth stops being exponential and tapers down. </div><div><br /></div><div>Where else have we seen something like that? Oh, right. The pandemic. The virus jumps from infected people to the people they meet, and from them to the people they meet and so on. Initially, that's exponential growth fof new cases, but after a while it tapers off, forms a peak and then starts to decrease. Why? Because eventually there is overlap in the sets of people that each infected person is "trying" (unintentionally) to infect, and a newly infected person who got the virus from one or many previously infected people is still just one newly infected person. </div><div><br /></div><div>So the chain letter spreads just like a virus. Indeed if one were to, somewhat fancifully, think of the chain letter as an independent entity whose goal is to self-replicate, then it looks even more like a virus, and, like a virus, it can only achieve its self-replication goal through the help of a host. But here's a way in which it is not like a virus. Once one has got the virus and recovered, one (hopefully) does not get it again. Not so the chain letter, of which one may get many copies over time! So maybe you will get some gifts or poetry, but you will likely also get more requests for them!</div><div><br /></div><div>So what's wrong with the poetry chain email? It depends on your perspective. To those of you who are wistfully waiting for that Poem from a Stranger, I dedicate the following to you.</div><div><br /></div><hr /><div><br /></div><div><i>An open letter to my 2<sup>n</sup> dearest friends:</i></div><div><br /></div><div>A letter came for me today</div><div>It promised wondrous ends</div><div>If only I would forward it </div><div>To just two other friends.</div><div><br /></div><div>If they in turn should send it on</div><div>to two more that they know,</div><div>the goodwill that we're sending out</div><div>would grow and grow and grow.</div><div><br /></div><div>Is this as pleasant as it seems?</div><div>Alas, dear friends, it's not.</div><div>This exponential growth can lead</div><div>To quite a sticky spot.</div><div><br /></div><div>Friends of friends of friends of mine</div><div>May very well be linked</div><div>The further that the letters go.</div><div>These folks are not distinct!</div><div><br /></div><div>Ensuring there's no overlap</div><div>Is a logistic* pain.</div><div>As you will see, when you receive</div><div>That letter yet again. </div><div><br /></div><div>So while you're stuck at home this year</div><div>And pacing in your room.</div><div>Pick up the phone and make a call</div><div>Or see your friends on Zoom.</div><div><br /></div><div>Your real thoughts would make me smile.</div><div>Chain letters are a con.</div><div>Do everyone a favor and</div><div>Don't send that letter on!</div><div><br /></div><div>--------------</div><div>* Pun intended. <a href="https://en.wikipedia.org/wiki/Logistic_function#In_medicine:_modeling_of_a_pandemic">https://en.wikipedia.org/wiki/Logistic_function#In_medicine:_modeling_of_a_pandemic</a></div><div><br /></div><div><br /></div>https://blog.computationalcomplexity.org/2020/06/on-chain-letters-and-pandemics.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-3523309889572389823Mon, 15 Jun 2020 15:17:00 +00002020-06-15T11:17:52.344-04:00Presentations of Diffie-Helman leave out how to find gWhen I first taught Diffie Helman I read the following<br />
1) Alice and Bob agree on p a prime and g a generator<br />
2) Alice picks a, sends g^a to Bob, Bob picks b, sends g^b to Alice<br />
3) Alice computes (g^b)^a and Bob computes (g^a)^b so they both have g^{ab}<br />
<br />
I knew how to find a prime- pick a number of length n (perhaps make sure the last digit is not even) and test for primality, if not then try again, you'll get one soon enough. I did not know how to find g. I had thought you<i> first </i>find p, and<i> then</i> given p you find g. I then figured out that you make actually pick p to be a <i>safe prime</i>, so q=(p-1)/2 is a prime, and then just pick random g and test them via computing g^2 and g^q: if neither is 1 then g is a generator. You will find a generator soon enough.<br />
<br />
That was all fine. But how come my source didn't <i>say </i>how to find g.?You need to know that to run the algorithm. That was years ago. Then I wondered how common it is for an explanation to not say how to find g. So I Googled ``Diffie-Helman'' I only record those that had some technical content to them, and were not about other DH such as Elliptic Curves.<br />
<br />
0) <a href="http://www.cs.jhu.edu/~rubin/courses/sp03/papers/diffie.hellman.pdf">The Original DH paper</a> Page 34:<i> alpha is a fixed primitive element of GF(alpha)</i>. No mention of how to find either the prime q or the prim root alpha.<br />
<br />
1) <a href="https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange">Wikiepdia</a>: ... <i>protocol uses the mult group of integers mod p, where p is a prime and g is a prim</i> <i>root mod p</i>. NO mention of how they find p or g.<br />
<br />
2) <a href="https://mathworld.wolfram.com/Diffie-HellmanProtocol.html">Wolfram's MathWorld</a>:<i> They agree on two prime numbers g and p, where p is large and g is a prim root mod p. In practice it is good to choose p such that (p-1)/2 is also prime. </i>They mention (p-1)/2 but not for the reason I give. (There are algorithms for Discrete Log that do well if (p-1)/2 has many factors.)<br />
<br />
3) <a href="https://www.comparitech.com/blog/information-security/diffie-hellman-key-exchange/">Comparatech</a>: <i>Alice and Bob start out by deciding two numbers p and g.</i> No mention of how to find p or g.<br />
<br />
4) <a href="https://searchsecurity.techtarget.com/definition/Diffie-Hellman-key-exchange">Searchsecurity</a> Won't bother quoting, but more of the same, no mention of how to find p or g.<br />
<br />
5) <a href="https://doubleoctopus.com/security-wiki/encryption-and-cryptography/diffie-hellman-algorithm/">The Secret Security Wiki</a> <i>Alice and Bob agree on p and g</i>.<br />
<br />
6) <a href="https://www.sciencedirect.com/topics/computer-science/diffie-hellman">Science Direct</a> More of the same.<br />
<br />
7) <a href="https://www.math.ucla.edu/~baker/40/handouts/rev_DH/node1.html">Notes from a UCLA Crypto Course</a> YEAH! They say how to find g.<br />
<br />
8) <a href="https://brilliant.org/wiki/diffie-hellman-protocol/">Brilliant (yes that really is the name of this site)</a> Brilliant? Not brilliant enough to realize you need to say how to find p and g.<br />
<br />
9) <a href="https://wiki.openssl.org/index.php/Diffie_Hellman">OpenSSL</a> Hard to tell. Their intuitive explanation leaves it out, but they have details below and code that might have it.<br />
<br />
<br />
I looked at a few more but it was the same story.<br />
<br />
This is NOT a RANT or even a complaint, but its a question:<br />
<br />
<b>Why do so few expositions of DH mention how to find p,g? You really need to do that if you really want to DO DH.</b><br />
<b><br /></b>
Speculation<br />
<br />
1) Some of the above are for the laymen and hence can not get into that. But some are not.<br />
<br />
2) Some of them are for advanced audiences who would know how to do it. Even so, how to find the generator really needs to be mentioned.<br />
<br />
3) Goldilocks: Some papers are for the layman who would not notice the gap, and some papers are for the expert who can fill in the gap themselves, so no paper in between. I do not believe that.<br />
<br />
4) The oddest of the above is that the original paper did not say how to find g.<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2020/06/presentations-of-diffie-helman-leave.htmlnoreply@blogger.com (GASARCH)10tag:blogger.com,1999:blog-3722233.post-9046421052819875987Mon, 08 Jun 2020 15:03:00 +00002020-06-08T11:03:43.456-04:00The Committee for the Adv. of TCS- workshop coming up SOON!<span id="docs-internal-guid-06a8f4c9-7fff-916b-0154-0d4b08969907"></span><br />
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span id="docs-internal-guid-06a8f4c9-7fff-916b-0154-0d4b08969907"><span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">(Posted by request from Jelani Nelson.)</span></span></div>
<span id="docs-internal-guid-06a8f4c9-7fff-916b-0154-0d4b08969907"><br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">The Committee for the Advancement of Theoretical Computer Science (CATCS)</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">is organizing a Visioning workshop. The primary objective of the workshop</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">is for TCS participants to brainstorm directions and talking points for TCS</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">program managers at funding agencies to advocate for theory funding.</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">There was some question of whether or not it would run this summer, but</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">YES, it is going to run.</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">If you are interested then reply (at the link below) by June 15.</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">This is SOON so click that link SOON.</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">The time commitment is 4-5 hours during the week of July 20-July 24 for</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">most participants, or roughly 10 hours for those who are willing to</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">volunteer to be group leaders.</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">The link to sign up is:</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;"><a href="https://thmatters.wordpress.com/2020/06/05/tcs-visioning-workshop-call-for-participation/">https://thmatters.wordpress.com/2020/06/05/tcs-visioning-workshop-call-for-participation/</a></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<br /></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<br /></div>
</span>https://blog.computationalcomplexity.org/2020/06/the-committee-for-adv-of-tcs-workshop.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-6696939180299352624Wed, 03 Jun 2020 04:55:00 +00002020-06-03T00:55:35.898-04:00How to handle grades during the PandemicIn March many Colleges sent students home and the rest of the semester was online. This was quite disruptive for the students. Schools, quite reasonably, wanted to make it less traumatic for students.<br />
<br />
So what to do about grades? There are two issues. I state the options I have heard.<br />
<br />
<br />
ISSUE ONE If P/F How to Got About it?<br />
<br />
1) Grade as usual.<br />
<br />
2) Make all classes P/F.<br />
<br />
PRO: Much less pressure on students.<br />
<br />
CON: Might be demoralizing for the good students.<br />
<br />
3) Make all classes P/F but allow students to opt for letter grades BUT they must decide before the last day of class. Hence teachers must post cutoffs before the final is graded<br />
<br />
CON: Complicated and puts (a) teachers in an awkward position of having to post cutoffs before the final, and (b) puts students in an awkward position of having to predict how well they would do.<br />
<br />
CON: A student can blow off a final knowing they will still get a D (passing) in the course.<br />
<br />
PRO: Good students can still get their A's<br />
<br />
CAVEAT: A transcript might look very strange. Say I was looking at a graduate school applicant and I see<br />
<br />
Operating Systems: A<br />
<br />
Theory of Computation: P<br />
<br />
I would likely assume that the Theory course the student got a C. And that might be unfair.<br />
<br />
3) Make all classes P/F but allow students to opt for letter grades AFTER seeing their letter grades. <br />
<br />
PRO: Less complicated an awkard<br />
<br />
PRO: A students blah blah<br />
<br />
CAVEAT above still applies.<br />
<br />
ISSUE TWO If P/F what about a D in the major<br />
<br />
At UMCP COMP SCI (and I expect other depts)<br />
<br />
a D is a passing grade for the University<br />
<br />
but<br />
<br />
a D is not a passing grade for the Major.<br />
<br />
So if a s CS Major gets a D in Discrete Math that does not count for the major--- they have to take it over again.<br />
<br />
But if classes are P/F what do do about that.<br />
<br />
Options<br />
<br />
1) Students have to take classes in their major for a letter grade.<br />
<br />
CON: The whole point of the P/F is to relieve pressure on the students in these hard times.<br />
<br />
PRO: None.<br />
<br />
2) Students taking a course in their major who get a D will still get a P on the transcript but will be told that they have to take the class over again.<br />
<br />
3) Do nothing, but tell the students<br />
<br />
IF you got a D in a course in your major and you are taking a sequel, STUDY HARD OVER THE SUMMER!<br />
<br />
4) Do nothing, but tell the teachers<br />
<br />
Students in the Fall may have a weak background. Just teach the bare minimum of what they need for the major.<br />
<br />
(Could do both 3 and 4)<br />
<br />
SO- what is your school doing and how is it working?https://blog.computationalcomplexity.org/2020/06/how-to-handle-grades-during-pandemic.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-1531592307894359428Mon, 25 May 2020 16:34:00 +00002020-05-27T21:28:29.744-04:00Oldest Living Baseball Players- can you estimate...(The Baseball season is delayed or cancelled, so I post about baseball instead.)<br />
<br />
This post is going to ask a question that you could look up on the web. But what fun with that be?<br />
<br />
The following statements are true<br />
<br />
1) Don Larsen, a professional baseball player who played from 1953 to 1967, is still alive. He is 90 years old (or perhaps 90 years young---I don't know the state of his health). He was born Aug 7, 1929. He is best know for pitching a perfect game in the World Series in 1956, pitching for the Yankees. He played for several other teams as well, via trades (this was before free agency).<br />
(CORRECTION- I wrote this post a while back, and Don Larsen has died since then.)<br />
<br />
<br />
2) Whitey Ford, a professional baseball player who played from 1950 to 1967, is still alive. He is 91 years old (or perhaps 91 years young---I don't know the state of his health). He was born Oct 21, 1928. He had many great seasons and is in the hall of fame. He played for the New York Yankees and no other team.<br />
<br />
3) From 1900 (or so) until 1962 there were 16 professional baseball teams which had 25 people each. From 1962 until 1969 there were 20 teams which had 25 people each. There were also many minor league teams.<br />
<br />
4) The youngest ballplayers are usually around 20. The oldest around 35. These are not exact numbers<br />
<br />
SO here is my question: Try to estimate<br />
<br />
1) How many LIVING retired major league baseball players are there now who are older than Don Larsen?<br />
<br />
2) How many LIVING retired major league baseball players are of an age between Don and Whitey?<br />
<br />
3) How many LIVING retired major league baseball players are older than Whitey Ford?<br />
<br />
Give your REASONING for your answer.<br />
<br />https://blog.computationalcomplexity.org/2020/05/oldest-living-baseball-players-can-you.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-8975690027864850581Tue, 19 May 2020 18:30:00 +00002020-05-19T14:30:13.394-04:00Obit for Richard Dudley <div>
Richard M. (Dick) Dudley died on Jan. 19, 2020 (NOT from Coronavirus).You can find obituaries for him <a href="http://news.mit.edu/2020/richard-dudley-mit-mathematics-professor-emeritus-dies-0218">here</a>, <a href="https://math.mit.edu/about/history/obituaries/dudley.php">here</a>, and <a href="http://www.ams.org/publicoutreach/in-memory/in-memory">here</a> and an interview with him from 2019 <a href="https://projecteuclid.org/euclid.ss/1555056041">here</a>.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
Professor Dudley worked in Probability and Statistics. His work is now</div>
<div>
being used in Machine Learning. Here is a guest-post-obit by</div>
<div>
David Marcus who had Prof. Dudley as his PhD Thesis Advisor.</div>
<div>
<br /></div>
<div>
-----------------------------------</div>
<div>
<br /></div>
<div>
Guest Blog Obit by David Marcus:</div>
<div>
<br /></div>
<div>
Dick was my thesis advisor at M.I.T. After I got my Ph.D. in 1983, I went</div>
<div>
to work in industry, so did not work closely with him, as some of his other</div>
<div>
students did. But, I enjoyed working with him very much in graduate school.</div>
<div>
<br /></div>
<div>
Dick was very precise. His lecture notes and articles (and later his books)</div>
<div>
said exactly what needed to be said and didn't waste words. In his classes,</div>
<div>
he always handed out complete lecture notes, thus letting you concentrate</div>
<div>
on the material rather than having to take a lot of notes.</div>
<div>
<br /></div>
<div>
Dick was very organized, but his office had piles of papers and journal</div>
<div>
articles everywhere. There is a picture <a href="http://news.mit.edu/2020/richard-dudley-mit-mathematics-professor-emeritus-dies-0218">here</a>.</div>
<div>
<br /></div>
<div>
Before Dick was my advisor, I took his probability course. My orals were</div>
<div>
going to be towards the end of the term, and I was going to use probability</div>
<div>
as one of my two minor areas. So, I spent a lot of time studying the</div>
<div>
material. Dick gave a final exam in the course. The final exam was unlike</div>
<div>
any other final exam I ever took: The exam listed twelve areas that had</div>
<div>
been covered in the course. The instructions said to pick ten and for each</div>
<div>
area give the main definitions and theorems and, if you had time, prove the</div>
<div>
theorems. Since I had been studying the material for my orals, I didn't</div>
<div>
have much trouble, but if I hadn't been studying it for my orals, it would</div>
<div>
have been quite a shock!(COMMENT FROM BILL: Sounds like a lazy way to make up an exam, though on this</div>
<div>
level of may it works. I know of a prof whose final was</div>
<div>
<br /></div>
<div>
Make up 4 good questions for the final. Now Solve them.</div>
<div>
<br /></div>
<div>
)</div>
<div>
<br /></div>
<div>
Once Dick became my advisor, Dick and I had a regular weekly meeting. I'd</div>
<div>
tell him what I'd figured out or what I'd found in a book or journal</div>
<div>
article over the last week and we'd discuss it and he'd make suggestions.</div>
<div>
At some point, I'd say I needed to think about it, and I'd leave. I never</div>
<div>
did find out how long these meetings were supposed to last because I was</div>
<div>
always the one to end them.(COMMENT FROM BILL: It's good someone ended them! Or else you might never</div>
<div>
had graduated :-) )</div>
<div>
<br /></div>
<div>
When I began working with Dick, he said he already had a full</div>
<div>
load of students, but he would see if he had something I could work on. The</div>
<div>
problem Dick came up with for me to work on was to construct a</div>
<div>
counterexample to a theorem that Dick had published. Dick knew his</div>
<div>
published proof was wrong, and had an idea of what a counterexample might</div>
<div>
look like, so suggested I might be able to prove it was a counterexample.</div>
<div>
In retrospect, this was perhaps a risky thesis problem for me since if the</div>
<div>
student gets stuck, the professor can spend time figuring out how to do it.</div>
<div>
But, in this case, presumably Dick had already put some effort into it</div>
<div>
without success. Regardless, with Dick's guidance, I was able to prove it,</div>
<div>
and soon after got my Ph.D.(COMMENT FROM BILL: Sounds risky since if Dick could not do it, maybe it's too hard.)</div>
<div>
<br /></div>
<div>
In 2003 there was a conference in honor of Dick's 65th birthday. All of his</div>
<div>
ex-students were invited, and many of them attended. There was a day of</div>
<div>
talks, and we all went out to dinner (Chinese food, if I recall correctly)</div>
<div>
in the evening. At dinner, I asked Dick if any of his other students had</div>
<div>
written a thesis that disproved one of his published theorems. He said I</div>
<div>
was the only one.(COMMENT FROM BILL: Really good that not only was he okay with you disproving</div>
<div>
his theorem, he encouraged you to!)</div>
<div>
<br /></div>
<div>
<br /></div>
https://blog.computationalcomplexity.org/2020/05/obit-for-richard-dudley.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-1082301538511422857Thu, 14 May 2020 13:40:00 +00002020-05-14T09:40:54.625-04:00Awesome Video from Women In Theory!Below is an <a href="https://www.youtube.com/watch?v=4Wl-3kadvgw">awesome video</a> made by WIT (Women In Theory) on May 10, 2020 to celebrate the women in our field and in place of the Women in Theory Workshop that was supposed to take place<br />
<div>
@Simons in June. ENJOY:</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br />
<iframe allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/4Wl-3kadvgw" width="560"></iframe>
</div>
https://blog.computationalcomplexity.org/2020/05/awesome-video-from-women-in-theory.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-1023884907351872604Mon, 11 May 2020 14:41:00 +00002020-05-11T10:41:53.333-04:00And the winners are ....The Computational Complexity Conference has announced the <a href="https://computationalcomplexity.org/Archive/2020/accept.php">accepted papers</a> for the 2020 now virtual conference. Check them out!<div>
<br /></div>
<div>
Speaking of the complexity conference, my former PhD student Dieter van Melkebeek will <a href="https://sigact.org/prizes/service/2020.html">receive the ACM SIGACT Distinguished Service award</a> for his leadership in taking the conference independent. They grow up so fast! </div>
<div>
<br /></div>
<div>
Robin Moser and Gábor Tardos <a href="https://sigact.org/prizes/g%C3%B6del/citation2020.html">will receive the Gödel Prize</a> for their work giving a constructive proof of the Lovász Local Lemma, one of my truly <a href="https://blog.computationalcomplexity.org/2014/07/favorite-theorems-compressing-local.html">favorite theorems</a> as it gave a far stronger bound, a shockingly simple and efficient algorithm and an incredibly beautiful proof. Back in 2009 Moser gave my all-time favorite STOC talk on an early version of the paper. I (and <a href="https://rjlipton.wordpress.com/2009/06/02/mosers-method-of-bounding-a-program-loop/">others</a>) sat amazed as his algorithm and proof came alive. During the talk I asked Eric Allender sitting next to me "Are we really seeing a Kolmogorov complexity proof of the Lovász Local Lemma?" Yes, <a href="https://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html">we did</a>.</div>
<div>
<br /></div>
<div>
Cynthia Dwork will receive the <a href="https://sigact.org/prizes/knuth/citation2020.pdf">Knuth prize</a> given for her life's work. The prize would be justified by her work on distributed computing alone but it is her leadership in formalizing Differential Privacy, one of the coolest concepts to come out of the theoretical computer science community this century, that will leave her mark in theory history. </div>
https://blog.computationalcomplexity.org/2020/05/and-winners-are.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-7656443173792446291Thu, 07 May 2020 14:28:00 +00002020-05-07T10:28:50.018-04:00Vidcast on ConferencesBill and Lance have another socially-distanced <a href="https://youtu.be/VwvuTnE66xQ">vidcast</a>, this time with Lance telling the story of two conferences (<a href="http://ec20.sigecom.org/">ACM Economics and Computation</a> and the Game Theory Congress). As mentioned in the video the Game Theory Congress has been <a href="http://gametheorysociety.org/6th-world-congress-of-the-game-theory-society-in-budapest-july-13-17-2020/">postponed to next year</a>. Also mentioned in the video, for a limited time you can read Lance's <a href="https://goldenticket.fortnow.com/">book</a> on P v NP on <a href="https://muse.jhu.edu/book/36432">Project Muse</a>.<div><br /></div><div><br /></div>
<iframe width="560" height="315" src="https://www.youtube.com/embed/VwvuTnE66xQ" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>https://blog.computationalcomplexity.org/2020/05/vidcast-on-conferences.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-5609460581142399437Tue, 05 May 2020 04:39:00 +00002020-05-05T00:39:15.608-04:00Why is there no (d,n) grid for Hilbert's Tenth Problem?<br />
Hilbert's 10th problem, in modern language is:<br />
<br />
Find an algorithm that will, given a poly over Z in many variables, determine if it has a solution in Z.<br />
<br />
This problem was proven undecidable through the work of Davis, Putnam, Robinson and then<br />
Matiyasevich supplied the last crucial part of the proof.<br />
<br />
Let H10(d,n) be the problem with degree d and n variables.<br />
<br />
I had assumed that somewhere on the web would be a grid where the dth row, nth col has<br />
<br />
U if H10(d,n) is undecidable<br />
<br />
D if H10(d,n) is decidable<br />
<br />
? if the status of H10(d,n) was unknown.<br />
<br />
I found no grid. I then collected up all the results I could find <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/h10.pdf">here</a><br />
<br />
This lead to the (non-math) question: Why is there no grid out there? Here are my speculations.<br />
<br />
1) Logicians worked on proving particular (d,n) are undecidable. They sought solutions in N. By contrast number theorists worked on proving particular (d,n) decidable. They sought solutions in Z.. Hence a grid would need to reconcile these two related problems.<br />
<br />
<div>
<div>
2) Logicians and number theorists didn't talk to each other. Websites and books on Hilbert's Tenth problem do not mention any solvable cases of it.</div>
</div>
<div>
<br /></div>
<div>
<div>
3) There is a real dearth of positive results, so a grid would not be that interesting. Note that we do not even know if the following is decidable: given k in Z does there exists x,y,z in Z such that</div>
<div>
<br /></div>
<div>
x^3 +y^3+ z^3 = k. I blogged about that <a href="https://blog.computationalcomplexity.org/2019/04/x-3-y-3-z-3-33-has-solution-in-z-and.html">here</a></div>
</div>
<div>
<br /></div>
<div>
4) For an undecidable result for (d,n) if you make n small then all of the results make d very large.</div>
<div>
<br /></div>
<div>
For example</div>
<div>
<br /></div>
<div>
n=9, d= 1.6 x 10^{45} is undecidable. The status of n=9, d=1.6 x 10^{45} -1 is unknown.</div>
<div>
<br /></div>
<div>
Hence the grid would be hard to draw.</div>
<div>
<br /></div>
<div>
Frankly I don't really want a grid. I really want a sense of what open problems might be solved. I think progress has gone in other directions- H10 over other domains. Oh well, I want to know about</div>
<div>
<br /></div>
<div>
n=9 and d=1.6 x 10^{45}-1. (parenthesis ambiguous but either way would be an advance.)</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
https://blog.computationalcomplexity.org/2020/05/why-is-there-no-dn-grid-for-hilberts.htmlnoreply@blogger.com (GASARCH)5tag:blogger.com,1999:blog-3722233.post-5535989522381894451Fri, 01 May 2020 14:40:00 +00002020-05-01T10:40:21.003-04:00Predicting the VirusAs a complexity theorist I often find myself far more intrigued in what we cannot compute than what we can. <div><br /></div><div>In 2009 I <a href="https://blog.computationalcomplexity.org/2009/06/failure-of-social-networks.html">posted on some predictions of the spread of the H1N1 virus</a> which turned out to be off by two orders of magnitude. I wrote "I always worry that bad predictions from scientists make it harder to have the public trust us when we really need them to." Now we need them to.</div><div><br /></div><div>We find ourselves bombarded with predictions from a variety of experts and even larger variety of mathematicians, computer scientists, physicists, engineers, economists and others who try to make their own predictions with no earlier experience in epidemiology. Many of these models give different predictions and even the best have proven significantly different than reality. We keep coming back to the George Box quote "All models are wrong, but some are useful."</div><div><br /></div><div>So why do these models have so much trouble? The standard complaint of inaccurate and inconsistently collected data certainly holds. And if a prediction changes our behavior, we cannot fault the predictor for not continuing to be accurate.</div><div><br /></div><div>There's another issue. You often here of a single event having a dramatic effect in a region--a soccer game in Italy, a funeral in Georgia, a Bar Mitzvah in New York. These events ricocheted, people infected attended other events that infected others. This becomes a complex process that simple network models can never get right. Plenty of soccer games, funerals and Bar Mitzvahs didn't spread the virus. If a region has hadn't a large number of cases and deaths is it because they did the right thing or just got lucky. Probably something in between but that makes it hard to generalize and learn from experience. We do know that less events means less infection but beyond that is less clear.</div><div><br /></div><div>As countries and states decide how to open up and universities decide how to handle the fall semester, we need to rely on some sort of predictive models and the public's trust in them to move forward. We can't count on the accuracy of any model but which models are useful? We don't have much time to figure it out.</div>https://blog.computationalcomplexity.org/2020/05/predicting-virus.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-7481748881751465174Wed, 29 Apr 2020 13:44:00 +00002020-04-29T09:44:14.877-04:00A Guest Blog on the Pandemic's affect on disability students<div>I asked my Grad Ramsey Theory class to email me about whatever thoughts they have on the pandemic that they want to share with the world, with the intend of making some of them into a blog post. I thought there would be several short thoughts for one post. And I may still do that post. But I got a FANTASTIC long answer from one Emily Mae Kaplitz. Normally I would ask to shorten or edit a guest post, but I didn't do that here since that might make it less authentic.</div><div><br /></div><div>Here is Emily Kaplitz's email (with her enthusiastic permission)</div><div><br /></div><div>--------------------------------------------------------------------------------------</div><div><br /></div><div>Ok so this might be super ranty, (It definitely is.) but I think it is super important to bring up in a blog post written by an academic that will be probably read by other academics. </div><div><br /></div><div>The students that are being most affected by this pandemic with online learning are disability students. As a disability student, we carefully cultivate the way that we learn best based off of years of trial and error. This is harder than anything else, we have to face in our lifetime. Most of the time disability students are left on the back burner and that statement is so much more prevalent right now. My friends brother is autistic. He is struggling so much right now because he is at home. Disability students learn what environment works best for them and at home is usually not the best place. We have to split our lives into different boxes that each have different tools to help us get our brains to focus and work well when we need them too. Disability students will rely on everything being planned out, so that they can succeed. Teachers and professors cannot understand the stress and strain that having to work at home puts on the student. Every time I go to another school, it is a struggle to figure out what new thing I need to add into the mix and what old thing I need to throw away. It's exhausting, but when I go from one school to another I at least know that the basics are the same. I sit in a classroom, the professors lecturer, and then I do work at home that is assigned to me. Changing to online changes that dynamic so much. A professor cannot see when a student is visibly struggling with a topic because we'll all behind computers. A neurotypical person might ask, "well why don't you just ask a question? Why don't you just let the professor know that you don't understand". Let me answer that simply. If all your life you've been silenced because of something that you cannot control, is your first reaction to speak out or to stay silent. It is so hard for disability students to ask a question after we've been labeled the dumb kid. Every time we ask a question, we always have the thought of: is this going to make me sound stupid. We've worked so hard to eliminate that word from our vocabulary and from others who will throw that word back at us. Disability students are being left in the hands of their parents and teachers/professors who do not understand us and our needs even if they try to or want to. It is so hard for us to explain what our normal is because we don't live your normal and therefore don't know the difference. Many disability students have their confidence slashed the moment they enter a classroom and realize that they are not like the other kids. Even more so because they don't understand why they aren't. Disability students are one of the most hard-working individuals when we have a cheerleader to cheer us on because it's hard. It's harder than anything anyone has to do. Because no one listens to you when you are stupid and no one cares for you if you're not easy to care for unless they are given a specific reason to. Fighting a losing battle every day is awful. Now imagine all of your weapons that you have carefully crafted over the years have been taken away and you are left defenseless. While we have things like ADS that are supposed to help support us, it's not enough. Just like putting a Band-Aid on an open infected wound will not be enough. Now more than ever we need to learn from this as academics. We need to learn that helping disability students does not only help disability students. It helps all students because all students learn differently. All students if given the chance can excel at any field that we put them in. We just have to figure out the best way to get that student to shine. That is one of the reasons why I am a PhD student right now. I saw in the tutoring center at my undergrad how many students came to me with so much frustration about something they are doing in class. Both students with disabilities and without. These students are constantly apologizing because they don't understand something. In one session by just changing the way that we talk about a subject the student was able to get it in less time than the professor taught it. I've had students come to me after an exam and tell me that the only reason they got the grade that they did was because in their head was my voice coaching them on a subject. We are not teaching optimally. We are teaching the way that it has been done for years and years and years and that is not the best way to teach. It might be the best way to teach the strongest links but really the link that matters the most is the weakest link that will snap under pressure because you can't pull a tractor with a broken link. Disability students think differently. Imagine how many impossible problems we can solve when we have people that think differently. But that's just my two cents as a disability student who is struggling and sees other disability students struggling every day. And really just wants to help all students succeed.</div><div><br /></div><div>I blame any misspellings, grammar errors, and run on sentences on my speech to text and text to speech. This was a long email and if we were on tumblr, I would post a potato at the end. Since we aren't, I will leave this email with this. Thank you for taking the time to read this rant. Even if you don't include this in your blog post, I believe one person reading this has made the difference.</div><div><br /></div><div>Thanks!</div><div><br /></div><div>Emily Mae Kaplitz</div>https://blog.computationalcomplexity.org/2020/04/a-guest-blog-on-pandemics-affect-on.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-8100403263538580223Wed, 22 Apr 2020 18:28:00 +00002020-04-22T14:28:12.195-04:00Complexity Vidcast - Future EditionBill and Lance aim to <a href="https://www.youtube.com/watch?v=4G2cxVRe0X8">talk about the future</a> but can't escape the present.<br />
<br />
<br />
<iframe allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/4G2cxVRe0X8" width="560"></iframe>https://blog.computationalcomplexity.org/2020/04/complexity-vidcast-future-edition.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-515246364372918249Mon, 20 Apr 2020 13:57:00 +00002020-04-22T06:11:15.480-04:00The Summer Virtual Conference SeasonBoth <a href="http://acm-stoc.org/stoc2020/">STOC</a> and <a href="https://computationalcomplexity.org/">Complexity</a> have announced they will go virtual for the summer. <a href="https://icalp2020.saarland-informatics-campus.de/">ICALP</a> moved from Beijing to Saarbrücken to online. I expect every major summer conference and workshop will be cancelled, postponed or virtualized.<br />
<div>
<br /></div>
<div>
Most CS conferences serve as publication venues and can't be cancelled or postponed. So how do we virtualize a conference? The ACM has an evolving <a href="https://people.clarkson.edu/~jmatthew/acm/VirtualConferences_GuideToBestPractices_CURRENT.pdf">virtual conferences best practices guide</a>. Putting the talks and poster sessions online is not trivial, but relatively straightforward. Personally I go to conferences mostly not for the talks but for the interactions with other participants--the receptions, meal time and just hanging in the hallways. The ACM document describes some approaches like Dagstuhl-style randomized virtual dinner tables. The IEEE VR conference <a href="https://www.cccblog.org/2020/04/02/computing-researchers-respond-to-covid-19-running-a-virtual-conference/">tried virtual reality</a> through <a href="https://hubs.mozilla.com/#/">Mozilla hubs</a>. None of these can truly replicate the on-site experience.</div>
<div>
<br /></div>
<div>
Let me mention two other meetings the <a href="https://games2020.hu/">Game Theory Congress</a> held every four years due to be held in Budapest and the <a href="https://cra.org/conference-at-snowbird/">CRA Snowbird Conference</a>, a meeting of CS department chairs and computing leadership, held every other summer in Utah. Both meetings are not archival publications venues though have several talks and panels. But the main purpose of both is mostly to bring people together, game theorists and CS leaders. I hope they postpone rather than virtualize these meetings. Rather get together a year late than pretend to get together now.</div>
https://blog.computationalcomplexity.org/2020/04/the-summer-virtual-conference-season.htmlnoreply@blogger.com (Lance Fortnow)8tag:blogger.com,1999:blog-3722233.post-104815394733465706Wed, 15 Apr 2020 13:42:00 +00002020-04-15T09:42:39.264-04:00Theoretical Computer Science for the Future<i>Guest post by the TCS4F initiative
(Antoine Amarilli, Thomas Colcombet, Hugo Férée, Thomas Schwentick) </i><div><br /></div><div><a href="https://tcs4f.org/">TCS4F</a> is an initiative by theoretical computer scientists who are
concerned about that other major crisis of our time: climate change. We
anticipate that the climate crisis will be a major challenge of the
decades to come, that it will require major changes at all levels of
society to mitigate the harm that it will cause, and that researchers in
theoretical computer science, like all other actors, must be part of the
solution and not part of the problem.</div>
<div><br /></div><div>Our initiative is to propose a <a href="https://tcs4f.org/">manifesto</a> to commit
to a reduction of greenhouse gas emissions: following <a href="https://www.ipcc.ch/2018/10/08/summary-for-policymakers-of-ipcc-special-report-on-global-warming-of-1-5c-approved-by-governments/">IPCC goals</a>, the
objective is to reduce by at least 50% before 2030 relative to pre-2020
levels. The manifesto is more than a simple expression of concern,
because it is a pledge with concrete objectives. However, it does not
prescribe specific measures, as we believe this discussion is not
settled yet and the right steps to take can vary depending on everyone's
practices. </div><div><br />
The manifesto can be signed by individual researchers (like you, dear
reader!), by research groups, and by organizers of conferences and
workshops. Currently, over 50 researchers have signed it. The goal of
TCS4F is also to start organizing a community of concerned researchers,
across theoretical computer science, to think about the issue of climate
change and how to adjust what we do, in particular our travel habits. </div><div><br />
We need your help to make this initiative a success and help theoretical
CS lead the way towards a sustainable, carbon-neutral future:</div><div><ul style="text-align: left;"><li>If you agree with our concerns and are ready to commit to reducing
your carbon footprint, consider <a href="https://tcs4f.org/">signing the manifesto</a>. Signing is open to all researchers in
theoretical CS in the broadest possible sense.</li><li>Advertise your support of the manifesto (e.g., by putting one of our
badges on your webpage). Talk in your research teams and departments
about the manifesto, and see if you can gather support for signing the
manifesto collectively as a research group.</li><li>If you are involved in conferences and workshops, start a discussion
about the carbon footprint of the event, and whether the event could
commit to the manifesto's goal. Indeed, now that conferences across
the globe are moving online because of the COVID-19 pandemic, it is a
good time to discuss how conferences could evolve towards more
sustainable models.</li><li>Spread the word about the issue of climate change and the TCS4F
initiative, and encourage discussion of this important challenge in
our communities. </li></ul></div><div>
As theoretical researchers, we are not used to discussing uncomfortable
non-scientific questions like the effects of our activities on the
world. However, we believe that the magnitude of the climate crisis
obliges us to act now as a community. We are confident that great
changes can be achieved if we do not limit our creativity to our
specific research areas and also use it to re-think our way to do
research.
<br /></div>https://blog.computationalcomplexity.org/2020/04/theoretical-computer-science-for-future.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-612436836431644422Mon, 13 Apr 2020 02:21:00 +00002020-04-13T13:53:25.387-04:00John Conway Dies of CoronvirusJohn Conway passed away on April 11, 2020 of the Coronovirus. He is the first person I knew (for some definition of `know') who has died of it. I suspect this is true of many readers of this blog.<br />
(Fellow bloggers Scott Aaronson and Terry Tao have already posted about John Conway,<br />
<a href="https://www.scottaaronson.com/blog/">here</a> and <a href="https://terrytao.wordpress.com/2020/04/12/john-conway/">here</a>. I suspect there will be others and when they do I will add it here.<br />
ADDED LATER: nice xkcd <a href="https://xkcd.com/2293/">here</a><br />
<br />
John Conway is a great example of how the line between recreational math and serious math is .... non-existent? not important? Take our pick.<br />
<br />
Examples<br />
<br />
1) Conway invented Surreal Numbers. These can be used to express infinitely big and infinitely small numbers. One can even make sense of things like square root of infinity. Conway's book is called On Numbers and Games (see <a href="https://en.wikipedia.org/wiki/On_Numbers_and_Games">here</a> and <a href="https://www.amazon.com/Numbers-Games-John-H-Conway/dp/1568811276">here</a>) Two free sources: <a href="https://thatsmaths.com/2012/11/22/the-root-of-infinity-its-surreal/">here</a> and <a href="https://www.whitman.edu/Documents/Academics/Mathematics/Grimm.pdf">here</a>.<br />
<br />
<div>
Note that Conway defined surreals in terms of games. Are they fun games? Probably not, but they are games!</div>
<div>
<br /></div>
<div>
2) Conway's Game of Life (you really do need to use his name, note the contrast between <i>The game</i> <i>of life <a href="https://en.wikipedia.org/wiki/The_Game_of_Life">here</a> </i>and <i>Conway's Game of Life <a href="https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life">here</a></i></div>
<div>
<i><br /></i></div>
<div>
<div>
The game is simple (and this one IS fun). You begin with some set of dots placed at lattice points, and a set of rules to tell how they live, die, or reproduce. The rules are always the same. Different initial patterns form all kinds of patterns. Sounds fun! Is it easy to tell, given pattern P1 and P2 whether, starting with P1 you can get to P2. No. Its undecidable.</div>
<div>
<br /></div>
<div>
So this simple fun game leads to very complicated patterns.</div>
<div>
<br /></div>
<div>
And nice to have an undecidable problem that does not mention Turing Machines. (I will tell the students it is undecidable this semester, though I won't be proving it.)</div>
<div>
<br /></div>
<div>
3) Berlekamp, Conway, and Guy wrote <i>Winning Ways for your Mathematical Plays </i>See <a href="https://en.wikipedia.org/wiki/Winning_Ways_for_your_Mathematical_Plays">here</a> and <a href="http://www.amazon.com/Winning-Ways-Your-Mathematical-Plays/dp/1568811446">here</a></div>
</div>
<div>
<br /></div>
<div>
This is the ultimate book on NIM games.</div>
<div>
<br /></div>
<div>
4) The above is probably what the readers of this blog are familiar with; however, according to his Wikipedia page (see <a href="https://en.wikipedia.org/wiki/John_Horton_Conway">here</a>) he worked in Combinatorial Game Theory, Geometry, Geometric Topology, Group Theory, Number Theory, Algebra, Analysis, Algorithmics and Theoretical Physics.</div>
<div>
<br /></div>
<div>
He will be missed.</div>
https://blog.computationalcomplexity.org/2020/04/john-conway-dies-of-coronvirus.htmlnoreply@blogger.com (GASARCH)1