tag:blogger.com,1999:blog-3722233Mon, 01 Mar 2021 19:59:11 +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)Blogger2818125tag:blogger.com,1999:blog-3722233.post-5663884325046890461Sun, 28 Feb 2021 17:42:00 +00002021-02-28T11:42:00.815-06:00Using number-of-PhD's as a measure of smartness is stupid. <p>In <i>Thor:Ragnorak</i> Bruce Banner mentions that he has 7 PhDs. Gee, I wonder how he managed to slip that into a conversation casually. Later in the movie:</p><p><br /></p><p>Bruce: I don't know how to fly one of those (it an Alien Spacecraft)</p><p>Thor: You're a scientist. Use one of your PhD's </p><p>Bruce: None of them are for flying alien spaceships.</p><p><br /></p><p>On the episode <i>Double Date </i>of Archer (Season 11, Episode 6) Gabrielle notes that she has 2 PhD's whereas Lana only has 1 PhD. </p><p><br /></p><p>I am sure there are other examples of a work of fiction using <i>number of PhDs </i>as a way to say that someone is smart. In reality the number of PhD's one has is... not really a thing. </p><p>In reality if a scientist wants to do work in another field they... do work in that field.</p><p>Godel did research in Physics in the 1950's, but it would have been silly to go back and get a PhD in it.</p><p>Fortnow did research in Economics, but it would have been silly to go back and get a PhD in it. </p><p>Amy Farrah Fowler worked in neurobiology and then in Physics. Her Nobel prize in physics (with Sheldon Cooper) is impressive, getting a PhD in Physics would be ... odd. Imagine someone looking at here resume: <i>She has a Nobel Prize in Physics, but does she have a PhD? Did she pass her qualifying</i> <i>exams?</i> This is the flip side of what I mentioned in a prior post about PhD's: <i>Not only does Dr. Doom want to take over the world, but his PhD is from The University of Latveria, which is not accredited. </i></p><p>There are other examples.</p><p>There ARE some people who get two PhDs for reasons of job market or other such things. That's absolutely fine of course. However, I wonder if in the real world they brag about it. I doubt it. </p><p>Is there anyone who has 3 PhDs? I would assume yes, but again, I wonder if they brag about it. Or should. </p><p>WHY do TV and movies use number-of-PhDs as a sign of genius? I do not know- especially since there are BETTER ways say someone is a genius in a way the audience can understand: number-of-Nobel-prizes, number-of-times-mentioned-in-complexityblog, number of Dundie's (see <a href="https://theoffice.fandom.com/wiki/Dundie">here</a>), etc. </p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2021/02/using-number-of-phds-as-measure-of.htmlnoreply@blogger.com (gasarch)7tag:blogger.com,1999:blog-3722233.post-2202248828009562800Thu, 25 Feb 2021 14:19:00 +00002021-02-25T08:19:22.435-06:00Complexity is the Enemy of Speed<p>The title of this post came from an <a href="https://www.wsj.com/articles/connecticuts-covid-vaccine-lesson-11614124012">opinion piece</a> in the Wall Street Journal yesterday on vaccine distribution. Many attempts to get the vaccines to the right groups first have slowed down distribution and sometime even caused <a href="https://www.nbcnews.com/news/us-news/thousands-covid-19-vaccines-wind-garbage-because-fed-state-guidelines-n1254364">vaccines to go to waste</a>. Rules to help spread vaccines across minority groups often backfire. Often when some rules lead to inequity, we try to fix it with more rules when we need less much less. Attempts to distribute vaccines to multiple medical and pharmacy sites have made it difficult to get appointments even if you are eligible.</p><p>Randomness is the simplest way to fairness. The movie Contagion got it right, just choose birthdays by picking balls from a bin to distribute the vaccine. Then people can just show up at a few chosen sites with proof of birthday. No need to sign up.</p><p>You could argue to add back conditions like age, medical conditions, jobs but that just leads you down the same problematic path. The fastest way to get past this pandemic is to get vaccines into arms. Trust the randomness.</p>https://blog.computationalcomplexity.org/2021/02/complexity-is-enemy-of-speed.htmlnoreply@blogger.com (Lance Fortnow)6tag:blogger.com,1999:blog-3722233.post-6398537358110172858Tue, 23 Feb 2021 05:36:00 +00002021-02-22T23:36:15.128-06:00Good Names and Bad Names of Game Shows and theorems<p> In my post on Alex Trebek, see <a href="https://blog.computationalcomplexity.org/2020/11/alex-trebekwhat-is-todays-post-about.html">here</a>, I noted that <i>Jeopardy!</i> is not a good name for the game show since it doesn't tell you much about the show. Perhaps <i>Answers and Questions </i>is a better name.</p><p>The following game shows have names that tell you something about the game and hence have better names: </p><p>Wheel of Fortune, The Price is Right, Lets make a Deal, Beautiful women have suitcases full of money (the original name for Deal-No Deal), Win Ben Stein's Money, Beat the Geeks. </p><p>In Math we often name a concept after a person. While this may be a good way to honor someone, the name does not tell us much about the concept and it leads to statements like:</p><p><br /></p><p><i>A Calabi-Yau manifold is a compact complex Kahler manifold with a trivial first Chern class. </i></p><p><i>A Kahler manifold is a Hermitian manifold for which the Hermitian form is closed.</i></p><p><i>A Hermitian manifold is the complex analog of the Riemann manifold. </i></p><p>(These examples are from an article I will point to later---I do not understand <i>any </i>of these terms, though I once knew what a <i>Riemann manifold</i> was. I heard the term <i>Kahler Manifold </i>in the song <a href="https://www.youtube.com/watch?v=2rjbtsX7twc">Bohemian Gravity</a>. It's at about the 4 minute 30 second place.) </p><p>While I am amused by the name <i>Victoria Delfino Problems</i> (probably the only realtor who has problems in math named after her, see my post <a href="https://blog.computationalcomplexity.org/2021/02/the-victoria-delfino-problems-example.html">here</a>) it's not a descriptive way to name open problems in descriptive set theory. </p><p><br /></p><p>Sometimes a name becomes SO connected to a concept that it IS descriptive, e.g.:</p><p><i>The first proof of VDW's theorem yields ACKERMAN-LIKE bounds. </i></p><p>but you cannot count on that happening AND it is only descriptive to people already somewhat in the field. </p><p><br /></p><p>What to do? <a href="http://nautil.us/issue/89/the-dark-side/why-mathematicians-should-stop-naming-things-after-each-other">This</a> article makes the ballian point that we should STOP DOING THIS and that the person who first proves the theorem should name it in a way that tells you something about the concept. I would agree. But this can still be hard to really do.</p><p><br /></p><p>In my book on Muffin Mathematics (see <a href="https://www.amazon.com/Mathematical-Muffin-Morsels-Problem-Mathematics/dp/9811215170">here</a>) I have a sequence of methods called</p><p>Floor Ceiling, Half, Mid, Interval, Easy-Buddy-Match, Hard-Buddy-Match, Gap, Train. </p><p>There was one more method that I didn't quite name, but I used the phrase `Scott Muffin Problem' to honors Scott Huddleton who came up with the method, in my description of it. </p><p>All but the last concept were given ballian names. Even so, you would need to read the book to see why the names make sense. Still, that would be easier than trying to figure out what a Calabi-Yau manifold is. </p><p><br /></p><p></p><br />https://blog.computationalcomplexity.org/2021/02/good-names-and-bad-names-of-game-shows.htmlnoreply@blogger.com (gasarch)8tag:blogger.com,1999:blog-3722233.post-699230831808345084Sun, 14 Feb 2021 20:23:00 +00002021-02-14T14:23:02.530-06:00Two examples of Journalists being... Wrong. One BIG one small<p> Journalists sometimes get things wrong.</p><p>This is not news, but it is interesting when you KNOW they are wrong. </p><p>1) Scott Aaronson has a GREAT example regarding an IMPORTANT story. I recommend you to read his blog post <a href="https://www.scottaaronson.com/blog/?p=5310">here</a>. Most of the comments are good also, though they go off on some tangents (e.g., is the Universal Basic Income a progressive idea?)</p><p><br /></p><p>2) I have my own example. It is far less important than the one Scott discusses; however, inspired by Scott, I will discuss it. My example also involves Scott, but that's a coincidence. </p><p>Quanta Magazine emailed me that they wanted to talk to me about an upcoming article on <i>The Busy</i> <i>Beaver Problem</i>. Why me? Because Scott's (same Scott as above!) survey/open problems column appeared in the SIGACT News Open Problem Column that I edit. </p><p>This sounded fine (Spoiler Alert: It was fine, the errors they made were odd, not harmful).</p><p>Here is the Quanta Article (though I do not know if it is behind paywalls- I can never tell if I am getting access because I have a UMCP account of or anyone can have access or if I am breaking copyright laws by posting the link): <a href="https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/">here</a></p><p>Here is Scotts article: <a href="https://www.scottaaronson.com/papers/bb.pdf">here</a></p><p>The interviewer asked me </p><p>a) Why did I ask Scott to write the article?</p><p>ANSWER: He had a blog post on it, and I was skeptical of why these numbers are interesting, so I asked a question in the comments. He gave a great answer, so I asked him if he wanted to write a column for my open problems column. Actually I asked him if either he or perhaps a grad student would do it- I assumed he would be too busy since his `day job' is quantum computing. However, much to my surprise and delight he said YES he would do it.</p><p>b) Is the Busy Beaver Function important?</p><p>ANSWER: In my opinion the actual numbers are not that important but its really neat that (a) we know some of them, and (b) they are far smaller than I would have thought. Also these numbers are interesting for the following reason: there is some n so that proving </p><p>BB(n)=whatever it equals</p><p> is Ind of Peano Arithmetic. When I hear that I think the number must be really large. Its not. Its 27. NEAT! And stronger theories are related to bigger numbers. This is a way to order theories. For ZF they have something in the 700's- MUCH SMALLER than I would have thought. Scott and others can even relate BB to open problems in Math! </p><p>There were some other questions also, but I don't recall what they were. </p><p>SO when the article came they mentioned me once, and its... not quite wrong but odd:</p><p><i>William Gasarch, a computer science professor at the University of Maryland College Park,</i></p><p><i>said he's less intrigued by the prospect of pinning down the Busy Beaver numbers than by </i></p><p><i>``the general concept that its actually uncomputable.'' He and other mathematicians are mainly interested in using the yardstick for gauging the difficulty of important open problems in mathematics--or for figuring out what is mathematically knowable at all. </i></p><p><br /></p><p>The oddest thing about the paragraph is they do not mention my connection to Scott and the article he wrote! I reread the article looking for something like `<i>Scotts article appeared in the SIGACT News</i> <i>Open Problems column edited by William Gasarch' </i>Nothing of that sort appears. </p><p>Without that its not clear why they are soliciting my opinion. My colleague Clyde says this is GOOD: people will ASSUME I am some sort of expert. Am I an expert? I proofread Scott's paper so... there is that...</p><p>Also I come off as more down on BB than I really am. </p><p>Did I claim that Mathematicians are more interested in using it as a yardstick. Actually I may have said something like that. I don't know if its true. That's my bad- I should have said that I am interested in that.</p><p>After the article came out I asked the interviewer why my role was not in the article. He said it was cut by the editor. </p><p>NOW- NONE of this is important, but even on small and easily correctable things, they get it wrong. So imagine what happens on hard issues that are harder to get right. </p><p><br /></p><p>MISC: One comment on Scott's blog was about the Gell-Mann amnesia effect, see this article on it:</p><p><a href="https://www.tefter.io/bookmarks/45454/readable">here</a><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2021/02/two-examples-of-journalists-being-wrong.htmlnoreply@blogger.com (gasarch)5tag:blogger.com,1999:blog-3722233.post-8474138395715737050Mon, 08 Feb 2021 04:55:00 +00002021-02-09T00:25:21.286-06:00The Victoria Delfino Problems: an example of math problems named after a non-mathematician<p> If you Google <b>Victoria Delfino </b>you will find that she is a real estate agent in LA (well, one of the Victoria Delfino's you find is such). After this blog is posted you may well get this post on the first Google page. </p><p>If you Google <b>Victoria Delfino Problems</b> you will find a paper:</p><p><a href="https://andrescaicedo.files.wordpress.com/2008/04/vdp-finalversion-withreferences.pdf">The fourteen Victoria Delfino Problems and their Status in the year 2015</a></p><p>(ADDED LATER: a comment pointed me to an updated version, so you can see that- I got to a pay wall.) </p><p>How did a real estate agent get honored by having 14 problems in descriptive set theory named after her?</p><p>Possibilities before I tell you which one.</p><p>1) Real estate is her day job. Her hobby is Descriptive Set Theory. Recall that Fermat was a lawyer (or something like that- see <a href="https://en.wikipedia.org/wiki/Pierre_de_Fermat">his Wikipedia page</a>) so perhaps she is similar. Doubtful- I think math is too hard for that now. Or at least descriptive set theory is too hard for that now. </p><p>2) She just happened to remark one day,<i> Gee, I wonder if</i></p><p><i> ZFC + SEP(Sigma_3^1) + # implies DET(Delta_2^1).</i> </p><p>Its just the kind of thing someone might just say. That was problem 4 of the 14. </p><p>3) There are two Victoria Delfino's- one is a realtor, one is a mathematician. While plausible, that would not be worth blogging about. </p><p>4) And now the truth: Victoria was the realtor who helped Moschovakis (a descriptive set theorist who I will henceforth describe as M) buy his house. When Tony Martin (another Desc. Set Theorist) moved to UCLA, M referred him to Victoria and she did indeed help Tony find a house. Victoria gave M a large commission which he tried to turn down. She did not want it returned, so M used the money to fund five problems. Later problems were added, but for no money. The article <i>The Fourteen... </i>linked to above has the full story. It also has the curious line: </p><p><i>Contrary to popular belief, no monetary prize is attached to further problems. </i></p><p>I didn't think any of this was so well known as to have popular believes. </p><p>ANYWAY, this is an example of a math problem named after a non-math person. Are there others? Will the name stick? Probably not- already 12 of the 14 are solved. I have noted in a prior blog (<a href="https://blog.computationalcomplexity.org/2009/08/how-much-credit-should-conjecturer-get_14.html">here</a>) once a conjecture gets proven, the one who made the conjecture gets forgotten. Or in this case the person who the conjectures is named after. </p><p>So are there other open problems in math named after non-math people? How about Theorems?</p><p>Near Misses: </p><p>Pythagoras: Not clear what he had to do with the theorem that bears his name. </p><p>L'hopital's Rule: the story could be a blog in itself, and in fact it is! Not mind, but someone else: <a href="https://andrescaicedo.wordpress.com/2013/11/05/credit/">here</a>. However L'hopital was a mathematician. </p><p>Sheldon's conjecture (see <a href="https://blog.computationalcomplexity.org/2019/10/the-sheldon-conjecture-too-late-for.html">here</a>) was named after a FICTIONAL physicist. Note that Sheldon inspired the conjecture but did not make it. It has been solved. </p><p>The Governor's Theorem (see <a href="https://blog.computationalcomplexity.org/2013/08/how-much-trig-does-your-governor-know.html">here</a>) was named because Jeb Bush was asked for the angles of a 3-4-5 right triangle (not a fair question). </p><p>The Monty Hall Paradox.</p><p>SO- are there Open Problems, Theorems, Lemmas, any math concepts, named after non-math people? I really mean non-STEM people. If a Physicist or an Engineer or a Chemist or Biologist or... has their name on something, that would not really be what I want.</p><p>(ADDED LATER - someone emailed me two oddly-named math things:</p><p>Belphegor's prime, <span style="background-color: white; color: #222222; font-family: Arial, Helvetica, sans-serif; font-size: small;">see </span><a href="https://en.wikipedia.org/wiki/Belphegor%27s_prime">here</a></p><p>Morrie's law- odd since Morrie is the FIRST name of who the name is honoring, see <a href="https://en.wikipedia.org/wiki/Morrie%27s_law">here</a> </p><p>)</p><p><br /></p><p>Are there any other open problems in descriptive set theory named after realtors?</p><p><i><br /></i></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2021/02/the-victoria-delfino-problems-example.htmlnoreply@blogger.com (gasarch)7tag:blogger.com,1999:blog-3722233.post-7991231367461036724Wed, 03 Feb 2021 13:26:00 +00002021-02-03T07:26:25.479-06:00A Blood Donation Puzzle<p>In the US you can donate whole blood every eight weeks. Suppose Elvira does exactly that. Will she hit every date of the year? For example, if Elvira gave blood today, will she in some future year give blood on the 4th of July? Can we figure it out without having to rely on a computer simulation or even a calculator?</p><p>Let's make the assumptions that the blood center is open every day and that Elvira gives blood exactly every 56 days for eternity. </p><p>A year has 365 days which is relatively prime to 56=2<sup>3</sup>*7 since 365 mod 2 =1 and 365 mod 7 = 1. By the <a href="https://en.wikipedia.org/wiki/Chinese_remainder_theorem">Chinese remainder theorem</a> her next 365 blood donations will be on 365 distinct dates. If Elvira started giving blood at age 17, she will have hit every date at age 73.</p><p>That was easy but wrong. We have to account for those pesky leap years.</p><p>In a four year span, there will be one leap day. The total days in four years (using modular arithmetic) will still be odd and 5 mod 7, so still relatively prime to 56. So Elvira will donate on every day on the calendar exactly four times, except February 29th which she will hit once, over a period 56*4=224 years. </p><p>Alas not quite. Years ending 00 are not leap years, unless the year is divisible by 400. 2000 was a leap year but 2100 won't be. Any stretch of 224 years will hit at least one of those 00 non-leap years.</p><p>In 400 years, there will be 97 leap years. Since a regular year is 1 mod 7 days and a leap year is 2 mod 7 days, 400 years will be 497 mod 7 days. Since 497=71*7, 400 years has a multiple of 7 days. Every 400 years we have exactly the same calendar. February 3, 2421 is also a Wednesday.</p><p>The cycle of blood donations will repeat every 3200 years, the number of years in the least common multiple of 56 and the odd multiple of seven number of days in 400 years. But we can no longer directly apply the Chinese remainder theorem and argue that every day of the year will be hit. In those 3200 years Elvira will have over 20,000 blood donations. If the dates were chosen randomly the expected number to hit all dates would be 2372 by <a href="https://en.wikipedia.org/wiki/Coupon_collector%27s_problem">coupon collector</a>. So one would expect Elvira would hit every day, but that's not a proof.</p><p>So I had to dust off my Python skills and do the computer simulation after all. No matter what day Elvira starts donating she will eventually hit every date of the year. If Elvira starts donating today, she would give blood on the 4th of July for the first time in 2035 and <a href="https://docs.google.com/document/d/10aTFv5UUWfsrkKmVeud_r2VObfS1_J1tJflMeWld2w4/edit?usp=sharing">hit all dates</a> on January 8, 2087 after 431 donations. The longest sequence is 3235 donations starting April 25, 2140 and hitting all dates on February 29, 2636.</p>https://blog.computationalcomplexity.org/2021/02/a-blood-donation-puzzle.htmlnoreply@blogger.com (Lance Fortnow)4tag:blogger.com,1999:blog-3722233.post-8809394001786387491Sun, 31 Jan 2021 21:50:00 +00002021-02-14T14:29:26.294-06:00Grading policies during Covid-No easy answers<p> Because of COVID (my spellecheck says covid and Covid are not words, but COVID is) various schools have done various things to make school less traumatic. Students already have problems, either getting COVID or having their friends got family get it (I've had four relatives get it, and one died) . Some do not adjust to learning online. Some do not have good computer connection to learn on line. So what is a good policy? Here are some things I have either seen schools do or heard that they might do.</p><p><br /></p><p>1) Be more generous with Tuition-Refunds if a student has to withdraw. </p><p>2) Be more generous with Housing-Refunds if a students comes to campus thinking it will be courses on campus and there are no courses on campus. Or if a student has to withdraw. </p><p>3) Make the deadlines for dropping-without-a-W, or taking-it-pass-fail, later in the semester. </p><p>4) Tell the teachers to `just teach them the bare min they need for the next course.'</p><p>5) Allow students to take courses P/F in their major and still allow them to count, so a student might get a D in Discrete Math and be able to go on in the major. </p><p>6) How far to extend deadlines? How is this: extend deadline to make it P/F until the last day of classes (but before the final) and then after the final is given, the school changes its mind and says - OH, you can change to P/F now if you want to.</p><p>7) Allow either an absolute number (say 7) or a fraction (say 1/3) of the courses to be changed to P/F by the last day of class.</p><p>8) Combine 6 or 7 with saying NO- a D is an F for a P/F course. Perhaps only if its in the major, but that maybe hard to work out. since majors can change. Some schools do A-B-C-NO CREDIT, where the NC grade does not go into the GPA.</p><p>9) Give standard letter grades and tell the students to tough it out. Recall the following inspirational quotes</p><p>When the going gets tough, the tough go shopping</p><p>When the going gets tough, the tough take a nap</p><p>If at first you don't succeed, quit. Why make a damn fool of yourself. </p><p>If at first you don't succeed, then skydiving is not for you. </p><p>10) Decide later in the term what to do depending on who yells the loudest. </p><p>11) Any combination of the above that makes sense, and even some that don't. </p><p><br /></p><p>On the one hand, there are students who are going through very hard times because of COVID and should be given a break. On the other hand, we want to give people a good education and give grades that are meaningful (the logic of how to give grades in normal times is another issue for another blog post). </p><p>What is your school doing? Is it working? What does it mean to be working?</p><p>The problems I am talking about are first-world problems or even champagne-problems. I know there are people who have far worse problems then getting a bad grade or dropping courses.</p><p><br /></p>https://blog.computationalcomplexity.org/2021/01/grading-policies-during-covid-no-easy.htmlnoreply@blogger.com (gasarch)4tag:blogger.com,1999:blog-3722233.post-5382973292753625821Thu, 28 Jan 2021 14:23:00 +00002021-01-28T08:23:56.081-06:00PhDs and Green Cards<p>Joe Biden's <a href="https://joebiden.com/immigration/">immigration policy</a> has some interesting policies for PhDs. </p><p></p><blockquote>Biden will exempt from any cap recent graduates of PhD programs in STEM fields in the U.S. who are poised to make some of the most important contributions to the world economy. Biden believes that foreign graduates of a U.S. doctoral program should be given a green card with their degree and that losing these highly trained workers to foreign economies is a disservice to our own economic competitiveness. </blockquote><p>Biden will submit an immigration plan to congress soon but it is not clear if the above will be in the bill, whether it will survive negotiations or even whether an immigration bill will be passed at all. </p><p>Nevertheless I worry about the unintended consequences of this policy. It will encourage students to apply and come for a PhD who have no interest in research, but want the green card. It gives too much power to professors who may abuse their students who need the PhD. Conversely it will pressure professors and thesis committees to grant PhDs because there would be a big difference between graduating with a PhD and leaving early with a Masters. By making the PhD so valuable, we may devalue it.</p><p>The solution is to give green cards to Masters students as well. We shouldn't limit talented researchers and developers who can help the United States keep its technology edge. They don't take jobs away from Americans, but instead help create new ones.</p><p></p>https://blog.computationalcomplexity.org/2021/01/phds-and-green-cards.htmlnoreply@blogger.com (Lance Fortnow)5tag:blogger.com,1999:blog-3722233.post-6340814883494512723Tue, 26 Jan 2021 06:33:00 +00002021-01-26T00:33:42.689-06:00Answers to the Prez Quiz, and some interesting history<p><br /></p><p>I posted a presidential quiz (that is, a quiz about presidents, not a quiz that is so majestic it can be called presidential) on Thursday Jan 21.</p><p>Here is the link to the post: <a href="https://blog.computationalcomplexity.org/2021/01/presidential-quiz-three-ways-to-take-it.html">The Post </a></p><p>Here is the link to the quiz:<a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/prezquiz.pdf">The Prez Quiz</a></p><p> I now post the answers here: <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/prezquizsol.pdf">The Prez Quiz Answers</a></p><p><br /></p><p>Looking back at the quiz and some prior ones I realize that some questions are TRIVIA while others are not- that is- they tell us something interesting beyond the answer. Some thoughts on that: </p><p><br /></p><p>a) Asking who the oldest prez ever has to be better defined. But however you define it, the answer is Joltin Joe. I will ask it as Age-when-sworn-in, which for Joltin Joe is 78. Second is Trump who was 70 when sworn in. INFO: Presidents seem to be getting older. Is this a trend or will 2024 and 2028 feature younger folks? I note that both VP's are in their 50's. </p><p>b) Presidential first via xkcd; <a href="https://xkcd.com/2383/">here</a></p><p>c) Between Nixon-Kennedy 1960 and Bush-Kerry 2004 EVERY election had one of he candidates being either a former or current Prez or Vice Prez. (This was a question on the 2008 quiz, but since the streak is broken it is no longer as interesting.) INFO: It was hard to break into the prez business unless you were already somewhat known. Having said that, note that some of the non-VPs and non-Prezs DID win. </p><p>d) Between 1948 and 2008 at least one of the candidates for Prez had served in the Military. How did they do? In many cases both served so I am not going to to a chart of how well the Military ones did. (This was a question on the 2012 quiz, but since the streak is broken it is no longer interesting.) INFO: At one time a lot of people were in the military. At one time a lot of people knew someone in the military. Now it seems like the military is rather far removed from civilians. </p><p>e) Kennedy was our first Catholic Prez in 1960. Biden is our second one in 2020. My impression is that it was an issue for the Kennedy Campaign but not for the Biden campaign. Romney being a Mormon seems to have not been an issue in the General election, but some of the other candidates brought it up in the primaries. INFO: Religious bigotry within different denominations of Christianity is declining. </p><p>f) Reagan was our first divorced Prez, in 1980. Trump was our second in 2016. It don't think it was an issue for either one. INFO: We need to couple this with Rockefellers divorce being a problem for him getting the nomination in 1964. Peoples attitude on divorce has changed A LOT. </p><p><br /></p><p>Contrast: Knowing which president had a fictional street gang named after him does not tell us anything about History .I will remove that question when I do the quiz in 2025. </p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2021/01/answers-to-prez-quiz-and-some.htmlnoreply@blogger.com (gasarch)3tag:blogger.com,1999:blog-3722233.post-1995922000817154646Fri, 22 Jan 2021 16:44:00 +00002021-01-22T18:05:26.986-06:00Alan Selman (1941-2021)<p></p><span style="text-align: center;"><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto;"><tbody><tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-4M0SuOy0o4s/X_y99qhI9aI/AAAAAAAB6E0/ZRefljNynqkOfgg4Kj3zCOk-dPyEp-TKACPcBGAsYHg/s2258/00000429.jpg" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="985" data-original-width="2258" height="246" src="https://1.bp.blogspot.com/-4M0SuOy0o4s/X_y99qhI9aI/AAAAAAAB6E0/ZRefljNynqkOfgg4Kj3zCOk-dPyEp-TKACPcBGAsYHg/w400-h174/00000429.jpg" width="550" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">From a 1994 Dagstuhl Workshop. Selman is the one wearing a cap.</td></tr></tbody></table></span><div>Alan Selman, one of the early leaders in structural complexity and the co-founder and first chair of what is now the Computational Complexity Conference, passed away this morning. He was one of the true greats in our field both for his research and his service.<p></p><p>Selman was a good colleague and a friend. I hosted his sabbatical at the University of Chicago in 1998 which <a href="https://doi.org/10.1007/s00224-001-0003-0">produced a paper</a> with Selman's student and my later postdoc Pavan Aduri. In Spring of 1999 Selman ran a NSF workshop in Chicago on <a href="https://cse.buffalo.edu/~selman/report/Report.html">Challenges for Theory of Computing</a>.</p><p>In a desire to create a community of complexity theorists and foster publications of their results, Selman led the efforts to establish the Structure in Complexity Theory conference, first held in 1986 in Berkeley, California. As a student in Berkeley I attended that meeting and the next twenty-five. The conference would join the IEEE in 1987, in 1996 renamed the IEEE Conference and Computational Complexity and in 2015 drop from the IEEE to become the Computational Complexity Conference, still going strong. Alan served as the first conference chair and as PC co-chair of the first meeting. </p><p>For all his service for the field, Selman received the ACM SIGACT Distinguished Service Award in 2002.</p><p>Selman joined University at Buffalo in 1990 to serve six years as department chair and then as a professor until he retired in 2014. Lane Hemaspaandra wrote a highly recommended <a href="https://arxiv.org/abs/1406.4106">appreciation</a> for Selman and his research in honor of his retirement where he mentions some of Selman's research programs, including his seminal work on P-Selective sets, non-deterministic functions and his work with Joachim Grollman on one-way functions. Selman came down hard on anyone who got the wrong number of l's in Grollman, so we would often joking cite it as Grollman and Sellman or just Grollman et Al.</p><p>In my <a href="https://doi.org/10.1137/S0097539794268315">favorite Selman paper</a>, in work with Hemaspaandra, Ashish Naik and Mitsu Ogihara, looks at witness reduction. If there is a set A in P such that for all satisfiable formula φ there is a unique satisfying assignment a of φ such that (φ,a) is in A then the polynomial-time hierarchy collapses. The more general question of whether NP=UP implies the polynomial-time hierarchy collapses <a href="https://blog.computationalcomplexity.org/2003/12/does-npup.html">remains open</a>.</p><p>Also <a href="https://doi.org/10.1016/0022-0000(92)90023-C">Selman's paper with Steve Homer</a> giving an oracle where Σ<sub>2</sub><sup>P</sup>-complete sets were isomorphic was instrumental to my own work on the isomorphism conjecture.</p><p>Bill wanted me to mention the Selman paper that most influenced him. Selman and Theodore Baker and <a href="https://doi.org/10.1016/0304-3975(79)90043-4">gave the first oracle</a> separating the second level of the polynomial-time hierarchy in 1979. It would take <a href="https://doi.org/10.1109/SFCS.1985.49">Yao</a> and <a href="https://doi.org/10.1145/12130.12132">Håstad</a> over five more years to get the whole hierarchy infinite relative to an oracle. The Baker-Selman proof could easily extend to show that AM games did not sit in Σ<sub>2</sub><sup>P</sup>, a bit surprising as MA is in Σ<sub>2</sub><sup>P</sup>.</p><p>In addition to his research, Selman wrote an <a href="https://amzn.to/3oBKWsD">introductory theory textbook</a> with Homer as well as <a href="https://amzn.to/38zspaQ">editor</a> and <a href="https://amzn.to/3qeA8kj">co-editor</a> of two editions of Complexity Theory Retrospective.</p><p>It would be no exaggeration to say the field of computational complexity and my own research within it would have been much different without Alan.</p><p>Alan drove a car with a "P NE NP" license plate. One day someone came up to him in a parking lot and said "Yes, but can you prove it?" Possibly the one thing in complexity he couldn't do.</p></div>https://blog.computationalcomplexity.org/2021/01/alan-selman-1941-2021.htmlnoreply@blogger.com (Lance Fortnow)8tag:blogger.com,1999:blog-3722233.post-5862964813565889129Fri, 22 Jan 2021 05:53:00 +00002021-01-21T23:53:08.532-06:00Presidential Quiz: Three ways to take it<p> Every four years around the time of the inaugural I post a presidential Quiz! I do that today, and I will post the answers on Monday. I am tempted to joke that I am posting it AFTER Joltin Joe gets sworn in just in case something happens; however, I always posted it after the prez is sworn in. </p><p>The quiz is here: <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/prezquiz.pdf">quiz</a></p><p><b> GRADING CRITERIA</b></p><p>33 questions, 3 points each, and 1 free point.</p><p>If the answer is a list of L elts and you get x correct, you get x/L points. If any are wrong then 0 points.</p><p>You can take the quiz one of three ways.</p><p>1) Take it WITHOUT using the web and see how many you can get right. Take 3 hours.</p><p>WARNING- its a hard quiz so this may not be fun. </p><p>2) Take it and use the web and try to do it fast. Stop when you want. Your Score is as follows:</p><p>If R is the number if points and T be how many minutes you took, your score is </p><p> (180R/T)+ 1.</p><p>If you get all 33 right in 60 minutes then you get a 100. You could get more than 100 if you do it faster.</p><p>3) The answer key has all kinds of other information in it and is fun to read. So do not take the quiz and enjoy reading the answers on Monday. That's what I did. </p><p><br /></p><p>I was curious if Joltin Joe would be sworn in by Joseph or Joe. I was routing for Joe so he would be the second president sworn in by his nickname (Jimmy Carter was the first--his real name is James). When I am sworn in as president I will use <i>Bill</i> and hence join the nickname-club. Lance does not have a nickname, so my veep will be sworn in by his actual name. Would we win? Is America ready for a 2-Phd ticket? </p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2021/01/presidential-quiz-three-ways-to-take-it.htmlnoreply@blogger.com (gasarch)2tag:blogger.com,1999:blog-3722233.post-2344881105581863703Tue, 19 Jan 2021 12:10:00 +00002021-01-19T06:17:59.964-06:00The Ethics Board<p>Back in 2014 I recommended a <a href="https://blog.computationalcomplexity.org/2014/03/should-we-have-tcs-ethics-board.html">TCS ethics board</a> mainly to deal with plagiarism and who should get credit for a result. It went the way of most suggestions I make in my blog, a quick road to nowhere. Bill <a href="https://blog.computationalcomplexity.org/2014/03/should-we-have-tcs-ethics-board.html?showComment=1396496899643#c955985184567246644">asked</a> "Does any other branch of CS have an ethics board? How have they worked?"</p><p>The NeurIPS conference created a such a board for the <a href="https://neuripsconf.medium.com/what-we-learned-from-neurips-2020-reviewing-process-e24549eea38f">reviewing process</a>, though with a broader mission.</p><p></p><blockquote><p>We appointed an ethics advisor and invited a pool of 22 ethics reviewers (listed <a href="https://neurips.cc/Conferences/2020/ProgramCommittee">here</a>) with expertise in fields such as AI policy, fairness and transparency, and ethics and machine learning. Reviewers could flag papers for ethical concerns, such as submissions with undue risk of harm or methods that might increase unfair bias through improper use of data, etc. Papers that received strong technical reviews yet were flagged for ethical reasons were assessed by the pool of ethics reviewers.</p><p>Thirteen papers met these criteria and received ethics reviews. Only four papers were rejected because of ethical considerations, after a thorough assessment that included the original technical reviewers, the area chair, the senior area chair and also the program chairs. Seven papers flagged for ethical concerns were conditionally accepted, meaning that the final decision is pending the assessment of the area chair once the camera ready version is submitted. Some of these papers require a thorough revision of the broader impact section to include a clearer discussion of potential risks and mitigations, and others require changes to the submission such as the removal of problematic datasets. Overall, we believe that the ethics review was a successful and important addition to the review process. Though only a small fraction of papers received detailed ethical assessments, the issues they presented were important and complex and deserved the extended consideration. In addition, we were very happy with the high quality of the assessments offered by the ethics reviewers, and the area chairs and senior area chairs also appreciated the additional feedback.</p></blockquote><p></p><div>Without seeing the process I cannot say what criteria were used to reject the four papers. There could be legitimate reasons if the authors did violate professional ethics or even inadvertently based their results on biased data sets. But there's a fine line to rejecting papers because you don't like the outcome or the questions they ask. No easy answers here.</div>https://blog.computationalcomplexity.org/2021/01/the-ethics-board.htmlnoreply@blogger.com (Lance Fortnow)2tag:blogger.com,1999:blog-3722233.post-6412374969669821012Mon, 11 Jan 2021 04:39:00 +00002021-01-13T16:24:36.792-06:00The ACM History Committee call for proposals looks wrong<p> In November I (and prob everyone in the ACM) got an email that was a call for proposal from the ACM History committee. <a href="https://history.acm.org/wp-content/uploads/2020/11/ACM-fellowship_CFP_2021-final-1.pdf">Here</a> is a pointer to it. </p><p>One of the passages in it just seems wrong to me:</p><p><i>This fellowship program is designed to support research and/or curatorial projects related to ACM's professional and educational activities and/or to ACM's rich institutional history including its organization, SIG activities, and conferences. </i></p><p>I will give examples of history projects that are interesting but do not fit the description. I challenge you to give me a history project that is interesting that does fit the bill. </p><p>1) Compare and contrast how NP-completeness developed in America and in the USSR. For the USSR side it would be an expansion of Trakhtenbrot's article <a href="https://drdoane.com/wp-content/uploads/2020/08/survey_of_russian_approaches_to_perebor.pdf">here</a>. OH, no good, Leonid Levin was not a member of the ACM.</p><p>2) Measure how various CS fields have changed by looking at the topics on the CALL FOR PAPERS for a conference. This would be a MASSIVE expansion of my blog post on how CCC call for papers, changed , see <a href="https://blog.computationalcomplexity.org/2011/05/how-has-structures-oh-i-mean-ccc.html">here</a>. OH, I could only do ACM conferences. STOC but not FOCS. Okay, it makes perfect sense to study only ACM conference. Oh wait. IT MAKES NO SENSE WHATSOEVER.</p><p>3) When did mathematicians begin looking at P vs NP seriously? (e.g., In The Handbook of Mathematical Logic from 1977 only one article mentions P vs NP: Michael Rabin's article on Decidable theories mentioned that even decidable theories may take a long time to decide and noted the importance of the P vs NP problem). How did MATH and CS interact early on and now? This would need one to look at math journals. How many of those are ACM? I would guess very few. </p><p>4) When did engineers begin looking at P vs NP seriously, or even notice it? Same issue as the last item. </p><p>5) Looking at how Programming lang design has changed one would have to only look at conference and journals that were ACM. And for those that were ACM but then dropped ACM you might only be able to use them up to the cutoff year. </p><p>6) Which academic studies eventually lead to practical products people can use? This is a really broad topic so one could narrow it down to just academic studies that appeared in ACM journals or conferences. Is that a good way to narrow the focus? Spoiler alert: NO.</p><p>7) I recently filled out a survey about the future of theory and if it is insular (the topic of another post surely). Most of the questions were about ``STOC-FOCS'' The people who did the survey clearly do not care that one is ACM and one is IEEE. Does anyone? I ask non-rhetorically. </p><p>Despite the capitol letters, I am not so much mad as puzzled. So I ask non-rhetorically: </p><p>Q1) Did the ACM really mean for people to do history in a way where you can only use ACM materials? </p><p>Q2) If no then please rewrite the Call for Proposals. </p><p>Q3) If yes then give examples of studies that would be interesting. </p><p>I am not asking to be snarky, I really want to know. And I note that <i>interesting</i> is subjective. </p><p>(ADDED LATER- two historians who have worked with this kind of history left comments that indicate the grant is FINE with non-ACM stuff, so Q1 above seems to have the answer NO. Given that they should rewrite the call for proposal next time they do this. ALSO- the historians left pointers to VERY INTERESTING papers they wrote.) </p><p><i><br /></i></p><p><br /></p>https://blog.computationalcomplexity.org/2021/01/the-acm-history-committee-call-for.htmlnoreply@blogger.com (gasarch)12tag:blogger.com,1999:blog-3722233.post-44450853695391906Wed, 06 Jan 2021 01:13:00 +00002021-01-05T19:13:14.547-06:00My Survey on Hilbert's 10th for particular (d,n) is ready for you to help me on!<p> Hilbert's 10th problem is (in modern terminology) to find an algorithm that will, given a poly </p><p>p(x1,...,xn) in Z[x1,...,xn], determine if it has a solution in the integers. </p><p>This was shown undecidable by the combined efforts of Davis-Putnam-Robinson and Matiyasevich. </p><p>I posted <a href="https://blog.computationalcomplexity.org/2020/05/why-is-there-no-dn-grid-for-hilberts.html">here</a> about the question of: For which (d,n) is H10 undecidable when restricted to degree d and number of vars n?</p><p>I was invited to make an article out of the blog post and what I learned from the comments for the Algorithms column of BEATCS. That first draft is</p><p><a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/h10_final.pdf">here</a><br /></p><p><br /></p><p>Did I miss an important reference? (Note- I had meant to get out Matiyasevich's book on H10 but have been unable to because of the Pandemic, so if you have it my have stuff I need to know.) </p><p>Did I misspell Matiyasevich? </p><p>Did I say something stupid?</p><p>Please leave comments or email me directly if you have suggestions. </p><p>Incidentally I am usually the one who is asking someone else to do an open problems column, a book review, a guest blog. Nice to be the askee instead of the asker for a change of pace. </p><p><br /></p>https://blog.computationalcomplexity.org/2021/01/my-survey-on-hilberts-10th-for.htmlnoreply@blogger.com (gasarch)5tag:blogger.com,1999:blog-3722233.post-373991171790634666Thu, 31 Dec 2020 12:24:00 +00002020-12-31T14:34:26.850-06:00Complexity Year in Review 2020<div>For the result of the year we go to all the way back to the "before times".</div><blockquote><div><a href="https://arxiv.org/abs/2001.04383">MIP*=RE</a> by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen</div></blockquote><div>A follow up to last year's runner up <a href="https://arxiv.org/abs/1904.05870">NEEXP in MIP*</a>, the new paper shows how to prove everything computable and beyond to a polytime verifier with two provers who cannot communicate but share entangled quantum bits. The result had a bit of a scare but <a href="https://blog.computationalcomplexity.org/2020/10/mip-re-redux.html">fixed up this fall</a>.</div><div><br /></div><div>Honorary mention goes to <a href="https://arxiv.org/abs/2007.01409">beating the Christofides-Serdyukov approximation</a> for traveling salesman by Anna R. Karlin, Nathan Klein and Shayan Oveis Gharan. Nathan got his start in Bill's REU program.</div><div><br /></div><div>Of course when we think back at 2020 it won't be the theorems but the pandemic, a divisive election and racial reckoning. The word of the year for academia is "virtual", virtual teaching, virtual research collaborations, virtual talks, virtual conferences, virtual panels and virtual job visits. For the most part the the pandemic hasn't really created new trends but accelerated trends already in place. Given the far lower costs in terms of time, money and the environment, how much of "virtual" will remain post-corona?</div><div><br /></div><div>Bill's published a new book on <a href="https://amzn.to/3avH9J9">muffin problems</a>, his second book in two years. I started a new <a href="https://www.iit.edu/news/illinois-tech-creates-college-computing-fuel-chicagos-tech-rise">College of Computing</a>. </div><div><br /></div><div>We remember <a href="http://blog.geomblog.org/2020/12/lars-arge.html">Lars Arge</a>, <a href="https://www.scs.cmu.edu/news/edmund-clarke-pioneered-methods-detecting-software-hardware-errors">Ed Clarke</a>, <a href="https://blog.computationalcomplexity.org/2020/04/john-conway-dies-of-coronvirus.html">John Conway</a>, <a href="https://blog.computationalcomplexity.org/2020/05/obit-for-richard-dudley.html">Richard Dudley</a>, <a href="https://cpsc.yale.edu/news/memoriam-stanley-c-eisenstat-1944-2020">Stanley Eisenstat</a>, <a href="https://blog.computationalcomplexity.org/2020/07/reflections-on-ronald-graham-by-steve.html">Ron Graham</a>, <a href="https://blog.computationalcomplexity.org/2020/03/richard-guy-passed-away-at-age-of-103.html">Richard Guy</a>, <a href="https://www.nytimes.com/2020/02/24/science/katherine-johnson-dead.html">Katherine Johnson</a>, <a href="https://blog.computationalcomplexity.org/2020/11/vaughan-jones-and-kaikoura.html">Vaughn Jones</a>, <a href="https://blog.computationalcomplexity.org/2020/11/james-randi-magicians-author-skeptic.html">James Randi</a>, <a href="https://twitter.com/betanalpha/status/1343770446777495552">Arianna Rosenbluth</a>, <a href="https://www.indiatechonline.com/it-happened-in-india.php?id=3995">Joy Thomas</a>, <a href="https://blog.computationalcomplexity.org/2020/03/robin-thomas.html">Robin Thomas</a>, <a href="https://blog.computationalcomplexity.org/2020/11/alex-trebekwhat-is-todays-post-about.html">Alex Trebek</a>, <a href="https://gilkalai.wordpress.com/2020/04/03/trees-not-cubes-memories-of-boris-tsirelson/">Boris Tsirelson</a> and <a href="https://blog.computationalcomplexity.org/2020/03/theorist-paul-r-young-passed-away.html">Paul Young</a>. </div><div><div><br /></div><div>Thanks to our guest posters <a href="https://blog.computationalcomplexity.org/2020/12/dr-jill-biden.html">Gorjan Alagic, Andrew Childs, Tom Goldstein, Daniel Gottsman, Clyde Kruskal and Jon Katz</a>, <a href="https://blog.computationalcomplexity.org/2020/04/theoretical-computer-science-for-future.html">Antoine Amarilli, Thomas Colcombet, Hugo Férée and Thomas Schwentick</a>, <a href="https://blog.computationalcomplexity.org/2020/07/reflections-on-ronald-graham-by-steve.html">Steve Butler</a>, <a href="https://blog.computationalcomplexity.org/2020/06/on-chain-letters-and-pandemics.html">Varsha Dani</a>, <a href="https://blog.computationalcomplexity.org/2020/02/pre-publish-and-perish.html">Evangelos Georgiadis</a> and <a href="https://blog.computationalcomplexity.org/2020/04/a-guest-blog-on-pandemics-affect-on.html">Emily Kaplitz</a>.</div></div><div><br /></div><div>In 2021 we will likely see the end of the pandemic and most definitely see the 50th anniversary of P versus NP. Hope for a successful and healthy year for all. </div>https://blog.computationalcomplexity.org/2020/12/complexity-year-in-review-2020.htmlnoreply@blogger.com (Lance Fortnow)2tag:blogger.com,1999:blog-3722233.post-1031792436674372594Thu, 24 Dec 2020 15:16:00 +00002020-12-24T09:16:14.228-06:00Slowest Sorting Algorithms<p>Radu Gigore <a href="https://twitter.com/rgrig/status/1342015488252063744">tweeted</a> "People are obsessed with finding the best algorithms. What about the worst?" So here's a Christmas gift that keeps giving, the slowest of sorting algorithms. </p><p>Before you read on, try to think of the slowest sorting algorithm. No fair spinning its wheels, sleeping or doing unrelated tasks. It should always make progress towards sorting. </p><p>Here are some <a href="https://www.geeksforgeeks.org/the-slowest-sorting-algorithms/">examples</a>, in particular bogosort that generates all permutations until it finds a sorted one. Takes n! time on average.</p><p>But we can do much worse. The following redicusort algorithm I got from Stuart Kurtz back in the 90's.</p><blockquote><p>Generate all permutations and then sort those permutations. The sort of the original permutation will be first on the list.</p></blockquote><p>The running time depends on the sorting algorithm you use after generating the permutations.</p><p>If you use bubblesort you get a (n!)<sup>2</sup> time algorithm. </p><p>If you use bogosort you get a (n!)! bound.</p><p>What if you just call redicusort recursively? The algorithm will never end. If you want to guarantee termination you need to bound the depth of the recursion. Choose something like an <a href="https://en.wikipedia.org/wiki/Ackermann_function">Ackermann function</a> to get a sorting algorithm that always makes progress but not primitively recursive. In general you can get a sorting algorithm that takes longer than any fixed computable function.</p>https://blog.computationalcomplexity.org/2020/12/slowest-sorting-algorithms.htmlnoreply@blogger.com (Lance Fortnow)12tag:blogger.com,1999:blog-3722233.post-985389002707236859Sun, 20 Dec 2020 06:22:00 +00002020-12-28T11:27:00.843-06:00Dr Jill Biden<p>(I was helped on this post by Gorjan Alagic, Andrew Childs, Tom Goldstein, Daniel Gottsman, Clyde Kruskal, Jon Katz. I emailed them for their thoughts on the issue and some of those thoughts are embedded in the post. ) </p><p>The First First Lady to have a college degree was Lucy Hayes (Rutherford B Hayes was Prez 1876-1880). Nickname: Lemonade Lucy since she did not serve alcohol. </p><p>Trivia: who was the last first lady to not have a college degree? I'll answer that one at the end of this post. </p><p>The First First Lady to keep her day job was Abigail Fillmore who was a teacher. (Millard Fillmore was Prez in 1850-1852. He became prez after Zachary Taylor died in office) . </p><p>In recent times it is uncommon for a first lady to have a day job. So much so that it was notable when Elizabeth Dole said that if her husband (Bob Dole) won in 1996 she would keep her job at the Red Cross. </p><p>For other first lady firsts see <a href="https://en.wikipedia.org/wiki/List_of_United_States_First_Lady_firsts#:~:text=Grace%20Coolidge,-Main%20article%3A%20Grace&text=First%20first%20lady%20to%20earn%20a%20four%2Dyear%20undergraduate%20degree.">here</a>.</p><p>Jill Biden is the First First Lady to have a PhD. (ADDED LATER- one of the comments pointed out that she has an Ed. D, Doctor of Education.) She says she will keep her day job as a professor. Four other First ladies had advanced degrees: Pat Nixon (MS in Education), Laura Bush (MS in Library Science), Hillary Clinton (Law degree), Michelle Obama (Law degree). If I missed any, let me know. </p><p>The WSJ had an op-ed that said Jill Biden should not call herself `Dr'. Inspired by that, here are thoughts on the use of the word `Dr'</p><p>1) At the 1986 Structures Conference (now Complexity Conference ) Lane Hemachandra (now Lane Hemaspaandra) gave a talk. He had just gotten his PhD a few weeks ago, so he was introduced as `DOCTOR Lane Hemchandra' Gee, most of the talks were by people with PhD's but were not introduced as such.</p><p>2) Most people I know within academia do not call themselves Dr since it sounds pretentious. However, speaking in public about an issue one might want to use `Dr' to signal that you...know stuff. However, it would be odd for a PhD in (say) linguistics to claim he knows a lot about (say) politics. It has been said: an Intellectual is someone who is an expert in one field and pontificates in another field. </p><p>3) Does the general public think of DOCTOR as Medical Doctor? Probably yes. There are some exceptions: Dr. Martin Luther King and Dr. Henry Kissinger. Also, I think it is more common in Psychology, pharmacy, education, and counseling to call yourself `Doctor' </p><p>4) The article also criticized her PhD (in education, about community colleges) as `useless' . If that's the reason to not call her doctor than I shudder to think what the WSJ would think of degrees in, say, set theory with an emphasis on Large Cardinals. GEE, you can't call yourself DOCTOR since your degree is on Ramsey Cardinals. OH, now they found an application, so now you CAN call yourself DOCTOR. OH, the application is to extending the Canonical Ramsey Theory from Polish spaces to meta- compact cardinals, so we can't call you DOCTOR after all. Do we really want to go down this path? </p><p>5) I ask all of the following non-rhetorically: Did the author read her PhD thesis? Is he qualified to judge it? Did he (as one should do) look at her entire body of work to judge her? What point is he trying to make anyway? </p><p>6) Should Dr. Who call themselves a doctor? Are they a medical doctor? PhD? If so, in what? Is `Who' part of their name? For other TV and movie tropes about the use of the word doctor, see <a href="https://tvtropes.org/pmwiki/pmwiki.php/Quotes/NotThatKindOfDoctor">here</a>.</p><p>7) I avoid saying I am a doctor since people will then ask me about the medical condition.</p><p>I avoid saying I am a computer scientist since people will then ask me how to help them with their Facebook privacy settings. </p><p>I avoid saying I am a mathematician since people will ask me to help their daughter with her trigonometry. </p><p>8) The answer to my trivia question: The last first lady to not have a college degree: Melania Trump. She went to college for a year and then left. The one before her was Barbara Bush who also went for a year and then left. </p><p>ADDED LATER: Many supervillians who don't have a PhD or an MD call themselves `Doctor', see <a href="https://www.buzzfeed.com/donnad/11-super-villains-masquerading-as-doctors">here</a>. Why no outrage about this? Because (1) they are fictional, and (2) imagine the scenario: Not only does Dr. Doom want to take over the world, he also doesn't even have a PhD or an MD!</p><p><br /></p><p>ADDED LATER: Where does Dr. Pepper fit into this? </p><p><br /></p>https://blog.computationalcomplexity.org/2020/12/dr-jill-biden.htmlnoreply@blogger.com (gasarch)12tag:blogger.com,1999:blog-3722233.post-411297283565155244Wed, 16 Dec 2020 14:59:00 +00002020-12-16T08:59:23.018-06:00Optiland<p>Many of you have heard of Russell Impagliazzo's <a href="https://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html">five worlds</a> from his 1995 classic <a href="https://doi.org/10.1109/SCT.1995.514853">A personal view of average-case complexity</a> In short </p><ul><li><i>Algorithmica</i>: P = NP or something "morally equivalent" like fast probabilistic algorithms for NP. </li><li><i>Heuristica</i>: NP problems are hard in the worst case but easy on average.</li><li><i>Pessiland</i>: NP problems hard on average but no one-way functions exist. We can easily create hard NP problems, but not hard NP problems where we know the solution. </li><li><i>Minicrypt</i>: One-way functions exist but we do not have public-key cryptography.</li><li><i>Cryptomania</i>: Public-key cryptography is possible, i.e. two parties can exchange secret messages over open channels.</li></ul><div>Impagliazzo's world has an explicit "you can't have your cake and eat it too", either you can solve NP-hard problems on average, or have cryptography but not both (neither is possible). That's the mathematical world of P v NP. </div><div><br /></div><div>The reality is looking more and more like <i>Optiland</i>, where we can solve difficult NP problems and still have cryptography thanks to vast improvements in machine learning and optimization on faster computers with specialized hardware.</div><div><br /></div><div>Back in 2004 I <a href="https://blog.computationalcomplexity.org/2004/05/what-if-p-np.html">gave my guess</a> of the world of P = NP</div><div><blockquote>Learning becomes easy by using the principle of Occam's razor--we simply find the smallest program consistent with the data. Near perfect vision recognition, language comprehension and translation and all other learning tasks become trivial. We will also have much better predictions of weather and earthquakes and other natural phenomenon.</blockquote><p>Today you can take your smartphone, unlock it by having the phone scan your face, and ask it a question by talking and often get a reasonable answer, or have your question translated into a different language. You get alerts on your phone for weather and earthquakes, with far better predictions than we would have though possible a dozen years ago.</p><p>We have computed the <a href="http://www.math.uwaterloo.ca/tsp/uk/index.html">shortest traveling-salesman tour</a> through nearly 50K UK pubs. <a href="https://deepmind.com/blog/article/alphafold-a-solution-to-a-50-year-old-grand-challenge-in-biology">AlphaFold</a> can simulate protein folding with an accuracy nearly as good as what we get with real-world experiments. You can view GPT-3 as generating a form of a universal prior. Even beyond P = NP, we have self-trained computers easily besting humans in Chess, Go and Poker.</p><p>Meanwhile these techniques have done little to break cryptographic functions. Plenty of cybersecurity attacks but rarely by breaking the cryptography. </p><p>Not all is rosy--there is still much more we could do positively if P = NP and we are already seeing some of the negative effects of learning such as loss of privacy. Nevertheless we are heading to a de facto best of both worlds when complexity theory tells us those worlds are incompatible. </p></div><p></p>https://blog.computationalcomplexity.org/2020/12/optiland.htmlnoreply@blogger.com (Lance Fortnow)10tag:blogger.com,1999:blog-3722233.post-4105007709227774779Sat, 12 Dec 2020 20:33:00 +00002020-12-12T14:35:02.071-06:00Quarterly Th. Wksp `at' Northwestern, and thoughts inspired by it <p> On the <a href="https://theory.cs.northwestern.edu/events/">Northwestern CS Theory Group</a> there is a set of Quarterly Theory Workshops. There is one coming up on Dec 17-18, 2020, called the <a href="https://theory.cs.northwestern.edu/events/2020-junior-theorists-workshop/">Junior Theorists Workshop</a>. Take a look and possibly go to it! Because it is virtual you do not need to plan that much ahead- though they do want you to register. </p><p>1) I notice broadly two kinds of meetings:</p><p><br />Based on WHO will be there, e.g., JUNIOR theorists</p><p><br />Based on TOPIC: e.g., there was a meeting on ALGORITHMIC FAIRNESS.</p><p><br /></p><p>2) These types of meetings (NY Theory day is another) are, I believe, intended to be for people that are local (more on that later). But because the meeting will be on zoom, geography is no longer an impediment for either the attendees or the speakers. </p><p><br /></p><p>3) Before covid there was some talk of `Gee, flying off to STOC, FOCS, other conferences is bad for the environment, what to do about that?'. With that in mind, here is a history which might not be true but makes a point:</p><p><i>In an earlier era FOCS/STOC were attended by mostly Americans and ICALP was attended by mostly Europeans. I do not think there was any policy of discrimination on admissions, but it was more like Americans just did not submit to ICALP as much, nor Europeans to FOCS/STOC. But over time when these conferences got to be considered prestigious people would routinely submit to either one depending on timing. If your paper was done in time for Conf X deadline, that's where you submit. If it does not get in then you edit it some, perhaps add some new results, and submit to Conf Y. </i></p><p>So one solution to the air-travel-global-Warming problem of conferences is go back to a time (which may not have ever existed) where it was just understood that you go to LOCAL conferences. Math does this, but it helps that their regional conferences are not prestigious. But even they don't quite get it right: the joint AMS-MAA meeting alternates coasts. One year when it was in California they invited me to be a guest speaker (on the Muffin Problem). The following year it was in Baltimore. Note that I live in Maryland, so perhaps they should have waited a year. </p><p>How to encourage people to submit locally. I DO NOT want to have a rule or a diff standard for those who don't. As such... I have no idea. </p><p><br /></p><p>4) Are virtual conferences a good idea? This is a hot topic now so I won't dwell on it, just to say that there is still something about being there IN PERSON, meeting people, serendipity that makes live confs better.</p><p>However, to have it at the same time be virtual and recorded will be VERY HELPFL to those who can't afford to go for whatever reason. </p><p>And of course there is the whole issue of if we should have prestigious conferences, which I won't get into now. Or later. That's more Lance's issue (he thinks no). </p><p><br /></p>https://blog.computationalcomplexity.org/2020/12/quarterly-theory-workshop-any-lessons.htmlnoreply@blogger.com (gasarch)4tag:blogger.com,1999:blog-3722233.post-4139075556580650905Wed, 09 Dec 2020 17:55:00 +00002020-12-09T11:55:21.900-06:00Shuffling Around<p>In the fall of 1983 as a junior at Cornell I took CS 481, Introduction to the Theory of Computing, from Juris Hartmanis. Needless to say this was the course that changed my life and led me down a path that would have me teach a variation of this course myself more than twenty times.</p><p>For some reason one of the final exam questions is still stuck in my head.</p><blockquote style="border: none; margin: 0px 0px 0px 40px; padding: 0px; text-align: left;"><p>Let the permutation of a language L be the set of strings x such that there is a string y in L which is a permutation of the letters in x. For example perm({01},{001})={01,10,001,010,100}. </p><p>Are regular languages closed under permutations?</p></blockquote><p>There's a short and easy answer that's not so easy to find. Just in that P v NP spirit a Hartmanis test question should have. Give it a try before you read more.</p><p>If you <a href="https://www.chegg.com/homework-help/questions-and-answers/ll-shuffle-language-l-let-shuffle-l-following-language-w-x-elementof-l-w-x-w-permutation-l-q23260847">ask Chegg</a> you end up with </p><div class="separator" style="clear: both; text-align: center;"><a href="https://d2vlcm61l7u1fs.cloudfront.net/media%2F357%2F35711f1a-f8bc-490e-893d-cb13349ebfa3%2FphpMmxXRb.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="138" data-original-width="800" height="70" src="https://d2vlcm61l7u1fs.cloudfront.net/media%2F357%2F35711f1a-f8bc-490e-893d-cb13349ebfa3%2FphpMmxXRb.png" width="400" /></a></div><p>And for $15 you can get the answer. Back in 1983 we called that cheating.</p><p>The hint only works if there are regular languages whose permutations are not context free. Which is true in general but oddly enough the <a href="https://cs.stackexchange.com/questions/55507/proving-that-the-scramble-of-a-regular-language-is-context-free">permutation of every context-free language over a two-letter alphabet is context free</a>. The proof uses <a href="https://en.wikipedia.org/wiki/Parikh%27s_theorem">Parikh's theorem</a> which implies that the permutation of any context-free language is the permutation of a regular language (over any alphabet size).</p><p>Some other fun permutation questions:</p><p></p><ul style="text-align: left;"><li>Show that NP is closed under permutations.</li><li>Show that P is closed under permutations if and only if E = NE.</li><li>What about NL and L?</li></ul><div>Go ahead and chegg on those. </div><p></p>https://blog.computationalcomplexity.org/2020/12/shuffling-around.htmlnoreply@blogger.com (Lance Fortnow)6tag:blogger.com,1999:blog-3722233.post-3063488709598214165Mon, 07 Dec 2020 02:53:00 +00002020-12-06T20:53:46.697-06:00In 1974 Planarity was O(V) time and could do 900 node graphs in 12 seconds! Fast then...<p>In 1974 Hopcroft and Tarjan showed that Planarity is in polynomial time. That is an understatement- they actually have an O(V) algorithm which one can actually code up. See their paper <a href="https://dl.acm.org/doi/pdf/10.1145/321850.321852">here</a>.</p><p>It has the curious line:</p><p><br /></p><p><i>An Algol implementation of the algorithm successfully tested graphs with as many as 900 vertices in less than 12 seconds.</i></p><p>900 nodes in 12 second was fast then but it slow now. </p><p>1) How would their algorithm do on todays machines? How does that compare to what Moore's law (for time) would have predicted? Can this help us determine an x such that Moore's law stopped working at year x. I've heard various candidates for x including the notion that the death of Moore's law has been greatly exaggerated. Moore himself is still alive, at the age of 91. </p><p>2) Are there better algorithms now? Nothing can beat O(V); however, is there an algorithm with a better constant? </p><p>3) Is there a modern implementation of it (or perhaps even an old implementation run on a modern machine)? If so, how fast does it run on 900 nodes? 9000 nodes? 90,000 nodes? 900,000 nodes? Not sure where to stop.</p><p>4) The people in the real world who really need to solve this problem fast: (a) do they exist, and (b) if they do exist then what do they use? </p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2020/12/in-1974-planarity-was-ov-time-and-could.htmlnoreply@blogger.com (gasarch)3tag:blogger.com,1999:blog-3722233.post-3699673705974309715Thu, 03 Dec 2020 14:48:00 +00002020-12-03T08:48:25.433-06:00Chess is Back<p>Back in 2005, I wrote a post titled <a href="https://blog.computationalcomplexity.org/2005/11/chess-and-poker.html">Chess and Poker</a>. Not really comparing the two but noting that Chess had lost its mojo while poker had high-stakes prime time tournaments. The inspiration was an <a href="https://www.nytimes.com/2005/11/27/opinion/all-the-right-moves.html">NYT Op-Ed</a> that started "CHESS in America is having a crisis". I suggested that computers getting better than humans may have reduced interest in the game. </p><p>Now chess is <a href="https://www.nytimes.com/2020/11/23/arts/television/chess-set-board-sales.html">booming again</a>, due to all of us being stuck at home and the Netflix limited series <a href="https://www.imdb.com/title/tt10048342/">The Queen's Gambit</a> (highly recommended). </p><p>The fictional show takes place in the 1960's when interest in chess in the US started to pick up due to <a href="https://blog.computationalcomplexity.org/2008/01/bobby-fischer-guest-post-by-ken-regan.html">Bobby Fischer's exploits</a> and well before computers played a decent game. Fischer isn't mentioned in the Netflix series, the main character Beth Harmon sort of plays his role. The games themselves, created by Gary Kasparov and others, are even a joy to watch. Check out <a href="https://www.youtube.com/watch?v=oIMaTKOZG-8">this analysis</a> of the final game (spoiler warning). </p><p>The New York Times <a href="https://www.nytimes.com/2012/04/22/crosswords/chess/chess-50-years-of-new-york-times-columns.html">started a chess column</a> in 1962 and ran its <a href="https://www.nytimes.com/2014/10/12/crosswords/chess/after-rocky-start-grand-prix-finds-a-favorite-in-the-lead.html">last column</a> in 2014, though that might be saying more about the state of newspapers than the state of chess.</p><p>What about the computers? They have just gotten so good and with <a href="https://blog.computationalcomplexity.org/2017/12/our-ai-future-good-and-ugly.html">AlphaZero</a> mastering the game with just machine learning on top of the rules of chess, it's not even fun to watch computer versus computer anymore. Now we're back to watching humans and getting back into the games ourselves.</p><p>Computers have opened the door to cheating. Complexity theorist Ken Regan has a <a href="http://www.buffalo.edu/news/experts/ken-regan-faculty-expert-chess.html">side gig</a> reviewing games to determine if a player punching above their weight secretly used a computer algorithm. </p><p>Microsoft just <a href="https://www.microsoft.com/en-us/research/blog/the-human-side-of-ai-for-chess/">announced</a> chess programs that play as a human at various levels of strength. I suppose someone could use a program like this to cheat in a way that even Ken couldn't detect. But mostly it would be like Googling in pub trivia--just takes the fun out of the game.</p>https://blog.computationalcomplexity.org/2020/12/chess-is-back.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-1036999202735486243Mon, 30 Nov 2020 04:36:00 +00002020-11-29T22:36:59.414-06:00James Randi, Magicians-Author-Skeptic, passed away at the age of 92<p><br /></p><p>James The Amazing Randi died on October 20, 2020, at the age of 92. He is survived by</p><p>his husband Jose Alvarez. His Wikipedia page is <a href=" https://en.wikipedia.org/wiki/James_Randi">here</a></p><div> </div><div>A few Randi Points:</div><div><br /></div><div><div><br /></div><div>0) Wikipedia lists his careers as Magician, Author, Skeptic. I didn't know that skeptic was a career.</div><div><br /></div><div>1) Randi debunked many paranormal claims, though he did not like the term <i>debunke</i>r. He preferred <i>investigator</i>.</div><div><br /></div><div>2) Martin Gardner and James Randi founded the</div><div><br /></div><div><i>Committee for Scientific Investigation of Claims of the Paranormal.</i></div><div><br /></div><div>which publishes</div><div><br /></div><div><i>The Skeptical Inquirer</i>: see <a href="https://skepticalinquirer.org/?gclid=Cj0KCQjwuL_8BRCXARIsAGiC51AlnsnROpbKH-O1K-3WoumIXHGLAACCVDxByb2lFy0rkKunUHblUOAaAmUmEALw_wcB">here</a> </div></div><div><br /></div><div><div><br /></div><div>3) The internet is both a place where unchecked claims of paranormal activity (and more dangerous lies) can grow faster than in an earlier time, but also a place where magazines like The Skeptical Inquirer, and fact-checking websites, can help check the unchecked claims. What is winning? I leave that as an exercise for the reader. </div><div><br /></div><div>4) I suspect most (all?) people reading this blog do not believe in astrology, UFO's, ESP, or other crank theories. Hence I was surprised to read that Alan Turing thought the evidence for ESP was <i>overwhelming. </i>This was mentioned in passing in his paper on The Turing Test (called there <i>The</i> <i>Imitation Game</i>) as something the Turing Test will have to account for. I've tried to find out why he believed this, without success. Some websites mentioned that belief in the paranormal was more... normal in those days. One suggested that after the counter-intuitive theories of quantum mechanics and relatively were out there, other counter-intuitive theories took hold, like ESP. Even so, what was the evidence he was referring to?</div><div><br /></div><div>5) Claims that<i> I was abducted by a UFO</i> or <i>I saw a UFO</i> have decreased since people now have cell phones so ALWAYS have a way to take pictures. Also rumors like (I had heard this one)</div><div><br /></div><div><i>There is an alternative ending to the movie BLAH which made is way to a few DVDs by mistake.</i></div><div><br /></div><div>are no longer made since IF true you could EASILY produce evidence of such (post to you tube or elsewhere).</div><div><br /></div><div>6) The term<i> skeptic</i> just means someone who doubts something, and is not necc a positive things.</div><div><br /></div><div><i>I am a skeptic when it comes go Global Warming</i></div><div><br /></div><div>being one example.</div></div><div><br /></div><div><div>Randi largely debunked things that were obviously false and not-political. (That the very existence of Global Warming is political is appalling. At some future point the question of whether or not we ever got to the moon will be political: Something done by big government that worked is impossible, hence it did not happen. See Scott's Blog on disbelief that we ever went to the moon <a href="https://www.scottaaronson.com/blog/?p=4267">here</a>. And people like Randi will need to debunk the notion that the moon landing was faked.) </div><div><br /></div><div>7) Back to Turing- There is a large diff between believing in ESP and believing in astrology.</div><div><br /></div><div>For ESP Turing mentioned <i>overwhelming evidence. </i> While he was WRONG, he did see the need to HAVE evidence. And note that ESP CAN be tested and found to NOT be true. Also note that it is plausible (though I really doubt it) that some humans somehow have some level of ESP. Astrology has NO redeeming value or hope whatsoever. (I am reminded that in Martin Gardner's book <i>Fads and Fallacies in the name of science </i>he noted that most people would say things like `YES, I liked your debunking of A, but you are wrong about B--- B is for real!')</div><div><br /></div><div>UFO's: I do not believe that aliens have come here and abducted people or left crop circles or anything of the sort. The intelligent question of <i>is there intelligent life in the universe </i>is quite another matter.</div><div><br /></div><div>7) When I saw magicians as a kid (1960's) I knew that it was all tricks- though very skillful tricks which were impressive. Sometimes they would indicate that it was <i>real magic </i>but I did not know what they meant. Since then I have learned that in an earlier time it was common that magicians claimed they used <i>real magic</i>. I still don't quite know what that means, which is just as well since it does not exist.</div><div><br /></div><div>8) Randi has been sued by people whose tricks he has debunked. Randi seems to have always won. I say <i>seems to </i> since legal cases are not as clear cut as mathematics. I also looked up Uri Geller. He has sued A LOT of people, and not just people who deny his claims. Thinks like using his likeness without permission (he may have a point there). Very hard to tell how he is doing on balance.</div><div><br /></div><div>9) According to Wikipedia Randi dropped out of High School. I assume he learned A LOT on his own.</div><div><br /></div><div>(Trivia-- who was the last president who did not have a college degree? I will answer at the end.)</div><div><br /></div><div>10) This seems like a paradox... or something (quoted from Wikipedia):</div></div><div><br /></div><div><div>BEGIN</div><div><br /></div><div>Randi has been accused of actually using <i>psychic powers</i> to perform acts such as spoon bending. According to James Alcock, at a meeting where Randi was duplicating the performances of Uri Geller, a professor from the University at Buffalo shouted out that Randi was a fraud. Randi said: "<i>Yes, indeed</i>, <i>I'm a trickste</i>r, <i>I'm a cheat, I'm a charlatan, that's what I do for a living. Everything I've done here was by trickery</i>. The professor shouted back:</div><div><br /></div><div><i>That's not what I mean. You're a fraud because you're pretending to do these things through trickery, but you're actually using psychic powers and misleading us by not admitting it.</i></div><div><br /></div><div>A similar event involved Senator Claiborne Pell, a confirmed believer in psychic phenomena. When Randi personally demonstrated to Pell that he could reveal—by simple trickery—a concealed drawing that had been secretly made by the senator, Pell refused to believe that it was a trick, saying: "<i>I think</i> <i>Randi may be a </i><i>psychic and doesn't realize it</i>." Randi consistently denied having any paranormal powers or abilities.</div><div><br /></div><div>END</div><div><br /></div><div>Reminds me of <a href="https://blog.computationalcomplexity.org/2013/06/fraud-or-not.html">this</a> blog entry where I speculate about someone who codes up a great new classical factoring algorithm and claims he has a quantum computer, or someone who has a working quantum computer and claims its a great new classical factoring algorithm. </div><div><br /></div><div><br /></div><div>11) The last president who did not have a college degree: Harry Truman.</div></div><div><br /></div><div><br /></div><div><br /></div>https://blog.computationalcomplexity.org/2020/11/james-randi-magicians-author-skeptic.htmlnoreply@blogger.com (gasarch)11tag:blogger.com,1999:blog-3722233.post-876463840143291851Sun, 22 Nov 2020 21:19:00 +00002020-11-27T18:35:53.841-06:00Fun with birthdays, inspired by Nov 20<p> On Nov 20, 2020 the Google Doodle was of Benoit Mandelbrot for his 96th birthday. Why have a Doodle on his 96th bday? Anyway, the Doodle is <a href="https://www.google.com/doodles/benoit-mandelbrots-96th-birthday">here</a>. </p><p>On Nov 20, 2020 I read that Joe Biden turned 78. Why no Google Doodle of him? Maybe when he's 96. </p><p>This got me thinking of who else might have a Nov 20 birthday. I found the following (`found' is not quite right as I will explain later).</p><p>In order of age. </p><p>Benoit Mandelbrot: Dead at 85, would have been 96</p><p>Bobby Kennedy: Dead at 43, would have been 95.</p><p>Sergei Novikov: 82 years old. (Won Fields Medal in 1970 and did work on Solitons)</p><p>Dick Smothers: 80 years old (Tommy Smothers is not his twin, Tommy is 3 years older) </p><p>Joe Biden, 78 years old (in most crowds he would be an old-timer, but in this crowd he is the baby of the bunch- though there is a reason for that as you will see later)</p><p>There are more Nov 20 famous people (famous to someone- I have not heard of most of them) <a href="https://www.famousbirthdays.com/november20.html">here</a></p><p>Some thoughts on all of this trivia</p><p>1) I keep a list of famous (to me) people over 80 (though if I look someone up who is not quite 80 I may put him on the list anyway, as is the case for Biden and Trump) so if they die I won't be one of those people saying `<i>I thought they were already dead</i>'. I then began putting people on it who were already dead so I could find matching bdays. Hence it was easy to find Nov 20 birthdays of people over 80, and one under. </p><p>2) Mandelbrot is more famous than Novikov since Mandelbrot has those pretty pictures. This is not a criticism of his work. Is it possible to make people who do hard and abstract math more in the public eye? Probably not. </p><p>3) There is an awesome song about the Mandelbrot set (though some of the comments on the you tube video say its the Julia Set, but HEY- if they have math in a song, I am happy and don't get too fussy about how accurate it is- though I would understand if Julia fans are annoyed). The song is <a href="https://www.youtube.com/watch?v=lIlwFpz9s_I">here</a>. It has 464 likes and 41 dislikes. That always puzzled me- why does it have <i>any</i> dislikes? I've seen really awesome songs still have some dislikes. Well, as Rick Nelson sings in Garden Party (see <a href="https://www.youtube.com/watch?v=uAHR7_VZdRw">here</a>) ,<i>you</i> <i>can't please everyone, so you got to please yourself.</i> He got 25,000 likes and 702 dislikes. An awesome ratio, but why are there any dislikes? </p><p>4) I don't think Novikov will have a song about his work anytime soon.</p><p>5) Joe Biden has had some novelty songs about him in the past, and will do have more in the future once he is the Whitehouse. (Is the statement `Joe Biden is the president-elect' biased?)</p><p>6) I like the variety of the Nov 20 birthdays: two math, two politics, one entertainment. </p><p>7) I originally thought Nov 20 is NOT special and that most days would have around 5 bdays in my files. but actually no- I did a spot check of Nov 21,22,23,24,25,26,27,28,29,30 and they are all either 0,1, or 2 bdays. Prob not significant since this is just my small file. OR people avoid having babies close to thanksgiving (not sure of that one, but people DO avoid Feb 29 and Dec 25). </p><p>8) Of more interest are people born the same DAY and YEAR. I have a few of those, but I will point out one relevant to our field:</p><p>Albert Meyer and Art Garfunkel are same DAY and same YEAR.</p><p>(ADDED LATER: Art Garfunekl got a BA in Art History and then an MA in Math Eduacation)</p><p>Most famous SAME DAY and SAME YEAR of all time? I would guess</p><p>Abe Lincoln and Charles Darwin. <br /><br /></p><p>Second place</p><p> Margaret Thatcher and Lenny Bruce.</p><p> (I really doubt that's second place) </p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2020/11/fun-with-birthdays-inspired-by-nov-20.htmlnoreply@blogger.com (gasarch)5tag:blogger.com,1999:blog-3722233.post-6939903186223741314Thu, 19 Nov 2020 16:56:00 +00002020-11-19T11:01:25.120-06:00Vaughan Jones and Kaikoura<p><a href="https://en.wikipedia.org/wiki/Vaughan_Jones">Vaughan Jones</a>, one of the greatest mathematicians from New Zealand, passed away on September 6 at 67. Jones is an expert in knot theory among other areas and received the Fields Medal in 1990.</p><p>The <a href="https://en.wikipedia.org/wiki/Jones_polynomial">Jones polynomial</a> captures information about knots. Vaughan Jones himself co-authored a <a href="https://arxiv.org/abs/quant-ph/0511096">paper</a> on a polynomial-time quantum algorithm for approximating the Jones polynomial, one of the few natural problems outside of factoring that has an exponential improvement with a quantum algorithm. </p><p>From his Vanderbilt <a href="https://news.vanderbilt.edu/2020/09/09/vaughan-jones-preeminent-vanderbilt-mathematician-has-died/">obituary</a></p><blockquote><p>One way he worked to improve the field of mathematics in his native country was to organize a “summer school” in January each year and attract leading mathematicians from around the world to give lectures and interact with local students and professional mathematicians at a variety of beautiful locations around New Zealand. Out of this activity grew the New Zealand Mathematics Research Institute, which he co-founded and then led from the mid-1990s to this year.</p></blockquote><p>I had the pleasure of teaching in one of those summer schools in January 2000 in Kaikoura on the South Island. In between the whale watching, mountain hiking, <a href="https://blog.computationalcomplexity.org/2008/09/jogging-on-trips.html">jogging</a>, gorging on mussels, and Maori ceremonies, the NZMRI summer school <a href="https://www.google.com/books/edition/Aspects_of_Complexity/XlB_JTR0sV8C">Aspects of Complexity</a> had short courses to a mix of students and researchers in complexity and logic. I gave some <a href="https://lance.fortnow.com/papers/files/kaikoura.pdf">lectures</a> on Kolmogorov complexity that preceded a study of algorithmic randomness in the logic community. Other speakers included Eric Allender on basic complexity, Felipe Cucker on real computation, Mike Fellows on parameterized complexity, and Dominic Welsh on counting complexity. </p><p>It took me 36 hours door-to-door to get to Kaikoura but definitely worth it. Thanks to Vaughan Jones, for his research, his polynomial and creating a summer school that gave me that one perfect week in New Zealand.</p>https://blog.computationalcomplexity.org/2020/11/vaughan-jones-and-kaikoura.htmlnoreply@blogger.com (Lance Fortnow)0