tag:blogger.com,1999:blog-3722233Sat, 31 Oct 2020 08:42:59 +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)Blogger2789125tag:blogger.com,1999:blog-3722233.post-6849296165197348032Wed, 28 Oct 2020 22:27:00 +00002020-10-28T17:27:25.784-05:002020 Fall Jobs PostMy annual fall jobs posts, giving advice to PhDs looking for faculty positions, were getting repetitive. See <a href="https://blog.computationalcomplexity.org/2019/10/2019-fall-jobs-post.html">last year's post</a> for the usual stuff and feel free to post opportunities in the comments on this post. This year let's talk about what's changed.<div><br /></div><div>First something you might have missed--the latest <a href="https://cra.org/wp-content/uploads/2020/05/2019-Taulbee-Survey.pdf">Taulbee Survey</a> shows a small drop in the number of new undergraduate CS majors in 2019 after years of massive growth. Is it a simple blip or have we hit the saturation point? We may never know because of the change you definitely didn't miss seeing.</div><div><br /></div><div>So let's talk about the effect of COVID. We're seeing a large drop in new international students who are having a hard time getting visas or just avoiding the US like the plague (literally). Not sure those numbers will fully come back given other alternatives and a changing international relationship particularly with China. Many undergrads have delayed college and some may never attend. </div><div><br /></div><div>On the other hand, COVID has accelerated digitizing the economy, from videoconferencing to in-home entertainment and games to remote access to work environments. The post-COVID economy could create even a larger demand for computer scientists. </div><div><br /></div><div>Many universities curtailed hiring last year worried and may do so in the spring given the uncertain budget situation due to the virus. Others continue to hire in computing, some to make up for last year. I just can't make a prediction for the upcoming year but I wouldn't rush to the job market if you have the option to wait. Last year the CRA reinstated the <a href="https://cifellows2020.org/">CIFellows</a>, postdocs to help those in a tight job market, and may do so again next year. The CRA will also repeat its <a href="https://cra.org/cras-cv-database-initiative-turns-two/">CV database</a>.</div><div><br /></div><div>Late spring interviews in 2020 went virtual and will likely go virtual again in 2021. Nevertheless take the zoom meetings seriously. Make sure your interview talk is still a discussion--answer questions people give in the chat. Still do your research to have strong conversations with everyone you talk to, especially the non-theorists. And still dress nicely, at least from the waist up. Putting on a sports coat is not a bad idea. </div><div><div><br /></div><div>Though most places continue to focus on data science/ML, cybersecurity and to some degree quantum, Rutgers is <a href="https://www.cs.rutgers.edu/about/employment/details/tenure-track-assistant-professor-position-2">specifically looking</a> for a hire in computational complexity. Don't see that everyday. </div></div>https://blog.computationalcomplexity.org/2020/10/2020-fall-jobs-post.htmlnoreply@blogger.com (Lance Fortnow)4tag:blogger.com,1999:blog-3722233.post-9110359134467856278Sun, 25 Oct 2020 20:36:00 +00002020-10-26T13:13:27.170-05:00Do not become obsessed with the Polls unless...I know someone who checks the polls 3 times a day to see who looks like they will be elected prez. She cares A LOT about the election. It is irrelevant to this post who she supports. <div><br /></div><div>I've asked her `if you find out that, say, Biden is up 8 points instead of 9 in Penn. or that Georgia is looking pretty safe for Trump, or that Texas is in play (really?) how will that change your life? What will YOU do differently?'</div><div><br /></div><div>She had no answer. Unfortunately she is still a poll-watcher (I know that means something else usually, but you know what I mean.)</div><div><br /></div><div>So who should be poll-watching or poll-obsessing?</div><div><br /></div><div>1) To be fair to my friend, she might decide to GIVE MORE to her candidate if the polls are saying that he will lose (whoops- by saying `he' I gave away that her candidate is NOT Jo Jorgenson- Libertarian). I doubt my friend could say to the campaign `I want to you to spend it in state X since I read that its close there' (I read that some big donors in 2016 demanded more say in where the money was spend. I doubt that's a good idea since I suspect the party knows more about how to best spend the money then the donor does.) </div><div><br /></div><div>2) The Biden and the Trump Campaigns SHOULD be poll-watching to decide where to put their efforts. And I suspect they are doing just that.</div><div><br /></div><div>3) A really big donor (my friend is not one of those) MIGHT want to poll watch to decide if the candidate they want needs money. (I wonder if EITHER candidate needs money since they get so much free media.)</div><div><br /></div><div>4) Nate Silver-being a poll-watcher is kind-of his job. And of course writing columns about them and making predictions based on what he sees. My friend is not Nate Silver. </div><div><br /></div><div>5) Other people who have Nate Silver's job. I can't name any- is Nate Silver the most famous... Gee, not sure what job title he has... SO this is now two questions: What is his job title, call it X, and is he the most famous person who does X?</div><div><br /></div><div><br /></div><div>SO- my point- DO NOT be a poll-obsessive unless the information you get will lead to an action you can take. And I suspect that mostly it does not. </div><div><br /></div><div>The primaries are different: If a poll says A can beat X but B cannot beat X, that might guide who you vote for. </div><div><br /></div><div>Misc thought: </div><div><br /></div><div> I've heard the phrase `democratic pollster' and `republican pollster' These terms do not make sense. Would I call myself a `democratic Muffin Mathematician' ? My political leanings do not affect my search for truth about mathematical Muffins. Similarly, one would think that a pollster wants to find the TRUTH, even if its bad news for their employer, ESPECIALLY if its bad news for their employer, so they can help their employer fix it. The phrase `pollster employed by the X party' would make more sense-- however, whenever they are on TV they seem to always say that their candidate is doing well, even when they are not. </div><div><br /></div><div>ADDED LATER: Lance had a great tweet about this post: <i>do not obsess about polls, but DO obsess bout prediction markets. </i>I think in the past prediction markets have been better predictors but some group-think has set in so its no longer clear. (I could be wrong- but thats why I have heard.) </div>https://blog.computationalcomplexity.org/2020/10/do-not-become-obsessed-with-polls-unless.htmlnoreply@blogger.com (gasarch)4tag:blogger.com,1999:blog-3722233.post-6623846086903606036Mon, 19 Oct 2020 15:55:00 +00002020-10-19T10:55:58.203-05:00 Nature vs Nurture close to my birthday<p> Since I was born on Oct 1, 1960 (that's not true---if I posted my real birthday I might get my identity stolen), I will do a nature vs nurture post based on my life, which seems less likely to offend then doing it on someone else's life. I'll just rattle off some random points on Nature vs Nurture.</p><p>1) Is it plausible that I was born with some math talent? Is plausible that I was born with some talent to understand the polynomial van der Warden theorem? What is the granularity of nature-given or nurture-given abilities?</p><p>2) My dad was a HS English teacher and later Vice-Principal. My mom taught English at a Community college. Readers of the blog might think, given my spelling and grammar, that I was switched at birth. My mom says (jokingly?) that I was switched at birth since she thinks I am good at math.</p><p>a) I am not THAT good at math. Also see next point.</p><p>b) While there are some math families, there are not many. See my post <a href="https://blog.computationalcomplexity.org/2009/02/baseball-families-and-math-families.html">here</a>.</p><p>c) I think being raised in an intellectual atmosphere by two EDUCATORS who had the money to send me to college and allowed me the freedom to study what I wanted to is far more important than the rather incidental matter of what field I studied.</p><p>d) Since my parents never went into math or the sciences it is very hard to tell if they were `good at math' or even what that means.</p><p>3) There were early signs I was INTERESTED in math, though not that I was good at it.</p><p>a) In fourth grade I wanted to know how many SECONDS were in a century so I spend some time figuring it out on paper. Did I get the right answer? I forgot about leap years.</p><p>b) I was either a beneficiary of, or a victim of, THE NEW MATH. So I learned about comm. and assoc. operations in 8th grade. We were asked to come up with our own operations. I wanted to come up with an operation that was comm. but not assoc. I did! Today I would write it as f(x,y) = |x-y|. This is the earliest I can think of where I made up a nice math problem. Might have been the last time I made up a nice math problem AND solved it without help. </p><p>c) In 10th grade I took some Martin Gardner books out of the library. The first theorem I learned not-in-school was that a graph is Eulerian iff every vertex has even degree. I read the chapter on Soma cubes and bought a set. (Soma cubes are explained <a href="https://en.wikipedia.org/wiki/Soma_cube">here</a>.) </p><p>d) I had a talent (nature?) at Soma Cubes. I did every puzzle in the book in a week, diagrammed them, and even understood (on some level) the proofs that some could not be done. Oddly I am NOT good at 3-dim geom. Or even 2-dim geom. For 1-dim I hold my own!</p><p>e) Throughout my childhood I noticed odd logic and odd math things that were said: </p><p>``Here at WCOZ (a radio station) we have an AXIOM, that's like a saying man, that weekends should be SEVEN DAYS LONG'' (Unless that axiom resolves CH, I don't think it should be assumed.) </p><p>``To PROVE we have the lowest prices in town we will give you a free camera!'' (how does that prove anything?) </p><p>``This margarine tastes JUST LIKE BUTTER'' (Okay-- so why not just buy butter?)</p><p>e) In 9th grade when I learned the quadratic formula I re-derived it once-a-month since I though it was important that one can prove such things. I heard (not sure from where) that there was no 5th degree equation. At that very moment I told my parents:</p><p><i>I am going to major in math so I can find out why there is no 5th degree equation.</i></p><p>There are worse things for parents to hear from their children. See <a href="https://blog.computationalcomplexity.org/2019/06/a-proof-that-227-pi-0-and-more.html">here</a> for dad's reaction. </p><p>f) When I learned that the earth's orbit around the sun is an ellipse and that the earth was one of the foci, I wondered where the other foci is and if its important. I still wonder about this one. Google has not helped me here, though perhaps I have not phrased the question properly. If you know the answer please leave a comment. </p><p>g) I also thought about The Ketchup problem and other problems, that I won't go into since I already blogged about them <a href="https://blog.computationalcomplexity.org/2012/06/ketchup-problem.html">here</a></p><p>4) I was on the math team in high school, but wasn't very good at it. I WAS good at making up math team problems. I am now on the committee that makes up the Univ of MD HS math competition. I am still not good at solving the problems but good at making them up. </p><p>5) From 9th grade on before I would study for an exam by making up what I thought would be a good exam and doing that. Often my exam was a better test of knowledge than the exam given. In college I helped people in Math and Physics by making up exams for them to work on as practice. </p><p>6) I was good at reading, understanding, and explaining papers. </p><p>7) I was never shy about asking for help. My curiosity exeeded by ego... by a lot!</p><p>8) Note that items 5,6, and 7 above do not mention SOLVING problems. The papers I have written are of three (overlapping) types:</p><p>a) I come up with the problem, make some inroads on it based on knowledge, and then have people cleverer (this is often) or with more knowledge (this is rarer) help me solve the problems.</p><p>b) I come up with the problem, and combine two things I know from other papers to solve it. </p><p>c) Someone else asks for my help on something and I have the knowledge needed. I can only recall one time where this lead to a paper. </p><p>NOTE- I do not think I have ever had a clever or new technique. CAVEAT: the diff between combining known knowledge in new ways and having a clever or new technique is murky. </p><p>8) Over time these strengths and weaknesses have gotten more extreme. It has become a self-fulfilling prophecy where I spend A LOT of time making up problems without asking for help, but when I am trying to solve a problem I early on ask for help. Earlier than I should? Hard to know. </p><p>9) One aspect is `how good am I at math' But a diff angle is that I like to work on things that I KNOW are going to work out, so reading an article is better than trying to create new work. This could be a psychological thing. But is that nature or nurture? </p><p>10) Could I be a better problem solver? Probably. Could I be a MUCH better problem solver? NO. Could I have been a better problem solver I did more work on that angle when I was younger? Who knows? </p><p>11) Back to the Quintic: I had the following thought in ninth grade, though I could not possibly have expressed it: The question of, given a problem, how hard is it, upper and lower bounds, is a fundamental one that is worth a lifetime of study. As such my interest in complexity theory and recursion theory goes back to ninth grade or even further. My interest in Ramsey Theory for its own sake (and not in the service of complexity theory) is much more recent and does not quite fit into my narrative. But HEY- real life does not have as well defined narratives as fiction does. </p><p>12) Timing and Luck: IF I had been in grad student at a slight diff time I can imagine doing work on algorithmic Galois theory. <a href="https://singer.math.ncsu.edu/Algorithmic_slides.pdf">Here</a> is a talk on Algorithmic Galois theory. Note that one of the earliest results is by Landau and Miller from 1985---I had a course from Miller on Alg. Group Theory in 1982. This is NOT a wistful `What might have been' thought. Maybe I would have sucked at it, so its just as well I ended up doing recursion theory, then Ramsey theory, then recursion-theoretic Ramsey Theory, then muffins. </p><p><br /></p><p><br /></p><div><br /></div>https://blog.computationalcomplexity.org/2020/10/nature-vs-nurture-close-to-my-birthday.htmlnoreply@blogger.com (gasarch)4tag:blogger.com,1999:blog-3722233.post-4895611208507130576Thu, 15 Oct 2020 13:00:00 +00002020-10-15T08:00:42.372-05:0050 Years of PBS<p>The Public Broadcasting Service (PBS) launched fifty years ago this month in the United States. The New York Times talks about its <a href="https://www.nytimes.com/2020/10/13/arts/television/pbs-50-anniversary.html">fifty reasons</a> how the network mattered. I'll throw in my thoughts.</p><p>I was just slightly too old for shows like Sesame Street, Electric Company, Mr. Rogers and Zoom, not that that stopped me from watching them. My kids grew up on Barney and Friends. My daughter even had a toy Barney that interacted with the show, which went <a href="https://blog.computationalcomplexity.org/2012/02/barney-evil-dinosaur.html">as well as you'd expect</a>. </p><p>PBS introduced me to those great British TV shows for young nerds like me including Monty Python and Doctor Who. I wasn't into Nova but did watch Carl Sagan's Cosmos religiously in high school.</p><p>My favorite PBS show was the American Experience, short documentaries about US culture. I remember learning about this history of Coney Island and the quiz show scandals before Robert Redford made a movie about it.</p><p>Siskel and Ebert got their start on PBS and became my go to source for movie reviews.</p><p>In 1987 PBS broadcasted Ivy League football games. One Saturday I sat down expecting to watch my alma mater and instead got supreme court hearings. Only on PBS could Cornell football get Borked.</p>https://blog.computationalcomplexity.org/2020/10/50-years-of-pbs.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-6616178737091923837Mon, 12 Oct 2020 17:49:00 +00002020-10-13T10:44:46.508-05:00Hugh Woodin, Kurt Godel, Dwayne `The Rock' Johnson, Robert De Niro, David Frum, Tom Selleck: Do I care what they think? Should I?<p> MATH:</p><p>My last <a href="https://blog.computationalcomplexity.org/2020/10/revisiting-continuum-hypothesis.html">post</a> on CH mentioned that Hugh Woodin used to think NOT(CH) but now thinks CH. In both cases his reasons have some math content to them. Also, note that Hugh Woodin seems to believe that CH somehow HAS an answer. Kurt Godel also thought CH HAS an answer. It has been said that he could have announced his result that CH is consistent by saying L is THE model, and the problem is now solved. </p><p>Should we care what Hugh Woodin and Kurt Godel think about CH?</p><p>YES- they have both studied the issue A LOT. If you think CH should have an answer, then surely you would care what they think. </p><p>NO- CH has no answer so there opinions are no better than mine. If you think CH does not have an answer then you might think this; however, I think you should still be at least INTERESTED in what people who have thought about the problem A LOT have to say, even if you will disagree with them.</p><p>But with MATH there are people who clearly know more than you on topics you care about, so it is worth hearing what they have to say. </p><p>POLITICS:</p><p>Recently Dwayne THE ROCK Johnson (by Wikipedia: actor, producer, businessman, and former professional wrestler) ENDORSED Joe Biden. Should we care about his opinion? Maybe, if wrestling fans and former pro wrestler tend to be Republicans, so this may indicate a shift. I do not know if this is the case. </p><p>Robert De Niro was in favor of impeaching Donald Trump. He also said that Trump was like a Gangster. He would know because he was in the movie GOODFELLOWS and later THE IRISHMAN (about Jimmy Hoffa). To be fair I do not think he said that is how he would know. Even so, I don't think I care what he thinks, unless he has some specialized knowledge I do not know about. </p><p>David Frum is a republican who had a break with the party NOT over Donald Trump, but over Obamacare- which you may recall was originally a CONSERVATIVE response to Hillarycare by the Heritage Foundation. He has a good article on this <a href="https://www.theatlantic.com/politics/archive/2017/03/the-republican-waterloo/520833/">here</a>. Because he is an intelligent republican in favor of Obamacare (or some version of it) he is worth listening to.</p><p>In POLITICS its trickier- who is worth listening to and why. For all I know, THE ROCK has made a detailed study of the Republican and Democratic platforms (actually this cannot be true since the Republicans did not have a platform this time). </p><p>COMMERCIALS:</p><p>Tom Selleck (Actor-Magnum PI a while back, Blue Bloods now) does commercials for reverse mortgages. A while back I asked a group of people WHY he is doing them. Here were some answers and reactions</p><p>a) He needs the money. Not likely, he seems to have done well and does not seem to have the kind of bad habits (e.g., drugs) that need money. Maybe he has expensive tastes (my only expensive tastes is in fine European Kit Kat bars--- which actually are not that expensive). </p><p>b) He likes doing commercials. Maybe.</p><p>c) He believes in the product. At this, everyone cracked up in laughter.</p><p>This raises a more general point: Why does ANYONE believe ANY commercial since we KNOW the actor is being PAID to say it. I ask non rhetorically as always. </p>https://blog.computationalcomplexity.org/2020/10/hugh-woodin-kurt-godel-dwayne-rock.htmlnoreply@blogger.com (gasarch)9tag:blogger.com,1999:blog-3722233.post-7346788885933681031Thu, 08 Oct 2020 13:52:00 +00002020-10-08T10:28:20.389-05:00Revisiting the Continuum Hypothesis<p>I have been thinking about CH lately for two reasons</p><p>1) I reread the article</p><p>Hilbert's First Problem: The Continuum Hypothesis by Donald Martin from <b>Proceedings of Symposia </b> i<b>n Pure Mathematics: Mathematical developments arising from Hilbert Problems</b>. 1976. (For a book review of the symposia and, <b>The Honor Class</b>, also about Hilbert's problems, see <a href="https://www.cs.umd.edu/users/gasarch/bookrev/44-4.pdf">here</a>.)</p><p>The article takes the point of view that CH CAN have an answer. He discusses large cardinals (why assuming they exist is plausible, but alas, that assumption does not seem to resolve CH) and Projective Det. (why assuming it is true is plausible, but alas, that assumption does not seem to resolve CH).</p><p>(A set A \subseteq {0,1}^omega is DETERMINED if either Alice or Bob has a winning strategy in the following non-fun game: they alternate picking bits a_1, b_1, a_2, b_2, ... with Alice going first. If a_1 b_1 a_2 b_2... IS IN A then Alice wins, IF NOT then Bob wins. Martin showed that all Borel sets are determined. Proj Det is the statement that all projections of Borel sets are determined. AD is the axiom that ALL sets A are determined. It contradicts AC.)</p><p>But what really inspired this post is the last paragraph:</p><p><i>Throughout the latter part of my discussion, I have been assuming a naive and uncritical attitude towards CH. While this <b>is</b> in fact my attitude, I by no means wish to dismiss the opposite viewpoint. Those that argue that the concept of set is not sufficiently clear to fix the truth-value of CH have a position that is at present difficult to assail. As long as no new axiom is found which decides CH, their case will continue to grow stronger, and our assertions that the meaning of CH is clear will sound more and more empty.</i></p><p>2) Scott Aaronson mentioned in a blog post (see <a href="https://www.scottaaronson.com/blog/?p=4962">here</a>) that he has read and understood the proof that CH is independent of set theory.</p><p>SO, this seemed like a good time to revisit thoughts on CH.</p><p> I took a very short poll, just two people, about CH: Stephen Fenner (in a perfect world he would be a set theorists) and Scott Aaronson (having JUST read the proof that CH is ind. he has thought about it recently).</p><p>Here are some thoughts of theirs and mine</p><p>1) All three of us are Platonists with regard to the Naturals (I was surprised to find recently that there are people who are not!) but not with regard to the reals. So we would be OKAY with having CH have no answer.</p><p>2) All three of us agree that it would be nice if SOME axiom was both</p><p>a) Intuitively appealing or aesthetically appealing , and</p><p>b) resolved CH.</p><p>I always thought that (a) would be the hard part-- or at least getting everyone (not sure who we are talking about) to AGREE on a new axiom. But even getting an axiom to resolve CH seems hard. Large cardinals don't seem to do it, and various forms of Determinacy don't seem to do it.</p><p>Scott reminded me of Freiling's Axiom of Symmetry (see <a href="https://en.wikipedia.org/wiki/Freiling%27s_axiom_of_symmetry">here</a>) which IS intuitive and DOES resolve CH (its false) though there are problems with it--- a minor variant of it contradicts AC (I am QUITE FINE with that since AC implies Banach-Tarski which Darling says shows `Math is broken'.)</p><p>Stephen recalled some of Hugh Woodin's opinions of CH, but Hugh seems to have changed his mind from NOT(CH): 2^{aleph_0} = aleph_2, to CH: 2^{aleph_0} = aleph_1.(See <a href="https://www.jstor.org/stable/24569622?seq=1#metadata_info_tab_contents">here</a>.)</p><p>3) All three of would be okay with V=L, though note that this would put many set theorists out of work. All the math that applies to the real world would still be intact. I wonder if in an alternative history the reaction to Russell's paradox would be a formulation of set theory where V=L. We would KNOW that CH is true, KNOW that AC is true. We would know a lot about L but less about forcing.</p><p>4) Which Geometry is true: Euclidian, Riemannian, others? This is now regarded as a silly question: Right Tool, Right Job! If you build a bridge use Euclid. If you are doing astronomy use Riemann. Might Set Theory go the same way? It would be AWESOME if Scott Aaronson found some quantum thing where assuming 2^{aleph_0} = aleph_2 was the right way to model it.</p><p>5) If I was more plugged into the set theory community I might do a poll of set theorists, about CH. Actually, someone sort-of already has. Penelope Maddy has two excellent and readable articles where she studies what set theorists believe and why.</p><p><b>Believing The Axioms I</b>: <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms1.pdf">here</a></p><p><b>Believing The Axioms II</b>: <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms2.pdf">here</a></p><p>Those articles were written in 1988. I wonder if they need an update.</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/2020/10/revisiting-continuum-hypothesis.htmlnoreply@blogger.com (gasarch)3tag:blogger.com,1999:blog-3722233.post-2360146425812493374Mon, 05 Oct 2020 12:50:00 +00002020-10-05T07:50:35.714-05:00MIP* = RE ReduxEverything pre-covid seems at least five years ago to me, so it's hard to believe that <a href="https://arxiv.org/abs/2001.04383">MIP* = RE</a> is a 2020 result. To remind you, consider the model where we have two powerful provers put in separate rooms where they can't communicate (think suspects of a crime put in separate interrogation rooms). An computationally efficient verifier can ask them questions based on random coins. Thirty years ago, Laszlo Babai, Carsten Lund and myself <a href="https://doi.org/10.1007/BF01200056">showed</a> that every language in nondeterministic exponential time has proofs in this model.<div><br /></div><div>Now suppose the provers have entangled quantum bits. This question has a long history that culminates in the <a href="https://arxiv.org/abs/2001.04383">MIP* = RE paper</a> earlier this year by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen showing that every proof of any length can be proven in this model. Incredible!</div><div><br /></div><div>But wait, why is there a new version 2 dated last week? Turns out the MIP* = RE paper relied on a 2016 paper by Vidick which was later discovered to have a bug. No worries, as the authors of the MIP* = RE paper got around this issue by a <a href="https://arxiv.org/abs/2009.12982">quantum analysis</a> of a low-degree test from that old Babai-Fortnow-Lund paper.</div><div><br /></div><div>Vidick's <a href="https://mycqstate.wordpress.com/2020/09/29/it-happens-to-everyonebut-its-not-fun/">blog post</a> explains it all, including the angst of a major result falling apart temporarily. He has <a href="https://blog.computationalcomplexity.org/2017/01/babai-strikes-back.html">good</a> <a href="http://nautil.us/issue/24/error/how-maths-most-famous-proof-nearly-broke">company</a>. Glad it all worked out. </div>https://blog.computationalcomplexity.org/2020/10/mip-re-redux.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-9181146391897180370Mon, 28 Sep 2020 01:44:00 +00002020-09-29T13:33:05.494-05:00A Quote from Tesla which is very predictive in one way, and perhaps not in another way<p> Nikola Tesla, famous inventor, who lived 1856--1943 said the following:</p><p><br /></p><p>When wireless is perfectly applied the whole earth will be converted into</p><p>a huge brain, which in fact it is, all things being particles of a real</p><p>and rhythmic whole. We shall be able to communicate with one another</p><p>instantly, irrespective of distance. Not only this but through television</p><p>and telephony, we shall see and hear one another as perfectly as though</p><p>we were face to face, despite intervening distances of thousands of miles;</p><p>and the instruments through which we shall be able to do this will be</p><p>amazingly simple compared with our present telephone. A man will be able to</p><p>carry one in his vest pocket.</p><p><br /></p><p>The `vest pocket' at the end really impressed me.</p><p><br /></p><p>By `a man will be able to carry one...' I don't know if he mean all people or if he actually </p><p>meant that women would not need such a device. If that is what he meant then,</p><p>while high marks for tech-prediction, low marks for social-prediction. </p><p><br /></p><p>This quote is SO right-on for technology that I offer the following challenge: Find other quotes from year X that were very predictive for year X+Y for a reasonably large Y.</p><p>ADDED LATER: I will give two answers to my own challenge:</p><p>1) On the TV show THE HONEYMOONERS, in 1955, Ralph Cramden predicts 3-Dim TV. I blogged about that <a href="https://blog.computationalcomplexity.org/2010/05/ralph-kramden-your-wait-is-over-3d-tv_05.html#comment-form">here</a></p><p>2) Did the TV show Get Smart foreshadow cell phones. Maxwell Smart's shoe-phone was portable but wearing it on his foot seems odd. It also used dial, not touch tone. Mel Brooks (co-creator of the series) points out that in the Pilot episode Max is enjoying a show and his phone goes off so he has to leave and take the call -- which was very strange then but standard now. So the show did predict one of the problems with cell phones, if not cell phones themselves. </p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2020/09/a-quote-from-testla-which-is-very.htmlnoreply@blogger.com (gasarch)5tag:blogger.com,1999:blog-3722233.post-7113260074896603448Wed, 23 Sep 2020 21:33:00 +00002020-09-23T16:33:17.452-05:00Remembering 2000<p><a href="http://www.cs.cmu.edu/~FOCS2000/">FOCS 2000</a> took place in Redondo Beach, just south of Los Angeles, November 12-14. Certainly some great results such as the Reingold-Vadhan-Wigderson <a href="https://doi.org/10.1109/SFCS.2000.892006">Zig-Zag Graph Product Expander construction</a> that would lead to Omer Reingold's <a href="https://blog.computationalcomplexity.org/2014/02/favorite-theorems-connecting-in-log.html">Undirected Connectivity in Log Space</a>. Mostly though I remember the discussions about the presidential election held the week before and whether we might find out our next president during the conference. Spoiler alert: <a href="https://en.wikipedia.org/wiki/2000_United_States_presidential_election_recount_in_Florida">We didn't</a>. </p><p>Consider the following viewpoints for a person X</p><p>1. Did X support Bush or Gore?</p><p>2. Did X interpret the rules of the election that Bush won or Gore won?</p><p>These should be independent events. Your interpretation of the rules should not depend on who you supported. But in fact they were nearly perfectly correlated. Whether you were a politician, a newspaper editorial page writer, a supreme court justice, a computer scientist or pretty much everyone else, if you supported Gore, you believed he won the election and vice-versa. Everyone had their logic why they were right and I'm sure my readers who remember that election still believe their logic was correct. </p><p>As this upcoming election gets messy, as it already has, take care with trying to justify your desired endgame by choosing the logic that makes it work. Would you use the same logic if the candidates were reversed? Everyone says "yes" but it's rarely true. Just like Mitch McConnell, you'll just find some excuse why the opposite situation is different. Trust me, my logic is impeccable. </p>https://blog.computationalcomplexity.org/2020/09/remembering-2000.htmlnoreply@blogger.com (Lance Fortnow)4tag:blogger.com,1999:blog-3722233.post-3655236890828727429Sun, 20 Sep 2020 18:56:00 +00002020-09-21T12:07:45.150-05:00Baseball can go on forever, it doesn't just seem that way<p> Most games have some way to make sure they cannot go on forever.</p><p>1) Chess: I had thought there was a 50-move rule and a 3-times-same-position rule, but its a byte more complicated than that, see <a href="https://en.wikipedia.org/wiki/Draw_(chess)">here</a>. There is also a chess clock. Suffice to say, Chess can never on forever (though it may seem like it does). </p><p>2) NIM: Eventually all of the stones are gone. There may be more complicated versions where you can add some stones, but in those versions I suspect that there is some parameter that goes to 0.</p><p>3) Basketball, Football, Hockey, Soccer: These all have a clock so they are time limited. For overtime there are also rules that make sure the game cannot go on forever. Or maybe its just very rare: what if the Superb Owl (spelled that way to avoid lawsuits, see <a href="https://www.vox.com/the-goods/2019/1/31/18202037/super-bowl-53-ads-trademark-the-big-game-2019">here</a>) is tied 0-0 at the end of the four quarters and goes into overtime and... nobody scores... ever. Could the game go on forever or would the referees declare it a tie? In the regular season there are ties, but in the in the superb owl? Actually this may be more a problem in the playoffs since you need to determine who goes to the next round.</p><p>4) Take your favorite game. I would bet dollars to doughnuts (what an odd phrase---see <a href="https://en.wiktionary.org/wiki/bet_a_dollar_to_a_doughnut">here</a> for more about the phrase) that there is some mechanism to make sure the game ends. An exception that Darling pointed out to me: If in Gin Rummy both players are terrible then the game can go on forever. This is probably true for other games as well and actually makes the question into two questions (a) will a game terminate no matter what the players do, and (b) (not sure how to formalize) will a game terminate if both players are trying to win and are making reasonable moves.</p><p>You may have noticed that in item 3 I left out Baseball. There is no clock in baseball. So one way the game can go on forever is to have a tie and extra innings and nobody scores. I think the umpire has the authority to call it a tie. (Incidentally, the shortened baseball season has a new extra inning rule---each inning starts with a runner on second. See <a href="https://www.mlb.com/news/reasons-new-extra-innings-rule-is-good">here</a>,) When Lance read an earlier version of this post he pointed me to 5 ways a game can go on forever, not counting the example I have later in this post. <a href="https://cs.nyu.edu/~gottlieb/tr/back-issues/1990s/1992/1-jan-scanned.pdf">Here</a> is where Lance found the question and answer (look on the first page under Speed Department for the question, and the very end of the second page for the answer). I also did my own writuep with more details, see <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/baseballforever.pdf">here</a>. Also of interest (though not if you were actually at the game this happened), the record for number of times a player has a foul with 2 strikes is 16, see <a href="https://www.businessinsider.com/brandon-belts-record-at-bat-pop-fly-2018-4">here</a>. </p><p> However, I came across an example more obscure than any of those. </p><p>Here is what happened (and you can see the video of it <a href="https://www.youtube.com/watch?v=yDyCRTlKllk">here</a>, though it really starts about a minute into it. Keep reading- it looks like its another post, but its part of this post: </p><div class="q-box qu-borderBottom qu-px--medium qu-py--small" style="border-bottom-style: solid; border-color: rgb(222, 224, 225); border-width: 1px; box-sizing: border-box; color: #282829; direction: ltr; font-size: 15px; padding: 8px 16px;"><div class="q-flex qu-justifyContent--space-between" style="box-sizing: border-box; direction: ltr; display: flex; justify-content: space-between;"><div class="q-flex qu-alignItems--center" style="align-items: center; box-sizing: border-box; direction: ltr; display: flex;"><div class="q-text qu-fontSize--small qu-ml--small qu-color--gray" style="box-sizing: border-box; color: #636466; direction: ltr; font-size: 13px; margin-left: 8px;">From your Digest</div></div></div></div><div class="q-box" style="box-sizing: border-box; color: #282829; direction: ltr; font-size: 15px;"><div class="q-box" style="box-sizing: border-box; direction: ltr;"><div class="q-box qu-pt--medium qu-pb--tiny" style="box-sizing: border-box; direction: ltr; padding: 16px 16px 4px; position: relative;"><div class="q-box" style="box-sizing: border-box; direction: ltr;"><div class="q-box" style="box-sizing: border-box; direction: ltr;"><div class="q-box" style="box-sizing: border-box; direction: ltr;"><div class="q-box" style="box-sizing: border-box; direction: ltr;"><div class="q-flex" style="box-sizing: border-box; direction: ltr; display: flex;"><div class="q-box qu-mb--small qu-pr--large" style="box-sizing: border-box; direction: ltr; margin-bottom: 8px; padding-right: 24px; width: 546px;"><div class="q-box spacing_log_answer_header" style="box-sizing: border-box; direction: ltr;"><div class="q-flex" style="align-items: start; box-sizing: border-box; direction: ltr; display: flex; width: 522px;"><div class="q-inlineFlex qu-mr--small qu-alignItems--center" style="align-items: center; box-sizing: border-box; direction: ltr; display: inline-flex; margin-right: 8px;"><div class="q-box qu-display--inline-block" style="box-sizing: border-box; direction: ltr; display: inline-block;"><div class="q-box qu-display--inline-block" style="box-sizing: border-box; direction: ltr; display: inline-block;"><div class="q-relative qu-display--inline-block" style="box-sizing: border-box; direction: ltr; display: inline-block; position: relative;"><div aria-owns="POPOVER2" class="q-box qu-display--inline-block" style="box-sizing: border-box; direction: ltr; display: inline-block;"><a class="q-box qu-display--inline-flex qu-color--gray_dark qu-cursor--pointer qu-hover--textDecoration--underline" href="https://www.quora.com/profile/Zev-Steinhardt" style="-webkit-tap-highlight-color: rgba(255, 255, 255, 0.6); background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; color: #282829; cursor: pointer; direction: ltr; display: inline-flex; text-decoration-line: none; transition-duration: 180ms; transition-property: text-decoration; transition-timing-function: ease-in-out;" target="_blank"><div class="q-inlineFlex qu-flex--none" style="box-sizing: border-box; direction: ltr; display: inline-flex; flex: 0 0 auto; position: relative;"><div class="q-inlineFlex" style="box-sizing: border-box; direction: ltr; display: inline-flex; position: relative;"><div class="q-inlineFlex qu-overflow--hidden qu-borderRadius--circle qu-borderWidth--retinaOverride" style="border-radius: 100%; border-style: none; border-width: 2px; box-shadow: rgba(0, 0, 0, 0.1) 0px 0px 0px 0.5px; box-sizing: border-box; direction: ltr; display: inline-flex; overflow: hidden;"><div class="q-box qu-bg--white__ignore_dark_mode qu-borderRadius--circle" style="background-color: white; border-radius: 100%; bottom: 1px; box-sizing: border-box; direction: ltr; left: 1px; position: absolute; right: 1px; top: 1px;"></div><img class="q-image qu-display--block qu-size--36 qu-minWidth--36" src="https://qph.fs.quoracdn.net/main-thumb-138599745-200-pbrgkfnbxdzyttabmtnmavtcwavrcktv.jpeg" style="animation-duration: 0.001s; animation-name: insQ_100; border: 0px none; box-sizing: border-box; color: transparent; direction: ltr; display: block; height: 36px; max-width: 100%; min-width: 36px; position: relative; width: 36px;" /><div class="q-box qu-borderRadius--circle qu-borderAll Photo___StyledBox-sc-1x7c6d3-1 djSgZk" style="border-color: rgba(0, 0, 0, 0.06); border-radius: 100%; border-style: solid; border-width: 1px; bottom: 0px; box-sizing: border-box; direction: ltr; left: 0px; position: absolute; right: 0px; top: 0px; transition: all 150ms ease 0s;"></div></div></div></div></a></div></div></div></div></div><div class="q-box qu-flex--auto" style="box-sizing: border-box; direction: ltr; flex: 1 1 auto; margin-top: -1px; min-width: 0px; overflow-wrap: break-word;"><div class="q-flex qu-flexWrap--wrap" style="box-sizing: border-box; direction: ltr; display: flex; flex-wrap: wrap;"><div class="q-box" style="box-sizing: border-box; direction: ltr;"><div class="q-text qu-bold qu-color--gray_dark qu-fontSize--small qu-passColorToLinks" style="box-sizing: border-box; direction: ltr; font-size: 13px; font-weight: bold;"><div class="q-box qu-display--inline" style="box-sizing: border-box; direction: ltr; display: inline;"><div class="q-box qu-display--inline" style="box-sizing: border-box; direction: ltr; display: inline;"><div class="q-relative qu-display--inline" style="box-sizing: border-box; direction: ltr; display: inline; position: relative;"><div aria-owns="POPOVER3" class="q-box qu-display--inline" style="box-sizing: border-box; direction: ltr; display: inline;"><a class="q-box qu-color--gray_dark qu-cursor--pointer qu-hover--textDecoration--underline" href="https://www.quora.com/profile/Zev-Steinhardt" style="-webkit-tap-highlight-color: rgba(255, 255, 255, 0.6); background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; cursor: pointer; direction: ltr; text-decoration-line: none; transition-duration: 180ms; transition-property: text-decoration; transition-timing-function: ease-in-out;" target="_blank">Zev Steinhardt</a></div></div></div></div></div></div><span class="q-text qu-mx--tiny qu-color--gray qu-fontSize--small" style="box-sizing: border-box; color: #636466; direction: ltr; font-size: 13px; margin-left: 4px; margin-right: 4px;">·</span><div class="q-text qu-color--gray qu-fontSize--small qu-passColorToLinks qu-truncateLines--1" style="-webkit-box-orient: vertical; -webkit-line-clamp: 1; box-sizing: border-box; color: #636466; direction: ltr; display: -webkit-box; font-size: 13px; overflow: hidden; text-overflow: ellipsis;"><a class="q-box qu-cursor--pointer qu-hover--textDecoration--underline" href="https://www.quora.com/Has-a-play-ever-happened-in-baseball-that-was-so-out-of-the-ordinary-that-no-written-umpiring-rule-at-the-time-covered-it/answer/Zev-Steinhardt" style="-webkit-tap-highlight-color: rgba(255, 255, 255, 0.6); background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; cursor: pointer; direction: ltr; text-decoration-line: none; transition-duration: 180ms; transition-property: text-decoration; transition-timing-function: ease-in-out;" target="_top">July 9, 2019</a></div></div><div class="q-flex qu-flexWrap--wrap" style="box-sizing: border-box; direction: ltr; display: flex; flex-wrap: wrap; margin-top: 2px;"><div class="q-text qu-truncateLines--2 qu-color--gray qu-passColorToLinks qu-fontSize--small" style="-webkit-box-orient: vertical; -webkit-line-clamp: 2; box-sizing: border-box; color: #636466; direction: ltr; display: -webkit-box; font-size: 13px; overflow: hidden; text-overflow: ellipsis;">Studied at <span class="TopicName___StyledSpan-t3tegb-0 crUglW" style="word-break: break-word;">Pace University</span></div></div></div></div></div></div><div class="q-box qu-pl--tiny" style="box-sizing: border-box; direction: ltr; margin-left: auto; padding-left: 4px;"><div class="q-relative qu-size--18" style="box-sizing: border-box; direction: ltr; height: 18px; position: relative; width: 18px;"><div class="q-absolute" style="box-sizing: border-box; direction: ltr; left: -9px; position: absolute; top: -9px;"><div class="q-box qu-display--inline-block" style="box-sizing: border-box; direction: ltr; display: inline-block; pointer-events: all;"><div class="q-relative" style="box-sizing: border-box; direction: ltr; position: relative;"><div class="q-click-wrapper qu-active--bg--darken qu-active--textDecoration--none qu-focus--bg--darken qu-focus--textDecoration--none qu-borderRadius--pill qu-whiteSpace--nowrap qu-display--inline-block qu-tapHighlight--white qu-textAlign--center qu-cursor--pointer qu-hover--bg--darken qu-hover--textDecoration--none" style="-webkit-tap-highlight-color: rgba(255, 255, 255, 0.6); border-radius: 1000px; border-width: 0px; box-sizing: border-box; color: inherit; cursor: pointer; direction: ltr; display: inline-block; font: inherit; outline: none; padding: 7px; text-align: center; white-space: nowrap;" tabindex="0"><div class="q-flex qu-alignItems--center qu-justifyContent--center" style="align-items: center; box-sizing: border-box; direction: ltr; display: flex; justify-content: center;"><div class="q-relative qu-display--flex qu-alignItems--center" style="align-items: center; box-sizing: border-box; direction: ltr; display: flex; position: relative;"><span class="q-inlineBlock qu-verticalAlign--text-bottom" name="SmallClose" style="box-sizing: border-box; direction: ltr; display: inline-block; flex-shrink: 0; height: 24px; line-height: 0; vertical-align: text-bottom; width: 24px;"><span class="CssComponent__CssInlineComponent-sc-1oskqb9-1 Icon___StyledCssInlineComponent-sc-11tmcw7-0 eXDwse" style="-webkit-box-align: center; -webkit-box-pack: center; align-items: center; display: inline-flex; height: 24px; justify-content: center; width: 24px;"><svg height="24px" viewbox="0 0 24 24" width="24px"><g class="icon_svg-stroke" fill-rule="evenodd" fill="none" id="small_close" stroke-linecap="round" stroke-width="1.5" stroke="#666666"><path d="M12,6 L12,18" transform="translate(12.000000, 12.000000) rotate(45.000000) translate(-12.000000, -12.000000) "></path><path d="M18,12 L6,12" transform="translate(12.000000, 12.000000) rotate(45.000000) translate(-12.000000, -12.000000) "></path></g></svg></span></span></div></div></div></div></div></div></div></div></div><div class="q-flex" style="box-sizing: border-box; direction: ltr; display: flex;"></div><div class="q-flex qu-mb--tiny" style="box-sizing: border-box; direction: ltr; display: flex; margin-bottom: 4px;"><div class="q-text qu-bold qu-color--gray_dark_dim qu-passColorToLinks qu-userSelect--text qu-lineHeight--regular" style="box-sizing: border-box; direction: ltr; font-size: 16px; font-weight: bold; line-height: 1.4; user-select: text; word-break: break-word;"><span class="CssComponent__CssInlineComponent-sc-1oskqb9-1 TitleText___StyledCssInlineComponent-sc-1hpb63h-0 jPnwvF"><a class="q-box qu-cursor--pointer qu-hover--textDecoration--underline" href="https://www.quora.com/Has-a-play-ever-happened-in-baseball-that-was-so-out-of-the-ordinary-that-no-written-umpiring-rule-at-the-time-covered-it" style="-webkit-tap-highlight-color: rgba(255, 255, 255, 0.6); background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; cursor: pointer; direction: ltr; display: block; text-decoration-line: none; transition-duration: 180ms; transition-property: text-decoration; transition-timing-function: ease-in-out;" target="_blank"><div class="q-flex qu-flexDirection--row" style="box-sizing: border-box; direction: ltr; display: flex; flex-direction: row;"><div class="q-inline qu-flexWrap--wrap" style="box-sizing: border-box; direction: ltr; display: inline; flex-wrap: wrap;"><div class="q-text puppeteer_test_question_title" style="box-sizing: border-box; direction: ltr;"><span class="q-box qu-userSelect--text" style="box-sizing: border-box; direction: ltr; user-select: text;">Has a play ever happened in baseball that was so out of the ordinary that no written umpiring rule at the time covered it?</span></div></div></div></a></span></div></div><div class="q-relative spacing_log_answer_content" style="box-sizing: border-box; direction: ltr; position: relative;"><div class="q-text" style="box-sizing: border-box; direction: ltr; max-width: 100%;"><span class="q-box qu-userSelect--text" style="box-sizing: border-box; direction: ltr; user-select: text;"><p class="q-text qu-display--block" style="box-sizing: border-box; direction: ltr; margin: 0px 0px 1em; overflow-wrap: break-word; padding: 0px;">Back in 2008, the Yankees drafted a pitcher named Pat Venditte. What made Venditte unusual is that he can throw with both hands. In other words, he’s a switch pitcher. When he was drafted, he was assigned to the Staten Island Yankees, a low A ball team.</p><p class="q-text qu-display--block" style="box-sizing: border-box; direction: ltr; margin: 0px 0px 1em; overflow-wrap: break-word; padding: 0px;">In his first game (against the Mets farm team, the Brooklyn Cyclones), Venditte came in to pitch. After getting the first two batters out and giving up a single, he then faced Ralph Henriquez, was a switch hitter. What happened next resembled an Abbott and Costello comedy routine. Venditte would put the glove on one hand (he had a specially made glove that could be worn on either hand) and Henriquez would then step across the plate to bat from the other side. Venditte would then switch his glove hand again and Henriquez went back to the other side.</p><p class="q-text qu-display--block" style="box-sizing: border-box; direction: ltr; margin: 0px 0px 1em; overflow-wrap: break-word; padding: 0px;">Eventually, after much discussion, the umpires ruled that Henriquez would have to choose a batting side first, before Venditte had to commit. Henriquez was mad and, after he struck out, he slammed the bat against the ground in frustration.</p><p class="q-text qu-display--block" style="box-sizing: border-box; direction: ltr; margin: 0px 0px 1em; overflow-wrap: break-word; padding: 0px;">The umpires were, in essence, winging it, because there was no rule to cover the situation. Eventually, the higher ups in baseball did write a rule to cover the situation — the opposite of the umpires’ decision.</p></span></div></div></div></div></div></div></div></div></div><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2020/09/baseball-can-go-on-forever-it-doesnt.htmlnoreply@blogger.com (gasarch)4tag:blogger.com,1999:blog-3722233.post-6364597152143042105Mon, 14 Sep 2020 16:16:00 +00002020-09-14T11:54:30.124-05:00An interesting serendipitous number<p> Last seek I blogged about two math problems of interest to me <a href="https://blog.computationalcomplexity.org/2020/09/two-math-problems-of-interest-at-least.html">here</a>.</p><p>One of them two people posted answers, which was great since I didn't know how to solve them and now I do. Yeah! I blogged about that <a href="https://blog.computationalcomplexity.org/2020/09/when-are-both-x23y-and-y23y-both.html">here</a>.</p><p><br /></p><p>The other problem got no comments, so I suppose it was of interest to me but not others. I was interested in it because the story behind it is interesting, and the answer is interesting.</p><p><br /></p><p>it is from the paper </p><p>An interesting and serendipitous number by John Ewing and Ciprian Foias, which is a chapter in the wonderful book </p><p>Finite vs Infinite: Contributions to an eternal dilemma</p><p>Here is the story, I paraphrase the article (I'll give pointers later).</p><p>In the mid 1970's a student asked Ciprian about the following math-competition problem:</p><p>x(1)>0 x(n+1) = (1 + (1/x(n)))^n. For which x(1) does x(n) --> infinity?</p><p>It turned out this was a misprint. The actual problem was</p><p>x(1)>0 x(n+1)=(1+(1/x(n))^{x(n)}. For which x(1) does x(n) --> infinity.</p><p><br /></p><p>The actual math-comp problem (with exp x(n)) is fairly easy (I leave it to you.) But this left the misprinted problem (with exp n). Crispian proved that there is exactly ONE x(1) such that x(n)--> infinity. </p><p>Its approx 1.187... and may be trans.</p><p><br /></p><p>I find the story and the result interesting, but the proof is to long for a blog post.</p><p>I tried to find the article online and could not. A colleague found the following:</p><p><br /></p><p>A preview of the start of the article <a href="https://link.springer.com/chapter/10.1007/978-1-4471-0751-4_8">here</a></p><p>Wikipedia Page on the that number, called the Foias constant, <a href="https://en.wikipedia.org/wiki/Foias_constant">here</a></p><p>Mathworld page on that number <a href="https://mathworld.wolfram.com/FoiasConstant.html">here</a></p><p>Most of the article but skips two pages <a href="https://books.google.com/books?id=Bjb0BwAAQBAJ&pg=PA119&lpg=PA119&dq=serendipitous+number+John+Ewing+and+Ciprian+Foias&source=bl&ots=4tn1sk3XEA&sig=ACfU3U3GM9VtlyWxTjq302E5Uf7Tmr49Hw&hl=en&sa=X&ved=2ahUKEwiewLSF9OjrAhVkmXIEHRYEAMA4ChDoATAAegQICRAB#v=onepage&q=serendipitous%20number%20John%20Ewing%20and%20Ciprian%20Foias&f=false">here</a></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2020/09/an-interesting-serendipitous-number.htmlnoreply@blogger.com (gasarch)3tag:blogger.com,1999:blog-3722233.post-8975826682758317937Thu, 10 Sep 2020 13:33:00 +00002020-09-10T15:19:45.139-05:00When are both x^2+3y and y^2+3x both squares, and a more general question<p> In my last post (see <a href="https://blog.computationalcomplexity.org/2020/09/two-math-problems-of-interest-at-least.html">here</a>) I asked two math questions. In this post I discuss one of them. (I will discuss the other one later, probably Monday Sept 14.)</p><p><br />For which positive naturals x,y are x^2+3y and y^2+3x both squares?</p><p>I found this in a math contest book and could not solve it, so I posted it to see what my readers would come up with. They came up with two solutions, which you can either read in the comments on that post OR read my write up <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/sq3.pdf">here</a>.)</p><p>The problem raises two more general questions</p><p>1) I had grad student Daniel Smolyak write a program that showed that if 1\le x,y \le 1000 then the only solutions were (1,1) and (11,16) and (16,11). (See write up for why the program did not have to look like anything close to all possibly (x,y).) </p><p>Is there some way to prove that if the only solutions for 1\le x,y\le N (some N) are the three given above, then there are no other solutions?</p><p><br /></p><p>2) Is the following problem solvable: Given p,q in Z[x,y] determine if the number of a,b such that both p(a,b) and q(a,b) are squares is finite or infinite. AND if finite then determine how many, or a bound on how many.</p><p><br /></p><p>Can replace squares with other sets, but lets keep it simple for now. </p>https://blog.computationalcomplexity.org/2020/09/when-are-both-x23y-and-y23y-both.htmlnoreply@blogger.com (gasarch)6tag:blogger.com,1999:blog-3722233.post-83517349672236531Sun, 06 Sep 2020 21:05:00 +00002020-09-06T22:42:03.965-05:00Two Math Problems of interest (at least to me)<p> I will give two math problems that are of interest to me.</p><p>These are not new problems, however you will have more fun if you work on them yourself and leave comments on what you find. So if you want to work on it without hints, don't read the comments.</p><p><br /></p><p>I will post about the answers (not sure I will post THE answers) on Thursday.</p><p><br /></p><p>1) Let x(1)>0. Let x(n+1) = ( 1 + (1/x(n)) )^n. </p><p><br /></p><p>For how many values of x(1) does this sequence go to infinity?</p><p><br /></p><p>2) Find all (x,y) \in N \times N such that x^2+3y and y^2+3x are both squares. </p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2020/09/two-math-problems-of-interest-at-least.htmlnoreply@blogger.com (gasarch)5tag:blogger.com,1999:blog-3722233.post-4647242799583898034Tue, 01 Sep 2020 15:29:00 +00002020-09-02T09:19:44.687-05:00A well known theorem that has not been written down- so I wrote it down- CLIQ is #P-complete<p>(The two proofs that CLIQ is #P-complete that I discuss in this blog are written up by Lance and myself and are <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/sharpclique.pdf">here</a>. I think both are well known but I have not been able to find a writeup,so Lance and I did one.)</p><p><br /></p><p> I have been looking at #P (see my last blog on it it, <a href="https://blog.computationalcomplexity.org/2020/08/sharp-p-and-issue-of-natural-problems.html">here</a>, for a refresher on this topic) since I will be teaching this topic in Spring 2021. Recall</p><p>#SAT(\phi) = the number of satisfying assignments for phi</p><p>#CLIQ((G,k))= the number of cliques of size \ge k of G</p><p>#SAT is #P-complete by a cursory look at the proof of the Cook-Levin theorem.</p><p>A function is #P-complete if everything else in #P is Turing-Poly red to it. To show for some set A </p><p>in NP, #A is #P-complete one usually uses pars reductions. </p><p>I wanted a proof that #CLIQ is #P-complete, so I wanted a parsimonious reduction from SAT to CLIQ (Thats a reduction f: SAT--> CLIQ such that the number of satisfying assignments of phi equals the number of cliques of size \ge k of G.)</p><p>I was sure there is such a reduction and that it was well known and would be on the web someplace. So I tried to find it.</p><p>ONE:</p><p>I tracked some references to a paper by Janos Simon (<a href="https://link.springer.com/content/pdf/10.1007%2F3-540-08342-1_37.pdf">see here</a>) where he claims that the reduction of SAT to CLIQ by Karp <a href="{http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf">(see here)</a> was pars. I had already considered that and decided that Karps reduction was NOT pars. I looked at both Simon's paper and Karp's paper to make sure I wasn't missing something (e.g., I misunderstood what Simon Says or what Karp ... darn, I can't think of anything as good as `Simon Says'). It seemed to me that Simon was incorrect. If I am wrong let me know.</p><p>TWO</p><p>Someone told me that it was in Valiant's paper (see <a href="https://epubs.siam.org/doi/10.1137/0208032">here</a>). Nope. Valiant's paper shows that counting the number of maximal cliques is #P-complete. Same Deal Here- if I am wrong let me know. One can modify Valiant's argument to get #CLIQ #P-complete, and I do so in the write up. The proof is a string of reductions and starts with PERM is #P-complete. This does prove that# CLIQ is #P-complete, but is rather complicated. Also, the reduction is not pars.</p><p>THREE <br />Lance told me an easy pars reduction that is similar to Karp's non-pars reduction, but it really is NOT Karp's reduction. Its in my write up. I think it is well known since I recall hearing it about 10 years ago. From Lance. Hmmm, maybe its just well known to Lance.</p><p><br /></p><p>But here is my question: I am surprised I didn't find it on the web. If someone can point to a place on the web where it is, please let me know. In any case, its on the web NOW (my write up) so hopefully in the future someone else looking for it can find it.</p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2020/09/a-well-known-theorem-that-has-not-been.htmlnoreply@blogger.com (gasarch)3tag:blogger.com,1999:blog-3722233.post-1663724076500583508Mon, 24 Aug 2020 01:40:00 +00002020-08-23T20:40:10.264-05:00Sharp P and the issue of `natural problems'<p> #P was defined by Valiant as a way to pin down that the PERMANENT of a matrix is hard to compute.</p><p>The definition I give is equivalent to the one Valiant gave.</p><p>g is in #P if there exists p a poly and B in P such that</p><p>g(x) = | { y : |y| = p(|x|) and (x,y) \in B } |</p><p>A function f is #P-complete if g is in #P and for all g in #P, f is poly-Turing reducible to g.</p><p>#SAT is the function that, given a formula, returns the number of satisfying assignments. It is #P-complete by looking at the proof the Cook-Levin Theorem. The reduction of f to #SAT only makes one query to #SAT. A common way to show that #A is #P-complete is to show that SAT \le A with a reduction that preserves the number of solutions. </p><p>Valiant proved that PERM was #P-complete (his reduction only used 1 call to PERM).</p><p>There are problems in P whose #-version is #-P complete: Matching and DNF-SAT are two of them.</p><p>Notice that I defined #SAT directly, not in terms of a poly p and a set B as above. Here is why: if you use poly p and set B one can do obnoxious things like: </p><p>SAT = { phi : exists yz 2n-bits long such that phi(y)=T and z is prime }</p><p>The # version of this definition is not really what I want (though I am sure its #P-complete).</p><p>Valiant (see <a href="https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf">here</a> and <a href="http://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/permanent.pdf">here</a>) and Simon (see <a href="https://link.springer.com/content/pdf/10.1007%2F3-540-08342-1_37.pdf">here</a>) showed that for many known NPC-problems A, #A is #P-complete. They meant NATURAL problems. Is it true for all natural NP-complete problems?</p><p>Unfortunately the statement `All NATURAL NPC problems give rise to #P-complete functions' is hard (impossible?) to state rigorously and hence hard (impossible?) to prove. </p><p>1) Is there a natural A in NP such that #A is NOT #P-complete (under assumptions)?</p><p>2) Are there any theorems that show a large set of NPC problems have #P counterparts? Or are we doomed to, when we want to show some #A is #P-complete, come up with a new proof?</p><p>3) Can one PROVE there are NPC problems A such that #A is NOT #P-complete? (under assumptions).</p>https://blog.computationalcomplexity.org/2020/08/sharp-p-and-issue-of-natural-problems.htmlnoreply@blogger.com (gasarch)1tag:blogger.com,1999:blog-3722233.post-6748297921609096715Mon, 17 Aug 2020 12:35:00 +00002020-08-17T08:53:59.973-05:00Mathematics is not commutative In my poll of P vs NP and other issues, one of the questions was<br />
<br />
<br />
<i>Is factoring in P?</i><br />
<i><br /></i>
One of the most interesting answers was<br />
<br />
<br />
<i> I don't really see why it shouldn't be. - Peter Shor</i><br />
<i><br /></i>
Recall that Peter Shor proved Factoring is in Quantum-P which lead to intense interest in Quantum Computing.<br />
<br />
1) What if factoring was in P and this was shown before Shor's algorithm? Would Shor or someone else have ever proven factoring in quantum P? Would there be as much intense interest in quantum computing as there is now? Perhaps by physicists more than CS people?<br />
<br />
2) What if factoring was in P and this was shown before RSA? Where would crypto be now? Zip drives with a googleplex random (or nearly random) bits and more 1-time pads? More lattice based crypto? Or RSA but with larger numbers? This may depend on how good the factoring algorithm is.<br />
<br />
3) More generally, how much does the order of events matter for science?<br />
<br />
a) If the Banach-Tarski paradox was discovered early on, would we have just tossed out the Axiom of Choice before so much more was build on it? Darling thinks we should toss out AC NOW because of Banach-Tarski.<br />
<br />
b) In the model of set theory L you can do ALL of math except some parts of set theory and maybe a few other things (note quite: Harvey Friedman has found some combinatorial statements that need large cardinals to prove). Had L been discovered earlier then could we all now be working in L (except a few people who look at other models, but they are not in the mainstream)? We might know more about L and less about forcing. We would KNOW that AC and CH are true. Or we would think we know.<br />
<br />
c) If Engineers were the first ones to look at SAT and reductions, might they have been content to know that if SAT \le A then A is probably hard? No need for the Cook-Levin Theorem! And then when someone proved Cook-Levin would the Engineers not really cares since they already knew SAT was hard?<br />
<br />d) I can imagine Ramsey's Theorem being discovered much later for some application, or perhaps never being discovered at all.<div><br /></div><div>e) VDW's theorem has so few application, I can imagine it never being discovered. </div><div><br /></div><div>4) There are cases where if A was discovered before B then B has an easy proof, whereas if B was discovered before A, then B has a hard proof. I'll give one example:</div><div><br /></div><div>Given HALT is undecidable, Godel's theorem is easy.</div><div><br /></div><div>Assume HALT is undecidable. </div><div><br /></div><div>Let STAT(e) be the statement M_e(0) does not halt.</div><div><br /></div><div>There is some e such that M_e(0) does not halt but ZFC cannot prove this.</div><div><br /></div><div>PROOF: Assume, By Way of Contradiction that for all e such that M_e(0) does not halt,</div><div>ZFC could prove this. Then HALT is DECIDABLE:</div><div><br />Given e, run M_e(0) and at the same time enumerate all proofs in ZFC. It is guaranteed that</div><div>you will either find M_e(0) halts or a proof that M_e(0) does not halt. Hence you will,</div><div>in finite time, know if M_e(0) halts OR NOT.</div><div><br /></div><div>END OF PROOF</div><div><br /></div><div>Is the sequence of events where HALT is proven undecidable before Godel's theorem plausible.</div><div>I think so</div><div><br /></div><div>I INVITE my readers to give there own examples of when Math is not commutative- meaning that</div><div>the order of events matters.</div><div>
<br /></div>https://blog.computationalcomplexity.org/2019/04/what-if-history-of-science-factoring.htmlnoreply@blogger.com (GASARCH)7tag:blogger.com,1999:blog-3722233.post-6597301440817356598Thu, 13 Aug 2020 14:10:00 +00002020-08-13T09:11:51.018-05:00Simons Institute Gets Another Decade<p> <a href="https://simons.berkeley.edu/news/simons-foundation-announces-new-355-million-grant-simons-institute-theory-computing-press">Great news</a> out of the Simons Institute.</p><blockquote><p>The Simons Foundation has ensured a second decade of research and innovation for the Simons Institute for the Theory of Computing, based at UC Berkeley, through a $35.5 million grant. The grant, which will begin in 2022, after the conclusion of the Simons Institute's first 10 years, will support the Simons Institute's mission and activities through June 2032.</p></blockquote><p>Congrats to Shafi Goldwasser and her team and of course a special thanks to Jim Simons and his foundation for their support for the theory community. </p><p>Time flies. I remember when I was on Team Chicago in the final rounds back in 2011. We lost but the theory community won as Berkeley did the institute well with amazing collaborative spaces, thanks mainly I hear from Alistair Sinclair, and the strong programs and workshops organized by the many volunteers across the theory community. </p><p>The institute started right when I started as a department chair so I never had the opportunity for the true Simons experience, joining for a semester-long program. When I did sneak away for a week at Simons I purposely avoided the workshops for Simons is at its best when strong researchers, connected by one of the programs, just talk, work and socialize together. I joined an amazing collection of complexity theorists to form a rather mediocre pub trivia team.</p><p>Even if you never make it there, the institute has a great <a href="https://www.youtube.com/user/SimonsInstitute">collection of videos</a> of its workshops, talks and celebrations. COVID-19 has driven Simons on-line but that just opens up their <a href="https://simons.berkeley.edu/workshops">workshops</a> and other events to a wider audience.</p><p>Congrats again to the Simons Institute for what it's given to the theory community and to its next dozen years with hopefully many more to follow!</p>https://blog.computationalcomplexity.org/2020/08/simons-institute-gets-another-decade.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-1361848584634042636Mon, 10 Aug 2020 01:38:00 +00002020-08-09T20:38:29.668-05:00Random Thoughts on the Pandemic<p> </p><p>1) Contrast the following two points and, if you have an intelligent way to fill-in-the-blank for the second one, please comment.</p><p>a) When Trump says `open the schools or I will cut of funding' I disagree, or at least he should talk more about how to do it carefully BUT there is an underlying important and serious issue: how to balance health and education. Similar for when he talks about opening up business's - how to balance heath and the economy.</p><p>b) When Trump says `hydroxychloroquine is a potential cure for covid' I (and most of the medical community) disagree, BUT FILL IN THE BLANK. Is there SOME serious issue involved here that I am just missing?</p><p>2) I have seen several approaches to large gathering, say Churchs, beach parties, motorcycle meeting etc. </p><p>a) DO IT ONLINE. UMCP classes will be on-line in the fall. My church has been online since mid March and seems like it will do the same in the fall. (Note- Choir is much worse than normal talking for spreading it, so Choir might not resume for a much longer time than Church).</p><p>b) HAVE THEM but SOCIAL DISTANCE and MASKS and other precautions. And it works. I hope it works.</p><p>c) HAVE THEM, realize that there IS an issue, TRY to do some of the precautions, but fail. This may be what has happened at some high schools, see <a href="https://www.thedailybeast.com/9-people-test-positive-at-georgia-school-with-photo-of-crowded-hallway?ref=home">Here</a>.</p><p>d) HAVE THEM and ignore ALL precautions either because </p><p>i) God will protect you</p><p>ii) The Government is not my boss. Such people are usually pro-business so they should NOT mind if a business on its own requires masks and SHOULD mind if its the government. I have not seen them making that distinction. Such people are usually against Federalism and for localism. So they should be upset when a Prez or a Gov overides a Mayor's Mask Mandate. I have not seen this.</p><p>iii) The whole think is a Hoax. How can people still believe this?</p><p>These three may overlap.</p><p>3) The Sturgis Motorcycle Rally in South Dakota seems to believe ii and iii. Can someone give any rational reason why they want to have this rally and why its allowed to happen. Given how many people come (usually 250,000- less now?) from all across the country, this could make thinks far far worse. But see next point.</p><p>4) Libertarians think that there is too much Government in our lives. This is a fair point of view but it needs to be tested on a case by case basis. There are some things that REQUIRE a more national response. When this happens Libertarians have two choices:</p><p>a) Apply their thinking to figure out how Gov can help with the least damage. For example, Carbon tax for global warning. In the current pandemic they might have LOCAL govs pass mandatory mask laws.. Or they would at least set a good example by wearing masks themselves. Perhaps relax regulations on medical stuff so that companies can work together without worrying about anti-trust, and perhaps look more carefully at regulations that get in the way (might be a good idea anyway).</p><p>b) Deny its a problem. Man made Global Warming is a myth. Covid is a hoax. Hence its okay to have the Motorcycle Rally. But the problem is, this doesn't just harm the people showing up, it harms others as well.</p><p>5) Early on I was puzzled that Trump didn't care more since older people (his base!) are at more risk. Did he think it would only affect democrats (early on NY was hit badly). Why didn't his advisors tell him that it would kill his own base?I ASK NON-RHETORICALLY Or did they and he didn't list. My point is, for purely selfish reasons Trump should have taken more action earlier, so I am surprised he did not. See next point.</p><p>6) Trump could have even taken action in a Trumpian way:</p><p>The Chinese and the Democrats are waging a bio-war on real Americans (white rural older) !!! We will STOP them in their tracks and show them they can't mess with us!! I will LOCKDOWN some cities AND provide online stuff to schools, business's (my cronies) and churchs (SCREW that stupid sep of church and state- that was only one passage in a letter Thomas Jefferson wrote). </p><p>He might have even got Democrats to complain that it will choke the economy and hurt the poor, and that giving stuff to churchs is against the constitution (it prob is). </p><p>7) If a vax for covid is found, will Trump urge his base (some of whom are anti-vax) to take it? Having said that, if it comes out in October it may be untested so I doubt I will take it. I'll wait until Dr Fauci says its okay to take it. (See <a href="https://www.youtube.com/watch?v=lUiDLcp_hIw">here</a> for a nice song about Dr. Fauci.)</p><p>8) Some people who thought it was a Hoax and then got a bad case of it are saying loudly `I WAS WRONG! Its Real!' I wonder if Herman Cain realized it was real before he died of it? I wish he had said `I WAS WRONG! ITS REAL! Wear a MASK' (The Whitehouse denies that he got Covid from the Tulsa Rally, here is headline only since something is behind paywalls: <a href="https://tulsaworld.com/news/local/white-house-denies-herman-cain-contracted-covid-19-at-tulsa-trump-rally-prior-to-his/article_b0c83d3c-c3de-547e-9a5f-434b6a82ac61.html">here</a>)</p><p>9) At Tulsa the presidents people took DOWN signs about safe distancing. So again, why does the Prez want to kill his own base? I ask non rhetorically. I am serious- I want someone to defend his actions intelligently both this one and the hydro-whatever in the first point.</p><p>10) Authoritarian governments often claim that they bring order and can act fast to get things done. So they SHOULD have an advantage during the pandemic since they can more easily ORDER a lockdown. Yet they don't seem to be doing better. </p><p>Russia: <a href="https://www.worldometers.info/coronavirus/country/russia/">See Here</a>, number of cases going up fast.</p><p>Iran: <a href="https://www.worldometers.info/coronavirus/country/iran/">See here</a> and <a href="https://www.bbc.com/news/world-middle-east-53598965">Here</a>, number of cases going up fast.</p><p>These countries and others, and America, had their leaders LIE about the extend of the virus early on. What is the upside of doing this? I ask non-rhetorically. </p><p><br /></p>https://blog.computationalcomplexity.org/2020/08/random-thoughts-on-pandemic.htmlnoreply@blogger.com (gasarch)4tag:blogger.com,1999:blog-3722233.post-4290135672537490640Thu, 06 Aug 2020 18:59:00 +00002020-08-15T13:31:11.095-05:00Do Senators have an Advantage for being Dem VP Nominee?This is a non-partisan post. Even so: I plan to vote for Joe Biden.<div><br /></div><div>(Lance says that whenever I write `this is a non-partisan post' its partisan anyway.)</div><div><br /></div><div>I've had posts on predicting VPs before:</div><div><br /></div><div>In <a href="https://blog.computationalcomplexity.org/2019/02/using-who-will-be-dem-vp-choice-article.html">this post</a> I looked at a Nate Silver column a few months ago where they were trying to predict the democratic VP nomination <i>before the Prez nominee was know</i>n. Some of what they said seems relevant.</div><div><br /></div><div>In <a href="https://blog.computationalcomplexity.org/2008/09/i-would-be-on-intrade-that-intrade-will.html">this post</a> I PREDICTED that bets on INTRADE would not do well on picking VPs since VP picks are hard to predict and often are not from anyone's short list. I DID NOT PREDICT that INTRADE would go out of business.</div><div><br /></div><div>I came across a statistic recently that seems relevant and inspired this post. Actually this post asks IS this statistic relevant?</div><div><br /></div><div>From Prez candidate Harry Truman to Prez candidate Hillary Clinton there have been 15 Dem VP nominees (not counting incumbents) of which 13 have been Senators:</div><div><br /></div><div>Harry Truman(Prez)-Alben Barkely. Sen from Kentucky</div><div>Adlai Stevenson(Gov-Illinois) -John Sparkman. Sen from Alabama</div><div>Adlai Stevenson(Gov-Illinois)-Estes Kefauver, Sen from Tennessee </div><div>John F Kennedy(Sen-Mass)-Lyndon B Johnson, Sen from Texas</div><div>Lyndon B Johnson(Prez)-Hubert Humphrey,Sen from Minnesoda</div><div>Hubert Humphrey(VP)-Ed Muskie, Sen from Maine</div><div>George McGovern Sen-South Dakota)-Sgt Shriver Amb to France, Office of Econ Activity</div><div>Jimmy Carter(Gov Georgia)-Walter Mondale- Senator from Minnesota</div><div>Walter Mondale(Senator Minnesota)-Geraldine Ferraro Congressperson- NY</div><div>Mike Dukakis (Gov Mass), Lloyd Benson-Sen Texas</div><div>Bill Clinton(Gov Arkansas), Al Gore Sen from Tennesee</div><div>Al Gore (VP), Joe Lieberman Senator from Conn</div><div>John Kerry (Sen-Mass), John Edwards Sen from NC</div><div>Barack Obama (Sen-Illinois), Joe Biden Sen from Del</div><div>Hillary Clinton (Sen-NY), Tim Kaine- Sen Virginia</div><div><br /></div><div>Of the 15 Dem VP nominees, 13 are Senators</div><div><br /></div><div>Of the 13 Rep VP nominees, 4 are Senators <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/rebvp.txt">see here</a></div><div><br /></div><div>My Speculations: </div><div><br /></div><div>1) When a gov runs he wants someone with fed experience. That explains 5 of the cases above.</div><div><br /></div><div>2) Senators tend to be better known than other politicians, so perhaps being well known is what you need. Note on the Republican Side Paul Ryan was a House member but was well known.</div><div><br /></div><div>3) Why do the Reps and Dems differ on this? Is the sample size too small to make this question interesting? </div><div><br /></div><div>So here is the question: When trying to predict who the Dem VP will be (this year or any year) should being a Senator give someone a plus? A higher weight in a Neural Net? </div><div><br /></div><div>Kamala Harris is the favorite on the betting markets. Is this because she is a Senator?</div><div><br /></div><div>She has a national profile and has already been vetted since she rana serious campaign for Prez in the primaries. So I would say that THATS the reason (and other reasons), not that she is a Senator. But would she have been able to run a serious campaign in the primaries if she wasn't already a Senator? I ask non rhetorically.</div><div><br /></div><div>ADDED LATER- one of the comments inspired me to also include who the Republicans picked for VP since Truman. Much more variety in the jobs they held prior. This is neither good or bad.</div><div><br /></div><div><br /></div><div><div><br /></div><div>Thomas Dewey (Gov-NY), Earl Warren (Gov-California)</div><div><br /></div><div>Dwight Eisenhower (General), Richard Nixon (Sen-California)</div><div><br /></div><div>Richard Nixon (VP), Henry Cabot Lodge (Sen-Mass, Amb-UN)</div><div><br /></div><div>Barry Goldwater (Sen-Arizona), William Miller (Representive-NY)</div><div><br /></div><div>Richard Nixon (VP), Spiro Agnew (Gov-MD)</div><div><br /></div><div>Gerald Ford (Prez, Senator-Michigan), Bob Dole (Senator-Kansas)</div><div><br /></div><div>Ronald Reagan (Gov California), George Bush (Dir of CIA)</div><div><br /></div><div>George Bush (VP), Dan Quayle (Sen-Indiana)</div><div><br /></div><div>Bob Dole (Sen-Kansas), Jack Kemp (Representiative-NY)</div><div><br /></div><div>George W Bush (Gov-Texas), Dick Cheney (Cabinet)</div><div><br /></div><div>John McCain (Sen-Arizona), Sarah Palin (Gov-Alaska)</div><div><br /></div><div>Mitt Romney (Gov-Mass), Paul Ryan (Represenative-NY)</div><div><br /></div><div>Donald Trump (Businessman-NY), Mike Pence (Gov-Indiana)</div></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div>https://blog.computationalcomplexity.org/2020/08/do-senators-have-advantage-for-being.htmlnoreply@blogger.com (gasarch)8tag:blogger.com,1999:blog-3722233.post-1233384953933252805Mon, 03 Aug 2020 02:02:00 +00002020-08-02T23:32:26.968-05: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)9tag:blogger.com,1999:blog-3722233.post-3389282706697250678Mon, 27 Jul 2020 03:18:00 +00002020-07-26T22:18:26.463-05: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-24T11:23:39.872-05: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-20T16:26:04.931-05: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-12T15:18:51.310-05: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-09T10:57:23.778-05: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)3