tag:blogger.com,1999:blog-3722233Sun, 25 Sep 2022 18:31:25 +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)Blogger2945125tag:blogger.com,1999:blog-3722233.post-6673399999358490980Wed, 21 Sep 2022 20:48:00 +00002022-09-21T15:51:00.831-05:00POSTED UPDATED VERSION OF Computers and Intractability: A guide to Algorithmic Lower Bounds posted (New title) <p>We have posted a revised version of </p><p><br /></p><p><i>Computational Intractability: A Guide to Algorithmic Lower Bounds</i></p><p>by Demaine-Gasarch-Hajiaghayi</p><p>The book is <a href="https://hardness.mit.edu/">here</a>.</p><p>(For the original post about it, edited it to use the new title (see below), see <a href="https://blog.computationalcomplexity.org/2022/08/computers-and-intractability-guide-to.html">HERE</a>.) </p><p><br /></p><p>We <i>changed the title</i> (the title above is the new one) </p><p>since the earlier title looked <i>too much</i></p><p>like the title of Garey's and Johnson's classic. While that was intentional we </p><p>later felt that it was <i>too close</i> to their title and might cause confusion. </p><p>Of course changing the title might <i>also</i> cause confusion; however, </p><p>this post (and we will email various people as well) will stem that confusion. </p><p><br /></p><p>We welcome corrections, suggestions and comments on the book. Email us at <a href="mailto:hardness-book@mit.edu">hardness-book@mit.edu</a></p><p><br /></p>https://blog.computationalcomplexity.org/2022/09/posted-updated-version-of-computers-and.htmlnoreply@blogger.com (gasarch)0tag:blogger.com,1999:blog-3722233.post-6364865158369002106Mon, 19 Sep 2022 19:02:00 +00002022-09-19T14:02:02.362-05:00There are two different definitions of Integer Programming. Why? <p>Alice and Bob have the following conversation.</p><p>===============================</p><p>ALICE: In your book you define INT PROG as, given a matrix A and vectors b,c,</p><p>find the integer vector x such that Ax\le b and c DOT x is maximized.</p><p>This is not correct! You also need x\ge 0.</p><p><br /></p><p>BOB: Really? I always heard it without that extra constraint, though I am</p><p>sure they are equivalent and both NP-complete (Alice nods).</p><p>Where did you see it defined with that extra constraint?</p><p><br /></p><p>ALICE:</p><p><a href="https://en.wikipedia.org/wiki/Integer_programming">Wikipedia entry in IP</a><br /></p><p><a href="https://web.mit.edu/15.053/www/AMP-Chapter-09.pdf">Chapter of a book at an MIT website</a><br /></p><p><a href="https://www.sciencedirect.com/topics/mathematics/integer-programming-problem">Something on Science Direct</a><br /></p><p><a href="https://courses.cs.duke.edu/fall12/compsci590.1/introduction.pdf">A course at Duke</a><br /></p><p><a href="https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf">An article by Papadimitriou</a> <br /></p><p><a href="https://arxiv.org/pdf/2012.00079.pdf">An article on arxiv</a><br /></p><p>The book <i>Graphs, Networks and Algorithms</i> by Dieter Jungnickel</p><p>Bob, do you have examples where they do not use that extra constraint. </p><p>BOB: </p><p><a href="https://www.mathworks.com/discovery/integer-programming.html">Math Works</a><br /></p><p><a href="https://faculty.math.illinois.edu/~mlavrov/docs/482-fall-2019/lecture33.pdf">Lecture notes from UIUC</a><br /></p><p><a href="https://coral.ise.lehigh.edu/~ted/files/ie418/lectures/Lecture1.pdf">Lecture notes from Lehigh Univ.</a><br /></p><p>The book <i>Parameterized Complexity Theory</i> by Flum and Grohe</p><p>The book <i>Computers and Intractability : A Guide to the Theory of NP-Completeness</i> by Garey and Johnson</p><p>ALICE: Both of our lists are impressive. So now what? </p><p>--------------------------------------------------------------------</p><p>(This is Bill again.)</p><p>What indeed!</p><p>1) Why are there two definitions of Int Prog?</p><p>2) When is it good to use which one? </p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2022/09/there-are-two-different-definitions-of.htmlnoreply@blogger.com (gasarch)6tag:blogger.com,1999:blog-3722233.post-6674583717006469349Thu, 15 Sep 2022 20:41:00 +00002022-09-19T11:00:38.293-05:00Monarachy: A Problem with Definitions<p> As I am sure you know, Queen Elizabeth II passed away at the age of 96 recently. I am not a royal-watcher, but I am a royal-watcher-watcher. That is, the question of why people care about the lives of these people intrigues me. A few notes</p><p>1) Was she a <i>good Queen?</i> People tend to think so; however, since the job is somewhat ill-defined its hard to say. </p><p>2) The Queen is supposed to be above politics (she does not vote- I was surprised to find out that legally she can, but she really can't). We know very few of Queen Elizabeth II's opinions on political events. But the notion of <i>political </i>is not well defined. One would think that if she did an appeal for people to take the COVID vax that would not be political, but somehow it is (I do not know if she did such an appeal). King Charles III believes in global warming and that we need to do something about it. This again should not be political but is. </p><p>3) She is the second longest reigning Monarch. First is King Louis XIV who first became king at the age of 4. I had a blog complaining about this <a href="https://blog.computationalcomplexity.org/2022/05/queen-elizabeth-is-3rd-longest-reigning.html">here</a>. However, there is a more interesting point I want to make. From the first to the last day of King Louis XIV reign not much had changed. Technology, politics, other things just didn't change much. By contrast the world changed A LOT between Queen Elizabeth II first and last day:</p><p>a) The British were an important power in 1952. Less so now.</p><p>b) When her father died she was in Kenya and it took 4 hours to get the news to her. Now that would be immediate. </p><p>c) Divorce was considered bad in 1952 and is why King Edmond VIII could not be king (he wanted to marry a twice-divorced woman whose ex-husbands were still alive). And now three of the Queen's children have been divorced.</p><p>d) Gay people.. enough said. There has even been a royal gay wedding, see <a href="https://www.dailymail.co.uk/news/article-5849971/Royal-familys-gay-wedding-story-Queens-cousin-Lord-Ivar-Mountbatten.html">here</a></p><p>Black people (can't call them African-Americans), Women,... you fill it in. </p><p>e) When Charles wanted to get married it seemed to be important that he marry a virgin. We cannot imagine this mentality anymore. When Prince William and Kate got married they were already living together and this was NOT an issue for ANYONE. I looked up what the Church of England thought of it and all I got was some very bland comments like <i>That's what young people do nowadays. </i></p><p>3) Is the monarchy a good thing? As an American I feel I do not have a right to an opinion. If the citizens of the United Kingdom approve of the monarch (polls show they do) then who am I do tell them they are wrong? Even so, lets look at reasons for it</p><p>a) Tourism. It has been said that the Monarchy leads to MONEY from tourism. So it is worth the price? Nobody seems to know and it would be hard to tell. However, I don't think the citizens of the United Kingdom view money as the reason for Monarchy. The American analog is giving Disneyland tax breaks to be in Florida which generates jobs. I doubt they think of the Monarchy in those mundane transactional terms. </p><p>b) CS Lewis said </p><p><i>Where men are forbidden to honour a king they honour millionaires, athletes, or film stars instead: even famous prostitutes and gangsters. For spiritual nature, like bodily nature, will be served; deny it food and it will gobble poison.</i></p><p>This is bit odd- they must all pretend to like the monarchy to make it work. A long time ago when Charles and Dianna were both having affairs, 80% of the citizens the United Kingdom thought that was okay so long as they are discreet so <i>the people</i> don't find out. But- those ARE the people.</p><p>Also odd- CS Lewis was a theologian and a believing Christian; however, his comment above can apply to God as well as to Kings. </p><p><i><br /></i></p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2022/09/monarachy-problem-with-definitions.htmlnoreply@blogger.com (gasarch)5tag:blogger.com,1999:blog-3722233.post-4092582253443093216Mon, 12 Sep 2022 15:26:00 +00002022-09-12T10:26:51.998-05:00Thirty Years of Dagstuhl<p> <table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto;"><tbody><tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiiAVV6vqRxQ0GiKOwjxUJJsrSy10_N1Rnaq7CSWN1LgmRkcVyYHAp5sLgwslboCRbhHq3s6iMU9bSHGJlLBUthZUpI750kpeBrLOkMQcLtDBumFlxNfU-mSDwmO_8nRgw9onQW6AVeluj2ZL1-oGuWqCRxbIVJyT5OZAsdPSTc-BM8UqwioQ/s2668/PXL_20220912_120021005.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="2259" data-original-width="2668" height="339" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiiAVV6vqRxQ0GiKOwjxUJJsrSy10_N1Rnaq7CSWN1LgmRkcVyYHAp5sLgwslboCRbhHq3s6iMU9bSHGJlLBUthZUpI750kpeBrLOkMQcLtDBumFlxNfU-mSDwmO_8nRgw9onQW6AVeluj2ZL1-oGuWqCRxbIVJyT5OZAsdPSTc-BM8UqwioQ/w400-h339/PXL_20220912_120021005.jpg" width="400" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Dagstuhl old-timers at the original castle<br /></td></tr></tbody></table><br /></p><p>I'm back at Dagstuhl for the seminar on <a href="https://www.dagstuhl.de/en/program/calendar/semhp/?semnr=22371">Algebraic and Analytic Methods in Computational Complexity</a>. My <a href="https://www.dagstuhl.de/en/program/calendar/semhp/?semnr=9206">first seminar</a> at Dagstuhl was back in 1992. I've been coming for thirty years and have been here roughly thirty times. My <a href="https://blog.computationalcomplexity.org/2019/03/back-at-dagstuhl.html">last trip</a> was pre-covid (virtual Dagstuhls don't count) and I really needed this chance to hang out and talk complexity with colleagues old and new.</p><p>Some changes since my last trip. The room doors have locks (there are rumors of an incident). You have to create your own keycard on a new machine logging into your Dagstuhl account. I had a long random password through a password manager and it was not so easy as process.</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLRrLcyKcZLTsqhWGocXuS13xG4yxOJNC9A0xL4mwzmXB8KXWwVTEsW4jF5lST7LAfHNbb_z4nwmOQarS1dwdoSwQYg7IX6NdpNqGkriuzDM4M1mP3rgiR99bV2XOAVr2iJvPsyGHBG6ECrwqYuR65Ok9uXvS_CvxogulpL0Eph-4xPLW9EA/s4080/PXL_20220912_122728903.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="3072" data-original-width="4080" height="241" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLRrLcyKcZLTsqhWGocXuS13xG4yxOJNC9A0xL4mwzmXB8KXWwVTEsW4jF5lST7LAfHNbb_z4nwmOQarS1dwdoSwQYg7IX6NdpNqGkriuzDM4M1mP3rgiR99bV2XOAVr2iJvPsyGHBG6ECrwqYuR65Ok9uXvS_CvxogulpL0Eph-4xPLW9EA/s320/PXL_20220912_122728903.jpg" width="320" /></a></div><p>The main conference room has been updated with tech for hybrid meetings, and new led lights. Books were removed from the library to create a coffee breakout space.</p><p>No Bill this time so no <a href="https://blog.computationalcomplexity.org/search?q=typecast">typecasts</a>. Still the best part of the week is talking and hearing about complexity. Today I learned about the <a href="https://en.wikipedia.org/wiki/Sperner%27s_lemma#Oriented_variants">orientations of Sperner's lemma</a>, that there is one more triangle oriented according to the direction of the corner vertices than those oriented the other way. Christian Ikenmeyer used this fact to motivate a study of closure properties of #P-functions.</p>https://blog.computationalcomplexity.org/2022/09/thirty-years-of-dagstuhl.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-1874664086811883884Wed, 31 Aug 2022 19:35:00 +00002022-08-31T14:41:34.039-05:00The NIST Process for Post-Quantum Cryptography<div><i>Guest post by <a href="https://www.cs.umd.edu/~jkatz/">Jonathan Katz</a></i></div><div><br /></div>Over the past few months there have been several interesting developments in the <a href="https://csrc.nist.gov/Projects/post-quantum-cryptography">NIST post-quantum standardization process</a>.<div><br /></div><div>By way of background, since the advent of <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm">Shor's algorithm</a> in 1994 we have known that a large-scale, general-purpose quantum computer would be able to break all currently deployed public-key cryptography in (quantum) polynomial time. While estimates vary as to when (or even whether!) quantum computers will become a realistic threat to existing public-key cryptosystems, it seems prudent to already begin developing/deploying newer "post-quantum" schemes that are plausibly secure against quantum computers.</div><div><br /></div><div>With the above in mind, NIST initiated an open process in 2017 for designing post-quantum cryptographic standards. Researchers from around the world submitted candidate algorithms for public-key encryption/key exchange and digital signatures. These were winnowed down over a series of rounds as cryptographers publicly debated the relative merits of different proposals, or showed security weaknesses in some candidates.</div><div><br /></div><div>On July 5 of this year, NIST <a href="https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf">announced</a> that it had selected four of the submissions as finalists for standardization. Only one candidate for public-key encryption was chosen, along with three digital signature schemes. Three of the four selected algorithms rely on the hardness of lattice problems; the only non-lattice scheme is a hash-based signature scheme. (It is possible to build digital signatures using "symmetric-key" assumptions alone.) In addition, four other public-key encryption schemes not based on lattices were designated for further study and possible standardization at a later point in time.</div><div><br /></div><div>Less than one month later, <a href="https://eprint.iacr.org/2022/975">Castryck and Decru announced</a> a <strong>classical</strong> attack on SIKE, one of the public-key encryption schemes chosen for further study. <a href="https://sike.org/">SIKE</a> is based on a conjectured hard problem related to isogenies on supersingular elliptic curves. The attack was not just theoretical; the researchers were able to implement the attack and run it in less than a day or less, depending on the security level being considered. Details of the attack are quite complex, but Galbraith <a href="https://ellipticnews.wordpress.com/2022/07/31/breaking-supersingular-isogeny-diffie-hellman-sidh/">gives a high-level overview</a>. <a href="https://ellipticnews.wordpress.com/2022/08/12/attacks-on-sidh-sike/">Subsequent improvements</a> to the attack followed.</div><div><br /></div><div>It is worth adding that the above follows an <a href="https://eprint.iacr.org/2022/214">entirely classical attack</a> shown roughly six months earlier on Rainbow, another submission to the NIST standardization process that made it to the 3rd round. (Rainbow is a signature scheme that relies on an entirely different mathematical problem than SIKE.) For completeness, note that none of the four finalists are impacted by any of these attacks.</div><div><br /></div><div>A few reflections on the above:</div><div><ul style="text-align: left;"><li>It is amazing that the factoring and RSA problems are still hard (for classical computers), more than 40 used after they were proposed for cryptography. The same goes for the discrete-logarithm problem (in certain groups).</li><li>It is not easy to find other hard mathematical problems! <a href="https://en.wikipedia.org/wiki/McEliece_cryptosystem">Code-based cryptography</a> has been around about as long as factoring, but has been somewhat unpopular for reasons of efficiency. Lattice-based cryptosystems still seem to give the leading candidates.</li><li>We need more (non-cryptographers) studying cryptographic assumptions. The attacks on SIKE involved deep mathematics; attacks on lattice problems may involve algorithmic ideas that cryptographers haven't thought of.</li></ul></div>https://blog.computationalcomplexity.org/2022/08/the-nist-competition-for-post-quantum.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-4599175495420459984Thu, 25 Aug 2022 03:09:00 +00002022-09-21T15:48:58.535-05:00Computational Intractability: A Guide to Algorithmic Lower Bounds. First draft available! Comments Welcome!<p>(This post is written by Erik Demaine, William Gasarch, and Mohammad Hajiaghayi)</p><p>In 1979 Garey and Johnson published the classic</p><p> <i>Computers and Intractability: A Guide to NP-Completeness</i></p><p>There has been A LOT of work on lower bounds since then.</p><p>Topics that were unknown in 1979 include</p><p>Parameterized Complexity,</p><p> Lower bounds on approximation,</p><p>Other hardness assumptions (ETH, 3SUM-conjecture, APSP-conjecture, UGC, Others), </p><p>Online Algorithms,</p><p>Streaming Algorithms, </p><p>Polynomial Parity Arguments, </p><p>Parallelism, and </p><p>Many new problems have been shown complete or hard in NP, PSPACE, and other classes.</p><p><br /></p><p>Hence a sequel is needed. While it is impossible for one book to encompass all, or even a large fraction, of the work since then, we are proud to announce a book that covers some of that material:</p><p><i>Computational Intractability: A Guide to Algorithmic Lower Bounds</i></p><p>by Erik Demaine, William Gasarch, and Mohammad Hajiaghayi. MIT Press. 2024</p><p>See <a href="https://hardness.mit.edu/">HERE</a> for a link to a first draft.</p><p>We welcome corrections, suggestions and comments on the book. Either leave a comment on this blog post or emailing us at <a href="mailto:hardness-book@mit.edu">hardness-book@mit.edu</a></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2022/08/computers-and-intractability-guide-to.htmlnoreply@blogger.com (gasarch)3tag:blogger.com,1999:blog-3722233.post-5383207883567807338Mon, 22 Aug 2022 13:04:00 +00002022-08-22T08:04:18.392-05:0020 Years of the Computational Complexity Weblog<p></p><div style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6GDCODRrARsTAby27oCbx62tuXwL99PLAQoF3EAnHJ_VYJHxBeQBEW4WDsti4OYckqE0f6i3_pnSOpEoApn4H-Wxdn3XoZzhM5W-xjKtAdVcWE3-61i-McxSL6kosop34uFHoMflbs2O4lHftdkjoW0SCudrJf3pC3YtQY7J1nmhUnc9VBQ/s1024/DALL%C2%B7E%202022-08-22%2008.00.34%20-%20birthday%20cake%20with%20green%20frosting%20and%2020%20candles.png" imageanchor="1"><img alt="Birthday Cake" border="0" data-original-height="1024" data-original-width="1024" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6GDCODRrARsTAby27oCbx62tuXwL99PLAQoF3EAnHJ_VYJHxBeQBEW4WDsti4OYckqE0f6i3_pnSOpEoApn4H-Wxdn3XoZzhM5W-xjKtAdVcWE3-61i-McxSL6kosop34uFHoMflbs2O4lHftdkjoW0SCudrJf3pC3YtQY7J1nmhUnc9VBQ/w200-h200/DALL%C2%B7E%202022-08-22%2008.00.34%20-%20birthday%20cake%20with%20green%20frosting%20and%2020%20candles.png" title="Dall-E baked us a cake" width="200" /></a></div><p>I <a href="https://blog.computationalcomplexity.org/2002/08/this-is-my-complexity-web-log.html">first posted</a> on this blog twenty years ago today, still the oldest and longest running weblog in theoretical computer science, possibly in all of computer science. In those twenty years we've had nearly 3000 posts and over 23,000 comments and 10,000,000 page views. Bill Gasarch <a href="https://blog.computationalcomplexity.org/2007/03/complexity-blog-lives.html">joined me</a> officially as a co-blogger over 15 years ago on March 30, 2007. </p><p></p><p>We've seen <a href="https://blog.computationalcomplexity.org/2014/12/favorite-theorems-recap.html">major results in computational complexity</a> but the biggest challenges remain, in particular major separations of complexity classes. We've also had a front row seat to a computing revolution with the growth of cloud and mobile computing, social networks connecting us for better or for worse, and incredible successes of machine learning. It's almost as though we've been handed an oracle that gives us much of the goodness of P = NP while leaving cryptography intact. </p><p>What will the next twenty years bring? We'll be watching, posting and <a href="https://twitter.com/fortnow">tweeting</a>. Hope you keep reading and commenting. </p>https://blog.computationalcomplexity.org/2022/08/20-years-of-computational-complexity.htmlnoreply@blogger.com (Lance Fortnow)4tag:blogger.com,1999:blog-3722233.post-483004697033875840Thu, 18 Aug 2022 14:47:00 +00002022-08-18T09:47:12.585-05:00Conference Modality<p>We have had an almost normal summer conference season, for some sense of normal. At one of those conferences I participated in an hybrid conversation about whether the conference should be in-person, virtual or hybrid the following year. Here are some general thoughts.</p><p><b>In-Person</b></p><p>The traditional conference format. People travel from near and far to a hotel, conference center or campus location. Talks given in large rooms, often in parallel. A reception, some social activities, participants gathering in small groups to go out for meals. </p><p>Positives: In-person maximizes interaction between participants. Being physically away from your home means you can focus your time on the conference and your fellow participants. This was more true before the mobile devices/laptops/internet days, but still most participants will spend more time on-site than on-line.</p><p>Negatives: Expensive--with registration, hotel and air fare, even a domestic participant could have to pay $2000 or up, higher for those traveling internationally. Visas can be hard to get. Some still feel unsafe in large groups. People often leave early, pity the last speakers. And don't forget the carbon footprint. </p><p>As countries declare war on other countries or states deny certain rights, there is a push against meetings in certain places. Note the disclaimer for next year's <a href="https://fcrc.acm.org/">FCRC</a>. You might upset some people if you have conferences at these locations (and others if you don't).</p><p><b>Virtual</b></p><p>Virtual conferences would never in the past have been taken seriously but Covid forced our hands. </p><p>Talks are streamed or pre-recorded. Some interaction with chats in talks, zoom get togethers or though a systems like <a href="https://www.virtualchair.net/">virtual chair</a>. Even if we had a perfect "metaverse" experience where we could get together as though we were in person, not being there in person means we wouldn't make it a priority.</p><p>The big advantages are costs are low, it's easy to attend talks, and no danger of spreading disease. Still a virtual conference can feel too much like just a collection of streamed and recorded talks.</p><p><b>Hybrid</b></p><p>So let's make the conference hybrid and have the best of both worlds. Alas, it doesn't work out that way. It's nearly impossible to have good interaction between in-person and virtual participants--basically you have to run two separate meetings. Do you allow virtual talks or require an author to show up in person. </p><p>How do you set prices? Lower prices for virtual increases assess but decreases in-person attendance. Participants (or their advisors) might opt to save expenses and attend virtually instead of in-person, reducing the networking opportunities for everyone. </p><p>Most conferences tend to take the hybrid route to avoid the complaints if one went fully in-person or virtual, but hybrid just pretty much guarantees a mediocre experience for all.</p><p><b>Opinion</b></p><p>My suggestion is some years run the conference virtually and others in hybrid. We already have too many conferences, a byproduct of our field using conferences as the primary publication venue. I suggest following conferences like the International Congress of Mathematicians or the Game Theory World Congress, held every four years. If the main conference of a field is held every four years, researchers, particularly senior researchers, make a bigger effort to be there. You can have the virtual meetings the other years so researchers, particularly students, can continue to present their work.</p><p>No easy solutions and CS conferences have <a href="https://cacm.acm.org/magazines/2009/8/34492-viewpoint-time-for-computer-science-to-grow-up/fulltext">not worked well for years</a>. Maybe the struggle to define future conferences will allow us to focus more on the connecting researchers than just "journals that meet in a hotel".</p>https://blog.computationalcomplexity.org/2022/08/conference-modality.htmlnoreply@blogger.com (Lance Fortnow)4tag:blogger.com,1999:blog-3722233.post-8900902852699534963Mon, 15 Aug 2022 12:13:00 +00002022-08-15T07:13:00.702-05:00A non-controversial question about the Documents Donald Trump had in his houseThis is a non-partisan post. In the interest of disclosure I will divulge that I do not think private citizens should have top secret government documents in their house.<div><br /></div><div>One phrase I kept hearing in the reporting was (I paraphrase and may have the number wrong)</div><div><br /></div><div><i> The FBI removed 15 boxes of documents</i></div><div><br /></div><div>Documents? Like--- on paper? </div><div><br /></div><div>a) Are the documents also online someplace? Perhaps they intentionally are not so that they can't be hacked. </div><div><br /></div><div>b) Is having top secret documents only on paper safer than having them in electronic form? Normally I would think so. Donald Trump having them is a very unusual case. </div><div><br /></div><div>c) Having to store all of those documents on paper would seem to have storage problems. I can imagine someone with NO bad purposes making copies and taking them home since they are tired of only being about to read them in a special room. </div><div><br /></div><div>d) A problem with having them ONLY on paper is that if an accident happens and they get destroyed there is no backup. Or is there? Are there copies somewhere? That leads to twice the storage problems. </div><div><br /></div><div>e) There is a tradeoff of security and convenience. Is having the documents only on paper is an extreme point on the tradeoff, but it may be the right one. It may depend on how important it is to keep the documents secret. </div><div><br /></div><div>f) I've heard (apocryphal?) stories about some top secret document also available in public though quite legal sources (e.g., a physics journal that discusses nuclear stuff). Does the government make to much classified? If so then the problem arises of people not taking the classification seriously and getting careless. I doubt that is what happened here. </div><div><br /></div><div>g) The question I am most curious about is why did he take them? For most of his other actions his motivations are clear (e.g., he is pushing STOP THE STEAL since he wants to be president). But for this one its not clear. Unfortunately, I doubt we'll ever find out. Maybe the answer is in some documents either on paper or electronic. </div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div>https://blog.computationalcomplexity.org/2022/08/a-non-controversial-question-about.htmlnoreply@blogger.com (gasarch)8tag:blogger.com,1999:blog-3722233.post-7923989097752903737Mon, 08 Aug 2022 13:11:00 +00002022-08-08T11:48:01.639-05:00The Godfather of Complexity<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto;"><tbody><tr><td style="text-align: center;"><a href="https://news.cornell.edu/sites/default/files/styles/story_thumbnail_xlarge/public/rmc2005_0803-cornell-library-archive-a_0.jpg?itok=aVzB0Cnw" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="450" data-original-width="800" height="225" src="https://news.cornell.edu/sites/default/files/styles/story_thumbnail_xlarge/public/rmc2005_0803-cornell-library-archive-a_0.jpg?itok=aVzB0Cnw" width="400" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Juris Hartmanis 1928-2022</td></tr></tbody></table><br />On Friday, July 29th, I was in the immigration line at an airport in Mexico. My phone rang with Bill Gasarch on the Caller ID but starting vacation I declined the call. The voicemail gave me the sad news that Juris Hartmanis, the person who founded computational complexity and brought me into it passed away earlier that day. I messaged Bill and told him to write <a href="https://blog.computationalcomplexity.org/2022/07/juris-hartmanis-passed-away-on-july-29.html">an obit</a> and I'd follow with something personal when I returned.<br /><br /><div style="text-align: center;"><br /></div><div><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="http://1.bp.blogspot.com/-sMoKiQvVwB8/VVEMTLT-beI/AAAAAAAA2VQ/LMLeAxFklRg/s1600/GE.jpg" style="clear: right; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="281" src="http://1.bp.blogspot.com/-sMoKiQvVwB8/VVEMTLT-beI/AAAAAAAA2VQ/LMLeAxFklRg/s400/GE.jpg" width="400" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Hartmanis and Stearns in 1963</td></tr></tbody></table><div><br /></div><div>In November 1962 Hartmanis, working with Richard Stearns at the GE Labs in Schenectady, determined how to use Turing machines to formalize the basic idea to measure resources, like time and memory, as a function of the problem being solved. Their classic Turing-award winning paper <a href="https://www.ams.org/journals/tran/1965-117-00/S0002-9947-1965-0170805-7/S0002-9947-1965-0170805-7.pdf">On the Computational Complexity of Algorithms</a>, not only gave this formulation but showed that increasing resources increased the problems one can solve. The photo above, from <a href="https://blog.computationalcomplexity.org/2015/05/fiftieth-anniversary-of-publication-of.html">a post celebrating the 50th anniversary of the paper</a>, shows Hartmanis and Stearns with the main theorem of their paper on the board.</div><div><br /></div><div>Twenty-one years later, a junior at Cornell University still trying to find his way took undergraduate theory from the man himself. Juris brought the topics to life and I found my passion. At the beginning of the class, he said the highest grade usually went to an undergrad followed by the grad students in the class. I was a counterexample, as I had the second highest grade. Never did find out who beat me out.</div><div><br /></div><div>In spring of my senior year, 1985, I forgave the traditional senior-slump <i>Wines</i> for graduate complexity with Juris. He focused the course around the <a href="https://blog.computationalcomplexity.org/2003/03/berman-hartmanis-isomorphism.html">isomorphism conjecture</a> he developed with his student Len Berman, which implied P≠NP, and Hartmanis believed using the conjecture might lead to settling P v NP. He offered an automatic A to anyone who could prove the isomorphism conjecture. I guess any other proof of P≠NP only warranted a B?</div><div><br /></div><div>I would later be obsessed by the isomorphism conjecture as an assistant professor, coming up with not <a href="http://doi.org/10.1137/S0097539793248305">one</a> but <a href="http://doi.org/10.1145/276698.276737">two</a> oracles making it true. The isomorphism conjecture didn't end up settling P vs NP, but then again neither did any other approach.</div><div><br /></div><div>It wasn't just me, there was a reason that many of the great American complexity theorists, including Ryan Williams, Scott Aaronson and my own PhD advisor Michael Sipser, were undergrads at Cornell. <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/hartmanisstud.pdf">Many more</a> were PhD students of Hartmanis.</div><div><br /></div><div>Juris Hartmanis had a certain gravitas in the community. Maybe it was his age, the way he dressed up, his seminal research in the field, or just that Latvian accent. He founded the CS department at Cornell in the 60s and served as head of the CISE directorate at the National Science Foundation in the 90s. His 60th birthday party at the 3rd Structures in Complexity conference (now the Computational Complexity Conference) was the only time I've seen complexity theorists in ties.</div><div><br /></div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto;"><tbody><tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRPQ7nB0GfMGvRD0sysZK398h6M_WyYoyNQwY2-5Bq5vCQfYpQaHyYnxfc1ZQQI-mvMvRQhTXBmh09tGY0LiszZKF7L_DRPr3wsKueny2Vq3DANV4dvbY4PbI_aCjICb2tXwOCXOsiQzghaoc1aeplK9Txg8OybEtZ_7Se8aGK1Sfo0x9Agg/s354/Hartmanis.png" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="256" data-original-width="354" height="231" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRPQ7nB0GfMGvRD0sysZK398h6M_WyYoyNQwY2-5Bq5vCQfYpQaHyYnxfc1ZQQI-mvMvRQhTXBmh09tGY0LiszZKF7L_DRPr3wsKueny2Vq3DANV4dvbY4PbI_aCjICb2tXwOCXOsiQzghaoc1aeplK9Txg8OybEtZ_7Se8aGK1Sfo0x9Agg/s320/Hartmanis.png" width="320" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Juris Hartmanis (center) being toasted by Janos Simon</td></tr></tbody></table><br /><div>A few of my favorite Hartmanis quotes.</div><div><ul style="text-align: left;"><li>"We all know P is different than NP. We just don't know how to prove it." - Still true.</li><li>"I only make mistakes in the last five minutes of the class." - Sometimes he made a mistake with ten minutes left but only admit it in the last five minutes.</li><li>"Primality is a problem not yet know to be in P but is hanging on by its fingernails with its grip continuing to loosen each day." - Juris Hartmanis said this in 1986, with primality hanging on for another 16 years.</li></ul></div><div>Thanks Juris for creating the foundations of our field and inspiring so many people, yours truly included, to dedicate ourselves to it.</div><div><br /></div><div>Much more to read:</div><div><ul style="text-align: left;"><li>In 1981 Hartmanis wrote a personal <a href="https://doi.org/10.1109/MAHC.1981.10005">article</a> for the Annals of History of Computing describing the birth of computational complexity and his role in it.</li><li>A CACM interview with Hartmanis gives a <a href="https://cacm.acm.org/magazines/2015/4/184690-an-interview-with-juris-hartmanis/fulltext">personal story</a> of his path from Latvia to Kansas City to Pasadena to Schenectady to Ithaca and DC.</li><li>Obits by <a href="https://news.cornell.edu/stories/2022/08/juris-hartmanis-first-cs-department-chair-dies-94">Cornell</a>, <a href="https://scottaaronson.blog/?p=6622">Ryan Williams</a> and <a href="https://rjlipton.wpcomstaging.com/2022/07/29/juris-hartmanis-1928-2022/">Dick Lipton and Ken Regan</a>.</li><li>My old blog posts celebrating <a href="https://blog.computationalcomplexity.org/2018/07/happy-90th-juris.html">Hartmanis' 90th birthday</a> and the <a href="https://blog.computationalcomplexity.org/2015/05/fiftieth-anniversary-of-publication-of.html">50th anniversary of Hartmanis-Stearns</a>,</li><li>And the many retrospectives, remembrances, special issues and conferences to come.</li></ul></div></div>https://blog.computationalcomplexity.org/2022/08/the-godfather-of-complexity.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-1878753039794185378Sun, 07 Aug 2022 12:21:00 +00002022-08-07T07:21:27.151-05:00The Held Prize for comb. opt. AND Disc Opt AND Alg AND Complexity theory AND related parts of CS.<p> Dan Spielman asked me to blog about the Held Prize. I first present what he send me, and then have some thoughts.</p><p><br /></p><p>FROM DAN: </p><p>--------------------------------------------------------------------------------------------------</p><p>Nominations are now being accepted for the National Academy of Sciences’ 2023 Michael and Sheila Held Prize. The Held Prize honors outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complexity theory. This $100,000 prize is intended to recognize recent work (defined as published within the last eight years). Additional information, including past recipients, eligibility requirements, and more, can be found at <a href="http://www.nasonline.org/programs/awards/michael-and-sheila-held-prize.html">here</a>.</p><p>All nominations must be submitted online. Unless otherwise stated, the following materials must be submitted: </p><p>A letter from the nominator describing the candidate's work and why he or she should be selected for the award. No more than three (3) pages.</p><p>Curriculum vitae. No more than two (2) pages (similar to CVs included with NSF proposals).</p><p>Bibliography listing no more than twelve (12) of the nominee's most significant publications.</p><p>Suggested citation. A 50-word summary stating why the nominee should be considered for this award. (Citation</p><p>examples)</p><p>Two letters of support. Support letters must be written by individuals from institutions outside both the</p><p>nominator's and the nominee’s institution. Up to three letters of support are accepted.</p><p>Nominations will be accepted through Monday, October 3, 2022. Please help spread the word that the nomination process is underway. </p><p>----------------------------------------------------------------------------------------------------</p><p>BILL COMMENTS</p><p>1) The scope seems rather broad (Dan confirmed this in private email) in that its Comb Opt AND Discrete Opt OR related fields like algorithms and complexity theory. </p><p>2) The research has to be Outstanding AND Innovative AND creative AND influential. That seems hard to do :-( If they made it an OR instead of an AND I may ask someone to nominate me for my Muffin Work. It does use 0-1 programming!</p><p>3) The past winners are, of course, very impressive. But there is one I want to point out to emphasize that the scope is broad: Amit Sahai won in 2022, and here is what the webpage says about it:</p><p>For a leading role in development of cryptographic Software Obfuscation and its applications, starting from initial conception of "Indistinguishability Obfuscation" and culminating in new constructions based upon well-founded cryptographic assumptions. These breakthroughs highlight how computational complexity can enable secrecy while computing in insecure environments.</p><p>4) Comb Opt and Discrete Opt seem to be Operations Research. So this inspires the following question:</p><p><i>What are the similarities and differences between Operations Research and Research on Algorithms?</i> </p><p>I tend to think of Operations Research as being more tied to the real world- but is that true?</p><p>5) Not enough 2-letter combinations for what you want to say: I had to use the term <i>Operations Research </i>instead of the abbreviation OR since I was using OR for or. Oh well. </p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2022/08/the-held-prize-for-comb-opt-and-disc.htmlnoreply@blogger.com (gasarch)0tag:blogger.com,1999:blog-3722233.post-1587140923174173168Sat, 30 Jul 2022 16:09:00 +00002022-07-30T19:17:28.303-05:00Juris Hartmanis passed away on July 29 at the age of 94<p> Juris Hartmanis, one of the founders of Complexity Theory, passed away on July 29 at the age of 94. The Gödel's Last Letter blog has an obit posted <a href="https://rjlipton.wpcomstaging.com/">here</a>. Scott Aaronson has some words and a guest post by Ryan Williams <a href="https://scottaaronson.blog/?p=6622">here</a>. When other bloggers post obits I will update this paragraph to point to them. </p><p>Here is one non-blog obit: <a href="https://usobit.com/obituaries-2022/juris-hartmanis-july-5-1928-july-29-2022-age-94/">here</a>. For an interview with Juris see <a href="https://dl.acm.org/doi/pdf/10.1145/2736346">here</a>.</p><p>Hartmanis and Stearns shared the 1993 Turing award for the paper <i>On the Computational Complexity of</i> <i>Algorithms </i>(see <a href="https://www.ams.org/journals/tran/1965-117-00/S0002-9947-1965-0170805-7/S0002-9947-1965-0170805-7.pdf">here</a> for the paper and see <a href="https://doi.org/10.1145/194313.214781">here</a> for his Turing Award Talk). In that paper they define DTIME(T(n)) for Turing Machines. They also proved some theorems about how changes to the model (1-tape, 2-tape, 1-dim, 2-dim others) change the notion of DTIME(T(n))- so they were well aware that the definition was not robust. They also have some theorems about computable numbers. </p><p>We are used to the notion that you can measure how long a computation takes my counting the number of steps on a Turing Machine. Before the Hartmanis-Stearns paper this was not how people thought of things. Knuth (I suspect independently) was looking at what we might now call concrete complexity- how many operations does an algorithm need. Hartmanis-Stearns were beginning what is now called Complexity Theory. </p><p> Recall that later, the Cook-Levin Theorem used Turing Machines. </p><p>If Hartmanis-Stearns did not start the process of putting complexity on a rigorous mathematical basis how might complexity theory have evolved? It is possible we would not have the Cook-Levin Theorem or the notion of NP. It is possible that we would ASSUME that SAT is hard and use that to get other problems hard, and also do reverse reductions as well to get some problems equivalent to SAT. Indeed- this IS what we do in other parts of theory with assuming the following problems are hard (for various definitions of hard): 3SUM, APSP, Unique Games. And in Crypto Factoring, DL, SVP, and other problems. </p><p>Hartmanis did other things as well. I list some of them that are of interest to me - other people will likely list other things of interest to them. </p><p>0) He had 21 PhD Students, some of them quite prominent. The list of them is <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/hartmanisstud.pdf">here</a>.</p><p>1) The Berman-Hartmanis Conjecture: All NP-Complete sets are poly isomorphic. Seems true for all natural NP-complete sets. Still open. This conjecture inspired a lot of work on sparse sets including that if a sparse set S is btt-hard for NP, then P=NP (proven by Ogiwara-Watanabe)</p><p>2) The Boolean Hierarchy: we all know what NP is. What about sets that are the <i>difference </i>of two NP sets? What about sets of the form A - (B-C) where A,B,C are all in NP? These form a hierarchy. We of course do not know if the hierarchy is proper, but if it collapse then PH collapses.</p><p>3) He helped introduce time-bounded Kolmogorov complexity into complexity theory, see <a href="https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4568108">here</a>.</p><p>4) He was Lance Fortnow's undergraduate advisor. </p><p>5) There is more but I will stop here.</p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2022/07/juris-hartmanis-passed-away-on-july-29.htmlnoreply@blogger.com (gasarch)6tag:blogger.com,1999:blog-3722233.post-6792824547495697148Sun, 24 Jul 2022 22:46:00 +00002022-07-24T17:46:24.151-05:00100 Best Number Theory books of all Time---except many are not on Number TheoryI was recently emailed this link:<div><br /></div><div><a href="https://bookauthority.org/books/best-number-theory-books">100 Best Number Theory books of all Time</a><br /></div><div><br /></div><div>That sounds like a good list to have! But then I looked at it. </div><div><br /></div><div>The issue IS NOT that the books on it are not good. I suspect they all are.</div><div><br />The issue IS that many of the books on the list are not on Number Theory.</div><div><br /></div><div>DEFINITLY NOT:</div><div><br /></div><div>A Mathematicians Apology by Hardy</div><div><br /></div><div>The Universe Speaks in Numbers by Farmelo (looks like Physics)</div><div><br /></div><div>Category theory in Context by Riehl</div><div><br /></div><div>A First Course in Mathematical logic and set theory by O'Leary</div><div><br />Astronomical Algorithms by Meeus (Algorithms for Astronomy)</div><div><br /></div><div>Pocket Book of Integrals and Math Formulas by Tallardia</div><div><br /></div><div>Entropy and Diversity by Leinster</div><div><br /></div><div>BORDERLINE:</div><div><br />Too many to name, so I will name categories (Not the type Riehl talks about)</div><div><br /></div><div>Logic books. Here <i>Number Theory </i> seems to mean <i>Peano Arithmetic</i> and they are looking at what you can and can't prove in it. </div><div><br /></div><div>Combinatorics books: Indeed, sometimes it is hard to draw the line between Combinatorics and Number Theory, but I still would not put a book on <i>Analytic Combinatorics o</i>n a list of top books in Number Theory. </div><div><br /></div><div>Discrete Math textbooks: Yes, most discrete math textbooks have some elementary number theory in them, but that does not make them number theory books.</div><div><br /></div><div>Abstract Algebra, Discrete Harmonic Analysis, other hard math books: These have theorems in Number Theory as an Application. But they are not books on number theory. </div><div><br />WHAT OF ALL THIS? </div><div><br /></div><div>Lists like this often have several problems</div><div><br /></div><div>1) The actual object of study is not well defined.</div><div><br /></div><div>2) The criteria for being good is not well defined.</div><div><br /></div><div>3) The list is just one person's opinion. If I think the best math-novelty song of all time is William-Rowan-Hamilton (see <a href="https://www.youtube.com/watch?v=SZXHoWwBcDc">here</a>) and the worse one is the Bolzano--Weierstrass rap (see <a href="https://www.youtube.com/watch?v=dfO18klwKHg&t=8s">here</a>) that's just my opinion. Even if I was the leading authority on Math Novelty songs and had the largest collection in the world, its still just my opinion. (Another contender for worst math song of all time is <a href="https://www.youtube.com/watch?v=4xQFlsK7jKg&t=10s">here</a>.)</div><div><br /></div><div>4) Who is the audience for such lists? For the Number Theory Books is the audience ugrad math majors? grad math majors? Number Theorists? This needs to be well defined.</div><div><br /></div><div>5) The list may tell more about the people making the list then the intrinsic qualify of the objects. This is more common in, say, the ranking of presidents. My favorite is Jimmy Carter since he is the only one with the guts to be sworn in by his nickname Jimmy, unlike Bill Clinton (sworn in as William Jefferson Clinton- a name only used by his mother when she was mad at him) or Joe Biden (sworn in as Joseph Robinette Biden which I doubt even his mother ever used). My opinion may seem silly, but it reflects my bias towards nicknames, just as the people who rank presidents use their bias. </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/2022/07/100-best-number-theory-books-of-all.htmlnoreply@blogger.com (gasarch)1tag:blogger.com,1999:blog-3722233.post-798583255902437127Thu, 21 Jul 2022 02:30:00 +00002022-07-20T21:30:26.065-05:00What is known about that sequence<p> In my last post I wrote:</p><p><br /></p><p>---------------------------</p><div>Consider the recurrence</div><div><br /></div><div><br /></div><div>a_1=1</div><div><br /></div><div>for all n\ge 2, a_n = a_{n-1} + a_{n/2}.</div><div><br /></div><div>For which M does this recurrence have infinitely many n such that a_n \equiv 0 mod M?</div><div><br /></div><div><br /></div><div>I have written an open problems column on this for SIGACT News which also says</div><div>what is known (or at least what I know is known). It will appear in the next issue.</div><div><br /></div><div>I will post that open problems column here on my next post.</div><div><br />Until then I would like you to work on it, untainted by what I know. </div><div>----------------------------------------</div><div><br />I will now say what is known and point to the open problems column, co-authored with Emily Kaplitz and Erik Metz. </div><div><br /></div><div>If M=2 or M=3 or M=5 or M=7 then there are infinitely many n such that a_n \equiv 0 mod M</div><div><br />If M\equiv 0 mod 4 then there are no n such that a_n \equiv 0 mod M</div><div><br /></div><div>Empirical evidence suggests that</div><div><br /></div><div>If M \not\equiv 0 mod 4 then there are infinitely many n such that a_n\equiv 0 mod M</div><div><br /></div><div>That is our conjecture. Any progress would be good- for example proving it for M=9. M=11 might be easier since 11 is prime. </div><div><br /></div><div>The article that I submitted is <a href="https://www.cs.umd.edu/~gasarch/open/cseq.pdf">HERE</a></div>https://blog.computationalcomplexity.org/2022/07/what-is-known-about-that-sequence.htmlnoreply@blogger.com (gasarch)0tag:blogger.com,1999:blog-3722233.post-4813311592001744524Tue, 19 Jul 2022 02:52:00 +00002022-07-20T21:25:02.011-05:00An open question about a sequence mod M. In this post n/2 means floor{n/2}<div><br /></div><div>Consider the recurrence</div><div><br /></div><div><br /></div><div>a_1=1</div><div><br /></div><div>for all n\ge 2, a_n = a_{n-1} + a_{n/2}.</div><div><br /></div><div>For which M does this recurrence have infinitely many n such that a_n \equiv 0 mod M?</div><div><br /></div><div><br /></div><div>I have written an open problems column on this for SIGACT News which also says</div><div>what is known (or at least what I know is known). It will appear in the next issue.</div><div><br /></div><div>I will post that open problems column here on my next post.</div><div><br />Until then I would like you to work on it, untainted by what I know. </div><div><br /></div><div>ADDED LATER: I have now posted the sequel which includes a pointer to the open problems column. To save you time, I post it <a href="https://www.cs.umd.edu/~gasarch/open/cseq.pdf">here</a> as well.</div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div>https://blog.computationalcomplexity.org/2022/07/an-open-question-about-sequence-mod-m.htmlnoreply@blogger.com (gasarch)11tag:blogger.com,1999:blog-3722233.post-3528238240939023029Tue, 12 Jul 2022 01:22:00 +00002022-07-11T20:22:47.406-05:00Review of The Engines of Cognition: Essays From the LessWrong Forum/Meta question about posts<p> A while back I reviewed<i> A Map that Reflects the Territory</i> which is a collection of essays posted on the lesswrong forum. My review is <a href="https://www.cs.umd.edu/~gasarch/bookrev/FRED/lesswrong.pdf">here</a>. I posted it to both this blog and to the lesswrong forum. In both cases I posted a link to it. My post to lesswrong is <a href="https://www.lesswrong.com/posts/JXTEDFCC5r4dW2tta/review-of-a-map-that-reflects-the-territory">here</a></p><p>On the lesswrong post many of the comments, plus some private emails, told me NO BILL- don't post a link, post it directly as text. It was not clear how to do that, but I got it done with help.</p><p>On complexity blog nobody commented that this was a problem. Then again, nobody commented at all, so its not clear what to make of that. </p><p>So</p><p>Meta Question: Is posting a link worse than posting direct text? Note that the book review was 12 pages long and looked great in LaTeX. </p><p>Meta Question: Why did lesswrong care about the format but complexityblog did not (Probably answer: omplexityblog readers did not care at all, whereas Lesswrong cared about what I though about Lesswrong)</p><p>Another Question, not Meta. One of the comments was (I paraphrase)</p><p><i>When I open a pdf file I expected to see something in the style of an academic paper. This is written in very much chatty, free-flowing blog post style with jokes like calling neologisms ``newords'', so the whole think felt more off-kilter than was intended. The style of writing would prob work better as an HTML blog post (which could then be posted directly as a Lesswrong post here instead of hosted elsewhere and linked.)</i></p><p>I think its interesting that the format of an article telegraphs (in this case incorrectly) what type of article it will be. Is this a common problem? I have had the experience of reading a real academic paper and being surprised that some joke or cultural-reference is in it, though I do not object to this. </p><p>Another comment and question</p><p><i>I was surprised the post only had 11 karma when I saw it (William had send me an advance copy and I'd really liked reading it) but when I saw that it was a link post, I understood why.</i></p><p>I find this hilarious- they have some way the posts are rated! For one, Lance told me very early on to never worry about comments, and I don't. Second, it reminds me of the Black Mirror episode <a href="https://en.wikipedia.org/wiki/Nosedive_(Black_Mirror)">Nosedive</a>.</p><p>ANYWAY, I have reviewed another collection of essays for less wrong, this one called <i>The Engines of</i> <i>Cognition. </i>I am posting it here as a link: <a href="https://www.cs.umd.edu/~gasarch/bookrev/FRED/lesswrong2.pdf">here</a> and I will post it on lesswrong as full text (with help) in a few days. </p><p>I am posting it so I can get comments before I submit it to the SIGACT News book review column. But this is odd since I think this blog has more readers than SIGACT news has subscribers, so perhaps THIS is its real debut, not that. And of course the lesswrong forum is a place where more will read it since its about them. </p><p>So- I appreciate comments to make it a better review!</p><p><br /></p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2022/07/review-of-engines-of-cognition-essays.htmlnoreply@blogger.com (gasarch)9tag:blogger.com,1999:blog-3722233.post-8754111030570733183Wed, 06 Jul 2022 12:29:00 +00002022-07-06T07:29:23.781-05:00The Highland Park Shooting<p>This week I should be celebrating Mark Braverman's <a href="https://www.quantamagazine.org/mark-braverman-wins-the-imu-abacus-medal-20220705/">Abacus Medal</a> and the <a href="https://www.quantamagazine.org/tag/2022-fields-and-abacus-medals/">Fields Medalists</a>. Instead my mind has been focused 25 miles north of Chicago.</p><p>Mass shootings in the United States have become far too commonplace, but the shooting at a fourth of July parade in Highland Park, Illinois hit home. Literally Highland Park was home for me, from 2003-2012. We've been in downtown Highland Park hundreds of times. We've attended their fourth of July parade in the past. My daughter participated in it as part of the high school marching band. </p><p>We were members of North Shore Congregation Israel. My wife, who had a party planning business back then, worked closely with NSCI events coordinator Jacki Sundhein, tragically killed in the attack.</p><p>We lived close to Bob's Deli and Pantry and we'd often walk over there for sandwiches or snacks, sometimes served by Bob Crimo himself. The alleged shooter, Bobby Crimo, was his son.</p><p>We spent the fourth with friends who came down from Glencoe, the town just south of Highland Park. We spent much of the day just searching for updates on our phones.</p><p>I wish we could find ways to reduce the shootings in Highland Park and those like it, the violence that plagues Chicago and other major cities and the highly polarized world we live in which both hampers real gun reforms and creates online groups that help enable these awful events. But right now I just mourn for the lives lost in the town that was my home, a town that will never fully recover from this tragedy.</p>https://blog.computationalcomplexity.org/2022/07/the-highland-park-shooting.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-3356810276237520801Tue, 28 Jun 2022 16:52:00 +00002022-06-28T11:53:05.911-05:00A Gadget for 3-Colorings <p>Following up on Bill's <a href="https://blog.computationalcomplexity.org/2022/06/counting-number-of-3-colorings-of-graph.html">post earlier this week</a> on counting the number of 3-colorings, <a href="https://www.bbk.ac.uk/our-staff/profile/9044528/steven-noble">Steven Noble</a> emailed us with some updated information. The first proof that counting 3-colorings is #P-complete is in a <a href="https://doi.org/10.1137/0607036">1986 paper</a> by Nati Linial. That proof uses a Turing reduction using polynomials based on posets.</p><p>Steven points to a <a href="https://ora.ox.ac.uk/objects/uuid:52070098-14fa-4cf1-ae6e-9f9ce6a626d8">1994 thesis</a> of James Annan under the direction of Dominic Welsh at Oxford that gives the gadget construction that I so tried and failed to do in Bill's post.</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiQlZ3z-rTCsgF-c7yTH6CuPV6eUG5aFEZjaFFEiy_Z1mjB0EedHG3DsqJtRqWLaSvA6tC2ALi4G-r3GTgI_4ErkfpITXGIr7gNcXUEZtuBUjYdBfyYfN2EyV5zv0j7e5SEJ7YnlUyqLpuO01WF6xVyOIOXTldVJJ9-ps5rqUaa25SVdb6-Rg/s925/3col%20gadget.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="857" data-original-width="925" height="370" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiQlZ3z-rTCsgF-c7yTH6CuPV6eUG5aFEZjaFFEiy_Z1mjB0EedHG3DsqJtRqWLaSvA6tC2ALi4G-r3GTgI_4ErkfpITXGIr7gNcXUEZtuBUjYdBfyYfN2EyV5zv0j7e5SEJ7YnlUyqLpuO01WF6xVyOIOXTldVJJ9-ps5rqUaa25SVdb6-Rg/w400-h370/3col%20gadget.png" width="400" /></a></div><div style="text-align: left;"></div>Think of color 0 as false and color 1 as true and use this gadget in place of the OR-gadgets in the regular NP-complete proof of 3-coloring. I checked all eight values of a, b and c and the gadget works as promised.<div><br /></div><div><a href="https://en.wikipedia.org/wiki/James_Annan">James Annan</a> later became a climate scientist and co-founded <a href="https://bskiesresearch.wordpress.com/">Blue Skies Research</a> in the UK. </div><div><br /></div><div><div>Steven also noted that counting 2-colorings is easy, because for each connected component, there are either 0 or 2 colorings.</div></div>https://blog.computationalcomplexity.org/2022/06/a-gadget-for-3-colorings.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-7823378841072893249Sun, 26 Jun 2022 19:00:00 +00002022-06-28T11:56:46.475-05:00Counting the Number of 3-colorings of a graph is Sharp-P complete. This should be better known.<p>(ADDED LATER- Lance and I were emailed more information on the topic of this post, and that was made into a post by Lance which is <a href="https://blog.computationalcomplexity.org/2022/06/a-gadget-for-3-colorings.html">here</a>.) </p><p><br /></p><p>BILL: Lance, is #3COL #P complete? (#3COL is: Given a graph G, return the number of different 3-colorings it has.) </p><p>LANCE: Surely you know that for all natural A, #A is #P complete. </p><p>BILL: There is no rigorous way to define <i>natural</i>. (I have several blog posts on this.) </p><p>LANCE: Surely then for all the NP-complete problems in <a href="https://amzn.to/3OiaKHb">Garey & Johson</a>.</p><p>BILL: I know that. But is there a proof that 3COL is #P Complete? I saw a paper that claimed the standard proof that 3-COL is NPC works, but alas, it does not. And stop calling me Shirley.</p><p>LATER</p><p>LANCE: I found this cool construction of an OR gate that creates a unique coloring.</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhXFZ_HG2ctfXyZPtF4TzkPf4gJni9XgTrsrfyy07yzdDJ5Faq0UuNYPWkS2yRd6g0SyFV6vbIKWqVtkgxzVB9ZKF-hqFUcBjzuQOQAFdWxILWQFZVZRPPB8XxcxjZckcaNXyulb6AfK4bGT-wY95sJyiS-sICaMRnhcA0fwek3Nv01WYu6pQ/s1672/unnamed.jpg" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="1672" data-original-width="1159" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhXFZ_HG2ctfXyZPtF4TzkPf4gJni9XgTrsrfyy07yzdDJ5Faq0UuNYPWkS2yRd6g0SyFV6vbIKWqVtkgxzVB9ZKF-hqFUcBjzuQOQAFdWxILWQFZVZRPPB8XxcxjZckcaNXyulb6AfK4bGT-wY95sJyiS-sICaMRnhcA0fwek3Nv01WYu6pQ/w139-h200/unnamed.jpg" width="139" /></a></div><br /><p></p><p>LATER</p><p>LANCE: That didn't work because you need to take an OR of three variables. OK, this isn't that easy.</p><p>LATER</p><p>LANCE: I found an unpublished paper (its not even in DBLP) that shows #3-COL is #P complete using a reduction from NAE-3SAT, see <a href="https://www.cs.umd.edu/~gasarch/BLOGPAPERS/3colsharpp.pdf">here</a>. The proof was harder than I thought it would be. </p><p>BILL: Great! I'll post about it and give the link, since this should be better known. The link is <a href="https://www.cs.umd.edu/~gasarch/BLOGPAPERS/3colsharpp.pdf">here</a>.</p><p>-----------------------------</p><p>This leads to a question I asked about 2 years ago on the blog (see <a href="https://blog.computationalcomplexity.org/2020/08/sharp-p-and-issue-of-natural-problems.html#comment-form">here</a>) so I will be brief and urge you to read that post.</p><p>a) Is every natural NPC problem also #P-complete. Surely yes though this statement is impossible to make rigorous. </p><p>b) Is there some well defined class LANCE of LOTS of NPC problems and a theorem saying that for every A in LANCE, #A is #P complete? The last time I blogged about this (see above pointer) a comment pointed me to a cs stack exchange <a href="https://cstheory.stackexchange.com/questions/16119/when-does-x-is-np-complete-imply-x-is-p-complete">here</a> that pointed to an article by Noam Levine, <a href="https://www.cs.umd.edu/~gasarch/BLOGPAPERS/NLsharpp.pdf">here</a> which has a theorem which is not quite what I want but is interesting. Applying it to 3COL it says that there is a NTM poly time M that accepts 3COL and #M is #P-complete. <br />Not just 3COL but many problems. </p><p>c) Is there some reasonable hardness assumption H such that from H one can show there is a set A that is NP-complete that is NOT #P-complete? (The set A will be contrived.) </p><p>ADDED LATER: Is #2-COL known to be #P-complete? This really could go either way (P or #P-complete) since some problems in P have their #-version in P, and some have their #-version be #P-complete.</p>https://blog.computationalcomplexity.org/2022/06/counting-number-of-3-colorings-of-graph.htmlnoreply@blogger.com (gasarch)1tag:blogger.com,1999:blog-3722233.post-4213949930505395862Sun, 19 Jun 2022 19:08:00 +00002022-06-19T14:10:54.875-05:00Guest post by Prahalad Rajkumar: advice for grad students<p>I suspect that Lance and/or I have had blogs giving advice to grad students. I won't point to any particular posts since that's a hard thing to search for. However, they were all written WAY AFTER Lance and I actually were grad students. Recently a former grad student at UMCP, Prahalad Rajkumar, emailed me that he wanted to do a post about advice for grad students. Since he has graduated more recently (Master degree in CS, topic was Monte Carlo Techniques, in 2009, then a job as a programmer-analyst) his advice may be better, or at least different, than ours was.</p><p>Here is his guest post with an occasional comment by me embedded in it. </p><p>----------------------------</p><p> <b>I Made this Fatal Mistake when I Joined a Graduate Program at Maryland</b></p><p>Getting accepted to a graduate program in a good school is an honor.</p><p>It is also an opportunity to do quality work and hone your skills. I made one fatal mistake at the start of my master’s degree at the University of Maryland which took me down a vicious rabbit hole. I believed that I was not cut out for this program.</p><p><b>The Only Person Who Gave an Incorrect Answer</b></p><p>Before the start of my graduate studies, there was an informal gathering held for newer students and some faculty members. A faculty member asked a basic algorithm question.</p><p>Everyone in the room gave one answer. I gave another answer.</p><p>This is real life and not Good Will Hunting, and of course, I was wrong. I had misunderstood the question. It would have been a simple matter to shrug and move forward. But the paternal voice in my head saw a good opportunity to continue to convince me that I was an imposter who did not belong here.</p><p><b>Who is Smarter than Whom?</b></p><p>Some of my fellow incoming graduate students, who TAed with me for Bill Gasarch’s class, played an innocent looking game.</p><p>“That guy is so smart”.</p><p>“I wish I were as smart as her”.</p><p>They couldn’t know that this would affect me. I too did not know that this could affect me. But it did. I asked myself “Am I smarter than person X?”. Each time, the paternal voice in my head was quick to answer “No”. And each time I took this “No” seriously.</p><p>NOTE FROM BILL: Professors also play <i>who is smarter than who</i> game and we shouldn't.</p><p><b>I Didn’t Choose My Classes Wisely</b></p><p>I made a few mistakes in choosing my classes. I chose Concrete Complexity with Bill, which I later realized I had no aptitude for. I chose an undergraduate class taught by a professor whose style did not resonate with me. Mercifully, I chose a third class that I liked and excelled in. A class which did not destroy my confidence.</p><p>In retrospect, though I chose a couple of classes that were not my cup of tea, I compounded my problems with the stories I told myself. I had several good options available to me. I could redouble my efforts in the said classes and give it my best shot. I could accept my inevitable “B” grades in these classes, and be mindful to choose better classes in the upcoming semesters.</p><p>I, however, did the one thing I should not have done: I further convinced myself that I was not cut out to be a graduate student.</p><div>NOTE FROM BILL: Some students wisely ask around to find out <i>who is a good teacher</i>? Prahalad points out that this is just the first question. A class may be appropriate for you or not based on many factors, not just if the instructor is a <i>good teacher.</i> </div><div><div><br /></div><div><b>I Fell Victim to Impostor Syndrome</b></div><div><br /></div><div>I kept compounding my woes in my second and third semesters. Things got bad -- I took up a position as a research assistant in my third semester. My confidence was low -- and I struggled to do basic tasks that fall under my areas of competence.</div><div><br /></div><div>In my fourth semester, I convinced myself that I could not code. In a class project where I had to do some coding as a part of a group project, I struggled to write a single line of code.</div><div><br /></div><div>When I confessed this to one of my group members, he got me out of my head. He got me to code my part more than capably. I’ve written about this experience <a href="https://os.me/short-stories/the-impostor-syndrome/">here</a>.</div><div><br /></div><div><br /></div><div><b> It Does Not Matter in the Slightest</b></div><div><br /></div><div>I wish I could tell the 2007 version of myself the following: It doesn’t matter who is smarter than whom. In any way whatsoever. We are on our individual journeys. In graduate school. In life.</div><div><br /></div><div>Comparing myself with another person is as productive as playing several hours of angry birds.</div><div><b><br /></b></div><div><b> The Admission Committee Believed in Me.</b></div><div><br /></div><div>There was one good reason I should have rejected the thought that I did not belong in the program. The admission committee believed that I belonged here. Consisting of several brilliant minds. If they thought I should be here, why should I second guess them?</div><div><br /></div><div>NOTE FROM BILL: While the Admissions committee DID believe in Prahalad and was CORRECT in this, I would not call the committee <i>brilliant</i>. As is well known, the IQ of a committee is the IQ of its dumbest member divided by the number of people on the committee. </div><div><br /></div><div><b>Bill Gasarch’s Secret Sauce</b></div><div><br /></div><div>Since I took a class with Bill and TAed for him, I had occasion to spend a lot of time with Bill.</div><div>In one conversation, Bill told me something profound. He told me the secret sauce behind his accomplishments. No, it was not talent. It was his willingness to work as hard as it takes.</div><div>And working hard is a superpower which is available to anyone who is inclined to invoke it. I wish I had.</div><div><br /></div><div>BILL COMMENT: The notion that hard work is important is of course old. I wonder how old. One of the best expressions of this that I read was in a book <i>Myths of Innovation</i> which said (a) Great ideas are over rated, (b) hard work and follow through are underrated. There are more sources on this notion in the next part of Prahalad's post. (Side Note- I got the book at the <i>Borders Books Going</i> <i>Out of Business Sale</i>. Maybe they should have read it.) </div><div><br /></div></div><div><div><br /></div><div><b>Talent is Overrated.</b></div><div><br /></div><div>I read a few books in the last couple of years that discussed the subject of mastery: Mastery by Robert Greene, Peak by Anders Ericsson, Talent is Overrated by Geoff Colvin, The Talent Code by Daniel Coyle, Grit by Angela Duckworth, Mindset by Carol Dweck</div><div><br /></div><div>There was one point that all of these books made: talent is not the factor which determines a person’s success. Their work ethic, their willingness to do what it takes, and several hours of deliberate practice is the secret of success. Of course, talent plays a part -- you can’t be 5’1 and hope to be better than Michael Jordan. But in the graduate school setting, where a majority are competent, it really is a matter of putting in the effort.</div><div><br /></div><div><b> Follow the Process</b></div><div><br /></div><div>Bill Walsh signed up as the coach of the languishing 49ers football team. The title of his bestselling book describes his coaching philosophy: The Score Takes Care of Itself. He established processes. Focusing on the smallest of details. Walsh made everyone in the football team and in the administrative departments follow their respective processes. Long story short: <i>the score took care of itself</i>. The 49ers won 3 super bowls among other impressive performances.</div><div><br /></div><div>If I had to do it all again: I would get out of my head. And keep going with a disciplined work ethic. Establish a process. Follow the process. And let the results take care of themselves.</div><div><br /></div><div><b><br /></b></div><div><b>All’s Well That Ends Well</b></div><div><br /></div><div>I grinded and hustled and successfully completed my Masters degree. However, instead of making the journey a joyride, I got in my own way and complicated things for no good reason.</div><div><br /></div><div><b> Final Thoughts</b></div><div><br /></div><div>As William James said, a person can change his life by changing his attitude. All I needed to do was change my thinking -- work hard -- and the “score would have taken care of itself”.</div><div><br /></div><div>I thought I was alone. But I found out in other spheres that a non-negligent percentage of people fall prey to the impostor syndrome. I wanted to write this to help any student who may be going through the problem that I did. If you are going through self-doubt, my message to you is to get out of the head, believe that you are capable (and make no mistake, you certainly are), do the work diligently,</div><div>follow the process, and <i>let the score take care of itself</i>.</div><div><br /></div></div>https://blog.computationalcomplexity.org/2022/06/guest-post-by-prahalad-rajkumar-advice.htmlnoreply@blogger.com (gasarch)0tag:blogger.com,1999:blog-3722233.post-414280661681721253Sun, 12 Jun 2022 18:34:00 +00002022-06-16T14:04:43.286-05:00I am surprised that the Shortest Vector Problem is not known to be NP-hard, but perhaps I am wrong<div><br /></div><div>A lattice L in R^n is a discrete subgroup of R^n. </div><div><br /></div><div>Let p IN [1,infinty)</div><div><br /></div><div>The<i> p-norm of a vector </i>x=(x_1,...,x_n) IN R^n is</div><div><br /></div><div> ||x||_p=(|x_1|^p + ... + |x_n|^p)^{1/p}.</div><div><br /></div><div>Note that p=2 yields the standard Euclidean distance.</div><div><br /></div><div>If p=infinity then ||x||_p=max_{1 LE i LE n} |x_i|.</div><div><br /></div><div>Let p IN [1,infinity]</div><div><br /></div><div>The Shortest Vector Problem in norm p (SVP_p) is as follows:</div><div><br /></div><div>INPUT A lattice L specified by a basis.</div><div><br /></div><div>OUTPUT Output the shortest vector in that basis using the p-norm.</div><div><br /></div><div>I was looking at lower bounds on approximating this problem and just assumed the original problem was NP-hard. Much to my surprise either (a) its not known, or (b) it is known and I missed in in my lit search. I am hoping that comments on this post will either verify (a) or tell me (b) with refs. </div><div><br /></div><div>Here is what I found:</div><div><br /></div><div>Peter van Emde Boas in 1979 showed that SVP_infinity is NP-hard. </div><div>(See <a href="https://cs.stackexchange.com/questions/33828/np-completeness-of-closest-vector-problem">here</a> for a page that has a link to the paper. I was unable to post the link directly. Its where it says <i>I found</i> <i>the original paper.) </i>He conjectured that for all p GE 1 the problem is NP-hard. </div><div><br /></div><div><br /></div><div>Miklos Ajtai in 1998 showed that SVP_2 is NP-hard under randomized reductions. (See <a href="https://doi.org/10.1145/276698.276705">here</a>)</div><div><br /></div><div>There are other results by Subhash Khot in 2005 (see <a href="https://doi.org/10.1145/1089023.1089027">here</a>) and Divesh Aggarwal et al. in 2021 (see <a href="https://doi.org/10.1137/1.9781611976465.109">here</a>) (Also see the references in those two papers.) about lower bounds on approximation using a variety of assumptions. Aggarwal's paper in unusual in that it shows hardness results for all p except p even; however, this is likely a function of the proof techniques and not of reality. Likely these problems are hard for all p.</div><div><br /></div><div>But even after all of those great papers it seems that the the statement:</div><div><br /></div><div> For all p IN [1,infinity] SVP_p is NP-hard</div><div><br /></div><div>is a conjecture, not a theorem. I wonder if van Emde Boas would be surprised. If he reads this blog, maybe I'll find out. If you know him then ask him to comment, or comment yourself. </div><div><br /></div><div>SO is that still a conjecture OR have I missed something?</div><div><br /></div><div>(Oddly enough, my own blog post <a href="https://blog.computationalcomplexity.org/search?q=shortest+vector">here</a> (item 5) indicates SVP_p is NP-hard; however, </div><div>I have not been able to track down the reference.)</div><div><br /></div>https://blog.computationalcomplexity.org/2022/06/i-am-surprised-that-shortest-vector.htmlnoreply@blogger.com (gasarch)5tag:blogger.com,1999:blog-3722233.post-18307925481231353Sat, 04 Jun 2022 17:03:00 +00002022-06-14T11:18:35.247-05:00Does the Social Media Law in Texas affect theory bloggers? <p>A new law in Texas states that any social media sites that has at least 50 million subscribers a month cannot ban anyone (its more nuanced than that, but that's the drift). </p><p>(I wrote this before the Supreme courts blocked the law, which you can read about <a href="https://nypost.com/2022/05/31/scotus-blocks-texas-law-targeting-social-media-censorship/">here</a>. This is a temporary block so the issue is not settled.) </p><p>Here is an article about the law: <a href="https://www.vox.com/2022/5/12/23068017/supreme-court-first-amendment-twitter-facebook-youtube-instagram-netchoice-paxton-texas">here</a></p><p>My random thoughts</p><p>1) How can any internet law be local to Texas or to any state? I wonder the same thing about the EU's law about right-to-be-forgotten and other restrictions. </p><p>2) Does the law apply to blogs? If Scott had over 50 million readers... <i>Hold that thought. </i>Imagine if that many people cared about quantum computing, complexity theory, the Busy Beaver function, and Scott's political and social views. T<i>hat would be an awesome world!</i> However, back to the point- if he did have that many readers would he not be allowed to ban anyone?</p><p>3) If Lance and I had over 50 million readers... <i>Hold that thought</i>. Imagine if that many people cared about Complexity Theory, Ramsey Theory, <a href="https://blog.computationalcomplexity.org/2022/01/did-betty-white-die-in-2021why-do.html">Betty White</a> and Bill and Lance's political and social views. Would <i>that be an awesome world?</i> I leave that as an open question. However, back to the point- would they be able to block posts like: </p><p> Great Post. Good point about SAT. Click here for a good deal on tuxedos. </p><p>Either the poster thinks that Lance will win a Turing award and wants him to look good for the ceremony, or its a bot. </p><p>4) If Lipton and Regan's GLL blog had over 50 million readers.... <i>Hold that thought</i>. Imagine if that many people cared about Complexity theory, open-mindedness towards P=NP, catching people who cheat at chess, nice things about everyone they mention, and their political and social views. <i>That would</i> <i>be a very polite world! </i>However, back to the point- would they be able to block posts? Block people? </p><p>5) arxiv recently rejected a paper by Doron Zeilberger. This rejection was idiotic, though Doron can argue the case better than I can, so see <a href="https://sites.math.rutgers.edu/~zeilberg/Opinion183.html">here</a> for his version of events (one sign that he can argue better than I can: he does not use any negative terms like <i>idiot.) </i>Under the moronic Texas law, can arxiv ban Doron for life? (of course, the question arises, do they have at least 50 million subscribers?)</p><p>6) Given who is proposing the law its intent is things like <i>you can't kick Donald Trump off Twitter</i>. I wonder if Parler or 8-chan or Truth-Social which claim to be free-speech sites, but whose origins are on the right, would block liberals. Or block anyone? I DO NOT KNOW if they do, but I am curious. If anyone knows please post- no speculation or rumor, I only want solid information. </p><p>7) Republicans default position is to not regulate industry. It is <i>not</i> necessarily a contradiction to support a regulation; however, they would need a strong argument why this particular case needs regulation when other issues do not. I have not seen such an argument; however, if you have one then leave a comment. (The argument <i>they are doing</i> <i>it to please their base </i>is not what I mean- I want a fair objective argument.) </p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2022/06/does-social-media-law-in-texas-affect.htmlnoreply@blogger.com (gasarch)7tag:blogger.com,1999:blog-3722233.post-1695433635483317846Mon, 30 May 2022 05:25:00 +00002022-05-30T00:25:50.154-05:00Discussions I wish we were having<p><br /></p><p>1) Democrats think the best way to avoid school shootings (and other problems with guns) is to have regulations on Guns. They have proposed legislation. The Republicans think its a mental health issue. They have proposed legislation for this. NO THEY HAVEN"T. I would respect the <i>its a mental health</i> <i>issue</i> argument if the people saying this respected it. They do not. See <a href="https://www.kvue.com/article/news/local/report-texas-last-access-mental-health-care/269-1283fcee-0dc4-4948-9dda-886f55c49ca3">here</a>. Idea: Politico should leak a (false) memo by Gov Abbott where he says </p><p><i>We have a serious mental health crisis in Texas which caused the recent event. I am not just saying this to deflect from the gun issue. I have drawn up a bill to fund mental health care, providing more money, for care and for studies. I call on Republicans and Democrats to pass it ASAP.</i></p><p>I wonder- if this false memo was leaked, would he deny it and say </p><p><i>I didn't write that. I am using mental health only as a way to deflect from the gun issue. How dare they say that I am reasonable and am proposing actual solutions. </i></p><p>Or would he be forced to follow through?</p><p>2) Democrats think Biden won the election. Some Republicans think Trump won the election. One issue was Arizona. So some republicans organized a recount of Arizona. And when they found out that Biden really did win it they said, as the good Popperian scientists they are, <i>we had a falsifiable hypothesis and it</i> <i>was shown to be false, so now we acknowledge the original hypothesis was wrong. </i>NO THEY DIDN"T. They seem to point to the Arizona audit as proof that they were right, even though it proves the opposite. (Same for all the court cases they lost.)</p><p>3) At one time I read some books that challenged evolution (Darwin on Trial by Phillip Johnson was one of them). Some of them DID raise some good points about how science is done (I am NOT being sarcastic). Some of them DID raise some questions like the gap in the fossil record and Michael Behe's notion of irreducible complexity. (In hindsight these were window dressing and not what they cared about.) MY thought at the time was <i>its good to have people</i> v<i>iew a branch of science with a different viewpoint. Perhaps the scientists at the Discovery Institute will find something interesting. </i>(The Discovery institute is a think tank and one of their interests is Int. Design.) Alas, the ID people seem to spend their time either challenging the teaching of Evolution in school OR doing really bad science. Could intelligent people who think Evolution is not correct look at it in a different way than scientists do, and do good science, or at least raise good questions, and come up with something interesting? I used to think so. Now I am not so sure.</p><p>4) I wish the debate was <i>what to do about global warming </i>and not <i>is global warming happening? </i>Conjecture: there will come a time when environmentalists finally come around to nuclear power being part of the answer. At that point, Republicans will be against Nuclear power just because the Democrats are for it. </p><p>5) I sometimes get email discussions like the following (I will call the emailer Mel for no good reason.)</p><p>------------------------------------------------------</p><p>MEL: Dr. Gasarch, I have shown that R(5)=45.</p><p>BILL: Great! Can you email me your 2-coloring of K_{44} that has no mono K_5?</p><p>MEL: You are just being stubborn. Look at my proof!</p><p>------------------------------------------------------------</p><p>Clyde has asked me <i>what if Mel had a nonconstructive proof?</i></p><p>FINE- then MEL can tell me that. But Mel doesn't know math well enough to make that</p><p>kind of argument. Here is the discussion I wish we had</p><p>-------------------------------------------</p><p>MEL: Dr. Gasarch, I have shown that R(5)=45.</p><p>BILL: Great! Can you email me your coloring of K_{44} that has no mono K_5?</p><p>MEL: The proof is non-constructive.</p><p>BILL: Is it a probabilistic proof? If so then often the prob is not just nonzero but close to 1. Perhaps you could write a program that does the coin flipping and finds the coloring.</p><p>MEL: The proof uses the Local Lovasz Lemma so the probe is not close to 1.</p><p>BILL: Even so, that can be coded up.</p><p>MEL: Yes but... (AND THIS IS AN INTELLIGENT CONVERSATION)</p><p>----------------------------------</p><p>Maybe Mel really did prove R(5)=44, or maybe not, but the above conversation would lead to</p><p>enlightenment. </p><p><br /></p>https://blog.computationalcomplexity.org/2022/05/discussions-i-wish-we-were-having.htmlnoreply@blogger.com (gasarch)4tag:blogger.com,1999:blog-3722233.post-8785234285731310998Mon, 23 May 2022 02:52:00 +00002022-05-22T21:52:37.699-05:00In the 1960's students protested the Vietnam war!/In 1830 students protested... Math?<p> I was at SUNY Stonybrook for college 1976-1980. </p><p>I remember one student protest about a change to the calendar that (I think) would have us go home for winter break and then come back for finals. I don't recall how that turned out. </p><p>However I had heard about the protests in the 1960's over the Vietnam war. Recall that there was a draft back then so college students were directly affected. </p><p>I was reading a book `<i>Everything you know is wrong'</i> which noted that some people thought the first time there were student protests was in the 1960's but this is not true. (Not quite as startling as finding out that a ships captain cannot perform weddings.) </p><p>It pointed to <i>The 1830 Conic Section Rebellion. </i>I quote Wikipedia (full entry is <a href="https://en.wikipedia.org/wiki/Conic_Sections_Rebellion">here</a>)</p><p><i>Prior to the introduction of blackboards, Yale students had been allowed to consult diagrams in their textbooks when solving geometry problems pertaining to conic sections – even on exams. When the students were no longer allowed to consult the text, but were instead required to draw their own diagrams on the blackboard, they refused to take the final exam. As a result forty-three of the ninety-six students – among them, Alfred Stille, and Andrew Calhoun, the son of John C. Calhoun (Vice Pres a the time) – were summarily expelled, and Yale authorities warned neighboring universities against admitting them.</i></p><p>Random Thoughts</p><p>1) From my 21st century prospective I am on the students side. It seems analogous to allowing students to use calculators-- which I do allow. </p><p>2) From my 21st century prospective the punishment seems unfair. </p><p>3) The notion of a school telling other schools to not admit student- I do not think this would happen now, and might even be illegal (anti-trust).</p><p>4) I am assuming the students wanted to be able to consult their text out of some principle: we want to learn concepts not busy work. And again, from my prospective I agree that it was busy work. </p><p>5) Since all of my thoughts are from a 21st century prospective, they may be incorrect, or at least not as transferable to the 1830 as I think. (Paradox: My ideas may not be as true as I think. But if I think that...) </p><p>6) I try to avoid giving busy work. When I teach Decidability and Undecidability I NEVER have the students actually write a Turing Machine that does something. In other cases I also try to make sure they never have to do drudge work. And I might not even be right in the 21st century- some of my colleagues tell me its good for the students to get their hands dirty (perhaps just a little) with real TM to get a feel for the fact that they can do anything. </p><p>7) The only student protests I hear about nowadays are on political issues. Do you know of any student protests on issues of how they are tested or what the course requirements are, or something of that ilk? I can imagine my discrete math students marching with signs that say: </p><p>DOWN WITH INDUCTION!</p><p><br /></p><p><br /></p><p><br /></p><p><br /></p>https://blog.computationalcomplexity.org/2022/05/in-1960s-students-protested-vietnam.htmlnoreply@blogger.com (gasarch)1tag:blogger.com,1999:blog-3722233.post-6897620455238922302Mon, 16 May 2022 04:41:00 +00002022-05-16T10:07:07.070-05:00Is Kamala Harris our first female PREZ? No. Do I have a theorem named after me. No. But in both cases...<p>On Nov 19, 2021 Joe Biden got a colonoscopy and hence the 25th amendment was used to make Kamala Harris the president temporarily (this source: <a href="https://nypost.com/2021/11/19/biden-returns-to-white-house-after-physical-colonoscopy/">here</a> says 85 minutes, though I thought I heard a few hours from other sources). </p><p>Does this make Kamala Harris our first female president?</p><p>I would say NO and I suspect you agree. A friend of mine suggested the phrasing <i>Kamala Harris is the</i> <i>first women to assume the powers of the president under the 25th amendment. </i>True. I don't think it means much. She tacked on the <i>under the 25th amendment </i>since Edith Wilson was essentially president when Woodrow Wilson had a stroke (see <a href="https://en.wikipedia.org/wiki/Edith_Wilson#Increased_role_after_husband's_stroke">here</a>).</p><p><br /></p><p>A student asked me <i>Is there a theorem that is referred to as Gasarch's Theorem or something like that?</i></p><p>I will answer YES and NO, but really the answer is NO.</p><p>YES: In 1999 Gasarch and Kruskal had a paper in Mathematics Magazine: </p><p><a href="http://www.cs.umd.edu/~gasarch/papers/dice.pdf">When can one load of Dice so that the sum is uniformly distributed</a>?<br /></p><p>In that paper we have a theorem that gives an exact condition on</p><p>(n_1,...,n_k) for when there is a loaded n_1-sided dice, n_2-sided dice,...,n_k-sided dice so that </p><p>the sums are all equally likely.</p><p>In 2018 Ian Morrison published a paper in the American Math Monthly:</p><p><a href="https://arxiv.org/abs/1411.2272">Sacks of dice with fair totals</a><br /></p><p>which used our work and referred to our main theorem as <b>The Gasarch-Kruskal Theorem.</b></p><p>Hence there is a theorem with my name on it!</p><p>NO: The Gasarch-Kruskal paper has only 8 citations (according to Google Scholar). This is more than I would have thought, but its not a lot. The fact that ONE person calls the main theorem THE GASARCH-KRUSKAL THEOREM hardly makes it a named theorem. </p><p>QUESTION: So what criteria can one use?</p><p>We could say that X has a theorem with their name on it if there is a Wikipedia entry about the theorem, using that name. That works to a point, but might fun afoul of Goodhart's law (if a measure becomes a target it stops being a measure) in that, for example, I could write a Wikipedia entry on The Gasarch-Kruskal Theorem. </p><p>We could say that 10 people need to refer to the theorem by the name of its authors. Why 10? Any number seems arbitrary. </p><p>CAVEAT: If someone asked Clyde Kruskal <i>is there a theorem that bears your name</i> that is trickier, since <i>The Kruskal Tree Theorem</i> bears his name.... but its not his theorem. Reminds me of the (fictional) scenario where a Alice steals a Field's medal and tells Bob<i> I have a Field's Medal! </i>and Bob thinks Alice is a world-class mathematician since she has a fields medal, rather than thinking Alice is a world class thief. See <a href="https://blog.computationalcomplexity.org/2018/08/how-valuable-is-fields-medal.html">here</a> for my post on that. </p><p>(I originally had Kruskal Three Theorem instead of Tree Theorem. I have corrected this but I hope it inspires Clyde to prove a theorem about the number Three so he can have a named theorem. And if he is lucky, over time, people will confuse it with the Kruskal Tree Theorem!) </p><p><br /></p><p><br /></p><p><br /></p><p><i><br /></i></p>https://blog.computationalcomplexity.org/2022/05/is-kamala-harris-our-first-female-prez.htmlnoreply@blogger.com (gasarch)2