tag:blogger.com,1999:blog-3722233Mon, 20 Aug 2018 05:42:02 +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)Blogger2607125tag:blogger.com,1999:blog-3722233.post-4363069041026174846Mon, 20 Aug 2018 04:09:00 +00002018-08-20T00:09:35.989-04:00Fractional Problems: 2.1-colorable, 2.8-SATSome graphs are 2-colorable, some graphs are 3-colorable, some graphs are...Does it make sense to say that a graph is 2.1-colorable? It does!(Source_ Factional Graph Theory by Schneinerman and Ullman-- I saw a talk on this by Jim Propp a long time ago.)<br />
<br />
Def 1: A graph is (a,b)-colorable (with a \le b) if you can assign to every vertex a set of a numbers from {1,...,b} such that if u and v are adjacent then the set of numbers are disjoint. Note that k-colorable is (1,k)-colorable. Let chi_b(G) be the least a such that G is (a,b)-col.<br />
The fractional chrom num of G is lim_{b-->infinity} chi_b(G)/b.<br />
<br />
Def 3: We restate the ordinary Chrom Number problem as an integer program (and NOT by using that<br />
Chrom Num \le SAT \le IP). In fact, our Int Prog will be LARGE. For every ind set I of G we have a 0-1 valued var x_I which will be 1 iff x_I is all one color. We want to minimize \Sum_I x_I with the constraint that, for every vertex v in the graph. sum_{v in I} x_I \ge 1, so every vertex is colored.<br />
: Fractional Chrom number is what you get if you relax the above IP to an LP with x_I in [0,1] instead of {0,1}.<br />
<br />
Defs 1 and 2 turn out to be equiv. The wikipedia entry on Fractional Chromatic Number (see <a href="https://en.wikipedia.org/wiki/Fractional_coloring">here</a>) is pretty good and has some applications to real world things.<br />
<br />
QUESTION: 2-col is in P, 3-col is NPC. What about, say, 2.1-col. It turns out that, for every c>2, c-col is NPC. <br />
<br />
Open question (which Jim Propp used to begin his lecture): Every planar graph is 5-col has an EASY proof. Every planar graph is 4-col has a HARD (or at least tedious) proof. Is there a nice proof that every planar graph is (say) 4.5-colorable? The answer is Yes, Every planar graph is 4.5 colorable. I blogged on it <a href="https://blog.computationalcomplexity.org/2015/10/a-human-readable-proof-that-every.html">here</a>.<br />
<br />
Are there other fractional problems related to NPC problems. YES- at a Dagstuhl there was a paper on (2+epsilon)-SAT. (by Austrin, Guruswami, Hastad) (see <a href="http://eccc.hpi-web.de/report/2013/159/">here).</a><br />
<br />
What is fractional SAT? Lets recall ordinary k-SAT: every clause has k literals and you need to make at least one of them true. What if you wanted to make at least 2 of them true? (a/b)-SAT is if every clause has exactly b literals and you want an assignment that makes at least a in each clause true.<br />
<br />
GOOD NEWS: for all epsilon, (2+epsilon) is NP-complete. Its not so much good that its true, but its good that its known.<br />
<br />
BAD NEWS: The proof is hard, uses lots of tools.<br />
<br />
ODD NEWS: The speaker said that they PROVED there was no easy proof.<br />
<br />
I think its worth having your students try to DEFINE these terms on their own. The NPC proofs may be over their heads (they may be over my head), but the definitions are nice and the students might be able to derive them.<br />
<br />
QUESTION: Do other NPC problems have Fractional versions? I would think yes. This could lead to a host of open problems OR perhaps they have already been asked. If you know of any, please comment.https://blog.computationalcomplexity.org/2018/08/fractional-problems-21-colorable-28-sat.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-8405648690074998060Thu, 16 Aug 2018 17:38:00 +00002018-08-17T07:22:51.078-04:00How valuable is a Fields Medal? (Johan Hastad won the Knuth Prize! The below post was written before I knew that but has a mild connection to it. See <a href="https://www.acm.org/media-center/2018/august/knuth-prize-2018">here</a> for more info on the Hastad winning it, or see Lance's tweet, or see Boaz's blog post <a href="https://windowsontheory.org/2018/08/16/johan-hastad-wins-knuth-prize/">here</a>. There will prob be other blogs about it as well. ADDED LATER: Lipton and Regan have a post on this <a href="https://rjlipton.wordpress.com/2018/08/16/winner-of-2018-knuth-prize-is/">here</a>.)<br />
<br />
<br />
<br />
<br />
The Fields Medal was recently awarded to<br />
<br />
Caucher Birkar<br />
<br />
Alessio Figalli<br />
<br />
Peter Scholze<br />
<br />
Akshay Benkatesh<br />
<br />
I was going to try to give one sentence about what they did, but Wikipedia does a better job than I ever could so I point there: <a href="https://en.wikipedia.org/wiki/Fields_Medal#Fields_medalists">here</a>. Terry Tao also has some comments on the Fields Medal <a href="https://terrytao.wordpress.com/2018/08/01/birkar-figalli-scholze-venkatesh/">here</a>. So does Doron Zeilberger <a href="http://sites.math.rutgers.edu/~zeilberg/Opinion168.html">here</a>.<br />
<br />
How much is a Fields medal worth?<br />
<br />
1) The winners get $15,000 each.<br />
<br />
2) Winning a Fields medal gets one a higher salary and the ability to change schools, so the $15,000 might not be the main monetary part. All Field Medalists are under 40 so the salary increases and such last for a much longer time then (say) a Nobel prize given for life achievements to someone much older. So you may rather win a Fields' medal when you are 39 than a Nobel when you are 70. The Abel prize is around 740,000 dollars and (I think) given for lifetime achievement so again, a Fields Prize may be better. (See <a href="https://en.wikipedia.org/wiki/Abel_Prize">here</a> for more on the Abel Prize). Which would I prefer to win? I would be delighted if that was my dilemma.<br />
<br />
3) I am sure that none of the four winners went into math because of the allure of the $15,000 Fields Medal.<br />
<br />
4) The title of this post is ambiguous. It can also be read as<br />
<br />
<i>how valuable is the actual medal?</i><br />
<i><br /></i>
The answer is $4000, much more than I would have thought. I only know this since it was recently stolen, see <a href="https://www.washingtonpost.com/news/worldviews/wp/2018/08/02/winner-of-top-mathematics-prize-has-medal-stolen-from-him-minutes-later/?utm_term=.5381b2018b53">here</a>.<br />
<br />
This raises a linguistic question. The four people above can say<br />
<br />
I WON a Fields Medal<br />
<br />
The thief can say<br />
<br />
I HAVE a Fields Medal<br />
<br />
and hope that people don't quite realize that he didn't earn it.<br />
<br />
(The article about the theft says the Fields medal is $11,500 dollars. Do they deduct the cost of the Medal itself? Or is the article wrong?)<br />
<i><br /></i>
<i><br /></i>https://blog.computationalcomplexity.org/2018/08/how-valuable-is-fields-medal.htmlnoreply@blogger.com (GASARCH)3tag:blogger.com,1999:blog-3722233.post-7186234639816352314Tue, 14 Aug 2018 13:45:00 +00002018-08-14T09:45:41.206-04:00While I Was AwayAfter the <a href="https://blog.computationalcomplexity.org/2018/07/complexity-in-oxford.html" target="_blank">Oxford Workshop</a> I enjoyed a two-week family vacation in Spain, where there was no rain in the plain, just <a href="https://www.nytimes.com/2018/08/04/world/europe/europe-heat-wave.html" target="_blank">very hot</a> up to 106℉. The old Spanish cities knew how to optimize for shade and breeze, more than I can say for Oxford.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<a href="https://1.bp.blogspot.com/-l592asXXNA8/W3Lcyp4RjqI/AAAAAAABi7w/5OFMt-r-T4882fbTM6GDD4pNJgyzt-UDgCLcBGAs/s1600/nevanlinna.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="388" data-original-width="640" height="193" src="https://1.bp.blogspot.com/-l592asXXNA8/W3Lcyp4RjqI/AAAAAAABi7w/5OFMt-r-T4882fbTM6GDD4pNJgyzt-UDgCLcBGAs/s320/nevanlinna.jpg" width="320" /></a>Meanwhile in a more moderate Brazilian climate, the <a href="https://www.icm2018.org/portal/en/home" target="_blank">International Congress of Mathematicians</a> awarded their medals, including the Rolf Nevanlinna Prize to <a href="https://www.mathunion.org/imu-awards/rolf-nevanlinna-prize/rolf-nevanlinna-prize-2018" target="_blank">Constantinos Daskalakis</a> in a year with several very strong candidates. The Nevanlinna prize gets awarded every four years to a researcher under 40 for contributions to mathematical aspects of information sciences. Costis was the then-student author of the 2004 <a href="https://blog.computationalcomplexity.org/2014/05/favorite-theorems-equilibrium.html" target="_blank">Nash Equilbrium is PPAD-complete</a> result and has gone on to be a leader in the algorithmic game theory community.<br />
<br />
The ICM also distributes the Fields Medal, the highest honor in mathematics. <a href="https://www.nytimes.com/2018/08/01/science/fields-medals-mathematics.html" target="_blank">Much ado</a> is given to Peter Scholze who received the award this year at the age of thirty though remember that Alexander Razborov received his Nevanlinna prize at the age of 27 in 1990. Caucher Birkar also received the Fields Medal at the more standard age of 40 but had it for only a few minutes before it was literally <a href="https://www.nytimes.com/2018/08/02/world/europe/fields-medal-theft-caucher-birkar.html" target="_blank">stolen away</a>.<br />
<br />
I didn't realize how much I appreciate the convenience of Uber and Lyft until I had to get around cities where they don't exist. Meanwhile New York <a href="https://www.nytimes.com/2018/08/08/nyregion/uber-vote-city-council-cap.html" target="_blank">started to limit</a> ride-sharing vehicles and I arrived in Madrid to a taxi strike protesting Uber in that city. The Yin and Yang of technology.<br />
<br />https://blog.computationalcomplexity.org/2018/08/while-i-was-away.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-6775816584620815277Wed, 08 Aug 2018 03:37:00 +00002018-08-08T09:11:45.032-04:00The Future of TCS Workshop, celebrating V Vazirani 60th, now online<br />
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
On June 29, 2018, a workshop was held, in conjunction with STOC 2018, to celebrate the accomplishments of Vijay Vazirani on the <span style="font-size: 12.8px;">occasion of his 60th birthday, organized by his PhD students, Aranyak Mehta, Naveen Garg and Samir Khuller. </span><span style="font-size: 12.8px;">The workshop was called "TCS: Looking into the Future" and true to the title, it was precisely that! In front of a large, enthusiastic </span><span style="font-size: 12.8px;">audience, left over from STOC, the star-studded lineup of speakers outlined some of the most avant-garde, far out ideas </span><span style="font-size: 12.8px;">on the future of computing. Fortunately, this exciting and highly thought-provoking set of talks was recorded for posterity </span><span style="font-size: 12.8px;">and is available for all to view </span><a href="https://www.cs.umd.edu/users/samir/stoc2018/" style="font-size: 12.8px;">her</a><span style="font-size: 12.8px;">e</span><br />
<span style="font-size: 12.8px;">THE LAST WORD `here' IS THE LINK to the website which has links to the four talks.</span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<blockquote style="font-size: 12.8px;" type="cite">
<div style="word-wrap: break-word;">
<div style="font-family: Menlo; font-size: 14px; margin: 0px;">
The speakers were:<span class="m_4037453103701832362gmail-m_5420954052706171597Apple-tab-span" style="white-space: pre-wrap;"> </span></div>
<div style="font-family: Menlo; font-size: 14px; margin: 0px; min-height: 16px;">
<blockquote style="font-family: arial, sans-serif; font-size: 12.8px;" type="cite">
<div style="word-wrap: break-word;">
<div style="font-family: Menlo; font-size: 14px; margin: 0px;">
Len Adleman, Manuel Blum, <span style="color: #500050;">Richard Karp, </span><span style="color: #500050;">Leonard<span style="white-space: pre-wrap;"> </span></span><span style="color: #500050;">Schulman, </span><span style="color: #500050;">Umesh Vazirani.</span></div>
</div>
</blockquote>
</div>
</div>
</blockquote>
<br />
1) I URGE you to all WATCH those talks!<br />
<br />
2) I really like it when talks are available on line after the fact so even if you didn't go (I didn't) you can still see the talks later.<br />
<br />
3) So many talks to watch, so little time, alas!<br />
<br />
4) Sorry for the white background for this post- that happens sometimes. NO comments on it please.<br />
<br />
<br />
<br />
<br /></div>
https://blog.computationalcomplexity.org/2018/08/the-future-of-tcs-workshop-celebrating.htmlnoreply@blogger.com (GASARCH)5tag:blogger.com,1999:blog-3722233.post-7489278706488122204Wed, 01 Aug 2018 20:50:00 +00002018-08-02T10:48:06.333-04:00Three trick questions in Formal Lang TheoryThere are three questions I ask in my Formal Lang Theory class that even the very best students get wrong. Two I knew were trick quesions, the other I was surprised by<br />
<br />
1) If w is a string then SUBSEQ(w) is all strings you can form by replacing some symbols in w<br />
with empty string. SUBSEQ(L) is defined in the obv way.<br />
<br />
I ask the following in class (not on an exam). TRUE or FALSE and WHY and we'll discuss<br />
If L is regular then SUBSEQ(L) is regular<br />
If L is context free then SUBSEQ(L) is context free<br />
If L is decidable then SUBSEQ(L) is decidable<br />
If L is c.e. (used to be called r.e.) then SUBSEQ(L) is c.e.<br />
<br />
The students pretty much get and prove that 1,2, and 4 are TRUE. They all think 3 is false.<br />
But is true. For a strange reason<br />
<br />
If L is ANY lang whatsoever then SUBSEQ(L) is regular. Comes from wqo theory. For more on this see a blog post I did when I was a guest blogger (it shows- the typeface is terrible) <a href="https://blog.computationalcomplexity.org/2006/01/theorem-that-should-be-better-known.html">here</a><br />
<br />
2) How many states does and NFA need for { a^n : n \ne 1000} (or similar large numbers). ALL of the students think it takes about 1000 states. They are wrong: <a href="https://blog.computationalcomplexity.org/2018/04/challenge-about-nfa-for-ay-yne-1000.html">here</a><br />
<br />
The two above I know people get wrong. The third one surprised me, yet every year the good students get it wrong<br />
<br />
3) BILL: We showed that<br />
a) 2-colorablility is in P, hence of course planar 2-colorability is in P<br />
b) 3-colorability is NP-complete<br />
c) 4-colorabilty of Planar graphs is in P<br />
<br />
SO what about 3-colorability of planar graphs?<br />
<br />
My very best student said the following last spring:<br />
<br />
Planar 2-col is in P<br />
<br />
Planar 4-col is in P<br />
<br />
so I would guess that Planar 3-col is in P.<br />
<br />
In prior years others made the same mistake. My opinion of these students is NOT lowered, but I am surprised they make that guess. Of course, once you KNOW something you have a hard time recovering the state of mind of NOT knowing it, so my being surprised says more about my having drunk the Kool aid then their thought patterns.<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/08/three-trick-questions-in-formal-lang.htmlnoreply@blogger.com (GASARCH)8tag:blogger.com,1999:blog-3722233.post-7485569213345579704Fri, 27 Jul 2018 09:20:00 +00002018-07-27T05:21:15.764-04:00Complexity in OxfordOxford, England is in the middle of a heat wave and it handles high temperatures about as well as Atlanta handles snow. But that can't stop the complexity and a <a href="http://www.claymath.org/events/complexity-theory">wonderful workshop</a> this past week. It's my first trip to Oxford since I came <a href="https://blog.computationalcomplexity.org/2013/10/celebrating-maths-in-oxford.html">five years ago</a> to celebrate the opening of the Andrew Wiles building, a building that hosted this weeks' workshop as well.<br />
<br />
We also got a chance to see old math and physics texts. Here's Euclid's algorithm from an old printing of Euclid's Elements.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://2.bp.blogspot.com/-rYrGEM8V3eY/W1rjLLvLq2I/AAAAAAABhwA/ymX4vFZZjiYxNdQxWZGNEFy-X3C9GXo2wCKgBGAs/s1600/IMG_20180725_145610.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1200" height="320" src="https://2.bp.blogspot.com/-rYrGEM8V3eY/W1rjLLvLq2I/AAAAAAABhwA/ymX4vFZZjiYxNdQxWZGNEFy-X3C9GXo2wCKgBGAs/s320/IMG_20180725_145610.jpg" width="240" /></a></div>
<br />
<div>
<br /></div>
<div>
Unlike a research conference, this workshop had several talks that gave a broader overview of several directions in complexity with a different theme each day.<br />
<br />
A few highlights of the many great talks.</div>
<div>
<br /></div>
<div>
Sasha Razborov gave a nice discussion of proof systems that help us understand what makes circuit bounds hard to prove. </div>
<div>
<br /></div>
<div>
Tuesday was a day for pseudorandomness, finding simple distributions that certain structure can't distinguish from random. Ryan O'Donnell talked about fooling polytopes (ANDs of weighted threshold functions). Avishay Tal talked about his <a href="https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.html">new oracle with Ran Raz</a>, viewing it in this lens as a distribution that the low-depth circuit can't distinguish but quantum can. I talked about some simple extensions to Raz-Tal and the possibilities of using their techniques to show that you can't <a href="https://blog.computationalcomplexity.org/2005/12/pulling-out-quantumness.html">pull out quantumness</a> in relativized worlds.</div>
<div>
<br /></div>
<div>
Toni Pitassi talked about lifting--creating a tight connection between decision tree and </div>
<div>
complexity bounds to export lower bounds from one model to the other. Yuval Ishai talked about the continued symbiosis between complexity and theoretical cryptography.</div>
<div>
<br /></div>
<div>
Ryan Williams talked about his approach of using circuit satisfiability algorithms to prove lower bounds that led to his famed <a href="https://blog.computationalcomplexity.org/2010/11/breakthrough-circuit-lower-bound.html">NEXP not in ACC<sup>0</sup></a> result. He has had considerable recent progress including <a href="https://eccc.weizmann.ac.il/report/2017/188/">his recent work</a> with Cody Murray getting reducing NEXP to nondeterministic quasipolynomial time.<br />
<br />
Great to get away and just think complexity for a week. Seeing my former students Rahul Santhanam and Josh Grochow all grown up. And realizing I've become that old professor who regales (or bores) telling complexity stories from long ago. </div>
https://blog.computationalcomplexity.org/2018/07/complexity-in-oxford.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-8298995692495359819Wed, 25 Jul 2018 13:16:00 +00002018-07-25T09:16:08.474-04:00Need EASY approaches to getting unif random from non-random sourcesTeaching crypto for the first time next semester I am looking into lots of stuff I always meant to look into but now I have to. NOT a complaint- good to be forced to expand my horizons (within TCS).<br />
<br />
I"m also finding out that the web is great for easy and hard stuff but not so good for medium stuff.<br />
<br />
Here is what I want to know so I am reaching out to my readers.<br />
<br />
KNOWN: you want to generate a unif rand seq of 0's and 1's. The bits you can generate are Independent (yeah) but biased (boo). So here is what you do: generate 2 at a time and<br />
<br />
if see 00 then DO NOT USE<br />
<br />
if see 11 then DO NOT USE<br />
<br />
if see 01 then generate 0<br />
<br />
if see 10 then generate 1<br />
<br />
KNOWN: You can do similar things if you have 00, 01, 10, 11 independent. And also if you have 000, 001, blah blah , 111 independent.<br />
<br />
I tried looking up if there is a better way and I came across some complicated papers. I need material for a senior course. So, are there INTERMEDIARY results Suitable for a classroom, on better ways to us an imperfect source to get unif rand?<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/07/need-easy-approaches-to-getting-unif.htmlnoreply@blogger.com (GASARCH)11tag:blogger.com,1999:blog-3722233.post-7589043882065177318Fri, 20 Jul 2018 14:22:00 +00002018-07-20T10:22:09.887-04:00CRA Snowbird 2018<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-S11q5hHLjOg/W1DmF2Nao_I/AAAAAAABhr0/VyE7q7WdZQUlhUD2CpWQpDKhCzFhHcgYgCKgBGAs/s1600/IMG_20180717_170023.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="1200" data-original-width="1600" height="240" src="https://4.bp.blogspot.com/-S11q5hHLjOg/W1DmF2Nao_I/AAAAAAABhr0/VyE7q7WdZQUlhUD2CpWQpDKhCzFhHcgYgCKgBGAs/s320/IMG_20180717_170023.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span style="font-size: 12.8px;">Marios Papaefthymiou (UC Irvine), Michael Franklin (U. Chicago), Larry Birnbaum (Northwestern) and me.</span></td></tr>
</tbody></table>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">This week I attended the <a href="https://cra.org/events/2018-cra-conference-snowbird/">2018 Computing Research Association Snowbird conference</a>, a </span><span style="font-family: inherit; font-size: 14.6667px; white-space: pre-wrap;">biennial</span><span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;"> meeting of Computer Science chairs and leadership mostly from the US. This is my fifth Snowbird meeting, once as a panelist talking about publications and now four times as a chair.</span><br />
<span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;"><br /></span></div>
<span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">One cannot deny the success of computer science over the past decade. Our enrollments have jumped dramatically, our students at all levels get great jobs, CS departments are expanding. CS research and ideas play fundamental roles in society usually but not always for the better. We have our challenges, how to we hire new faculty when most PhDs take industry jobs and how to cover the increasingly heavy course enrollments, but we do not have the existential discussions you might find in similar meetings in other disciplines.</span><br />
<span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;"><br /></span>
<span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">While the best part of the meeting happens in informal discussions in the hallways and on the mountain, several sessions bring out some specific topics in the minds of participants. A few that caught my interest.</span><br />
<span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;"><br /></span>
<span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">In the first Snowbird of the #metoo era, we had some good discussion and a few scary stories about what women face at conferences and academic departments. The ACM has a new </span><a href="https://www.acm.org/special-interest-groups/volunteer-resources/officers-manual/policy-against-discrimination-and-harassment" style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">conference harassment policy</a><span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;"> and many CS communities, </span><a href="https://www.ics.uci.edu/~irani/safetoc.html" style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">including theoretical computer science</a><span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">, are tackling this issue head on. This is part of a longer and larger struggle the field has had in attracting and retaining women and underrepresented minorities into the community.</span><br />
<span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;"><br /></span>
<span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">One session focused on <a href="https://arxiv.org/abs/1807.00071">pushing metric-based rankings</a> of computer science programs with presentations of </span><a href="https://academic.microsoft.com/#/institutions/41008148/Computer%20Science" style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">Microsoft Academic Search</a><span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">, CRA’s own </span><a href="http://csmetrics.org/" style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">CS metrics</a><span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;"> and Emery Berger’s </span><a href="http://csrankings.org/" style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">CS Rankings</a><span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">. CS Rankings has grown in popularity, particularly among undergrads looking at grad schools and Emery discussed how he’s created an advisory board that carefully considers how to count papers.</span><br />
<span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;"><br /></span>
<span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">Personally I </span><a href="https://blog.computationalcomplexity.org/2017/11/a-tale-of-three-rankings.html" style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">prefer</a><span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;"> the reputation-based rankings like </span><a href="https://www.usnews.com/best-graduate-schools/top-science-schools/computer-science-rankings" style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">US News</a><span style="font-family: inherit; font-size: 11pt; white-space: pre-wrap;">, but I was definitely the tiny minority in the room.</span>https://blog.computationalcomplexity.org/2018/07/cra-snowbird-2018.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-7608485142388752546Mon, 16 Jul 2018 16:55:00 +00002018-07-16T12:55:50.300-04:00The Mystical Bond Between Man and MachineYou just can't watch a movie these days without being inundated with trailers. First came <a href="https://www.youtube.com/watch?v=--8nr2kt4uk">Axl</a>, a movie about a boys love for a military robotic dog.<br />
<br />
<iframe allow="autoplay; encrypted-media" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/--8nr2kt4uk" width="560"></iframe><br />
<br />
"It's only a robot," says his father. "It's an intelligent robot" replies the kid. Then comes the generic ET-like story of the government coming for the robot.<br />
<br />
Next came a <a href="https://youtu.be/fAIX12F6958">trailer</a> for a movie that start off with Hailee Steinfeld discovering a VW bug with the background voice going "The driver don't pick the car. The car picks the driver". I'm thinking it's either a new <a href="https://www.imdb.com/title/tt0064603/">Herbie</a> movie or Transformers. Spoiler: Transformers.<br />
<br />
<iframe allow="autoplay; encrypted-media" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/fAIX12F6958" width="560"></iframe>
<br />
"There's a mystical bond between man and machine" the voice intones. Followed by action that looks just like Axl.<br />
<br />
Movie love for machines is hardly new. You can go back to <a href="https://www.imdb.com/title/tt1798709/">Her</a> or <a href="https://www.imdb.com/title/tt0091949/">Short Circuit</a> or even <a href="https://www.imdb.com/title/tt0017136/">Metropolis</a> in 1927. But in an age that <a href="http://www.chicagotribune.com/lifestyles/parenting/ct-life-parenting-alexa-rudeness-20180509-story.html">parents worry about their kids being rude to Alexa</a> perhaps this mystical bond is starting to get just a little too real.https://blog.computationalcomplexity.org/2018/07/the-mystical-bond-between-man-and.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-3053689401972298405Thu, 12 Jul 2018 05:33:00 +00002018-07-12T01:33:55.481-04:00The Six Degrees of VDW A long long time ago a HS student, Justin Kruskal (Clyde's son) was working with me on upper bounds on some Poly VDW numbers (see <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/polyvdwstat.pdf">here</a> for a statement of PVDW). His school required that he have an application. Here is what he ended up doing: rather than argue that PVDW had an application he argued that Ramsey Theory itself had applications, and since this was part of Ramsey Theory it had an application.<br />
<br />
How many degrees of separation were there from his work and the so called application.<br />
<br />
<ol>
<li>The best (at the time) Matrix Multiplication algorithm used 3-free sets.</li>
<li>3-free sets are used to get lower bounds on VDW numbers.</li>
<li>Lower bounds on VDW numbers are related to upper bounds on VDW numbers</li>
<li>Upper bounds on VDW are related to upper bounds on PVDW numbers.</li>
</ol>
Only 4 degrees! The people in charge of the HS projects recognized that it was good work and hence gave him a pass on the lack of real applications. Or they didn't quite notice the lack of applications. He DID end up being one of five students who got to give a talk on his project to the entire school. <br />
<br />
When you say that your work has applications is it direct? one degree off? two? Are all theorems no more than six degrees away from an application? Depends on how you define <i>degree</i> and <i>application.</i>https://blog.computationalcomplexity.org/2018/07/the-six-degrees-of-vdw.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-2985833046622649668Mon, 09 Jul 2018 20:05:00 +00002018-07-10T11:52:32.357-04:00Soliciting answers for THIRD survey about P vs NP<br />
<br />
I have done two surveys for SIGACT NEWS Complextiy Column (edited by Lane Hemaspaandra)<br />
on P vs NP and related topics. Lane has asked me to do a third. I annouced it in my open problems column <a href="https://www.cs.umd.edu/users/gasarch/open/pnp.pdf">here</a> For those who don't read SIGACT news<br />
<br />
1) You should!<br />
<br />
2) Here is where to go to fill out the survey: <a href="https://www.surveymonkey.com/r/PversusNP">here</a><br />
<br />
bill g.<br />
<br />
P.S. (do people use P.S. anymore? Do young people know that it means Post Script, and that it<br />
does not refer to ps-files?)<br />
<br />A commenter requested I add what the DEADLINE for responding was. I originally thought people would read the post and immediately respond (and I HAVE had a BIG uptick in responses in the last day). I still believe this. BUT there are people who read the blog days, weeks, months, even years after I post it (though the comments we get on very old posts tend to contain clicks for good deals on Tuxedo's (I am serious. Tuxedo's? Not well targeted unless they count my Tuxedo T-shirt).<br />
<br />
Okay, enough babbling -- the point is that I should have a deadline for those who read the blog later than now.<br />
<br />
DEADLINE: Oct 1, 2018. STRICT!<br />
<br />
P.P.S - does anyone use P.P.S anymore?<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/07/soliciting-answers-for-third-survey.htmlnoreply@blogger.com (GASARCH)7tag:blogger.com,1999:blog-3722233.post-4174824007188702211Thu, 05 Jul 2018 13:15:00 +00002018-07-05T09:15:31.343-04:00Happy 90th Juris!<div class="separator" style="clear: both; text-align: center;">
<a href="https://2.bp.blogspot.com/-KgCJcPhjO1o/Wz4ZxGnntbI/AAAAAAABhAM/f9n9VDzAgsgTg3pdB10tDsZpnWqIBlFGQCLcBGAs/s1600/Juris.gif" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="639" data-original-width="450" height="200" src="https://2.bp.blogspot.com/-KgCJcPhjO1o/Wz4ZxGnntbI/AAAAAAABhAM/f9n9VDzAgsgTg3pdB10tDsZpnWqIBlFGQCLcBGAs/s200/Juris.gif" width="140" /></a></div>
<a href="https://en.wikipedia.org/wiki/Juris_Hartmanis">Juris Hartmanis</a> turns 90 today. Hartmanis with Richard Stearns received the 1993 Turing Award for their seminar work <a href="http://dx.doi.org/10.2307/1994208">On the Computational Complexity of Algorithms</a>. I've <a href="https://blog.computationalcomplexity.org/2005/02/favorite-theorems-seminal-paper.html">talked about that paper before</a>, after all it started our field and gave the name that we use for the blog. So instead I'll use this blog post to talk about how Hartmanis led me into this wondrous field.<br />
<br />
At Cornell in 1983 I was an undergraduate double major in math and CS destined at the time for grad school in math. I took the undergraduate Introduction to Theory course from Hartmanis and immediately got excited about the field. Hartmanis said the top student in the course was typically an undergrad followed by a bunch of graduate students. I was a counterexample coming in second in the course list (back then your grades were posted by ID number). I never found out who came in first.<br />
<br />
In that same semester I took Introduction to Linguistics. Chomsky and context-free languages in both classes. Seemed cool at the time.<br />
<br />
Based almost solely on that course with Hartmanis I decided to do graduate work in theoretical computer science. In the spring of 1985, while most of my fellow second-semester seniors took Introduction to Wine, I took graduate Complexity Complexity again with Hartmanis. That cemented my career as a complexity theorist. The course started with some basic computability theory (then called recursion theory) and used that as a jumping point to complexity. A large emphasis on the <a href="https://blog.computationalcomplexity.org/2003/03/berman-hartmanis-isomorphism.html">Berman-Hartmanis Isomorphism Conjecture</a>. The conjecture implies P ≠ NP and Hartmanis said anyone who could prove the conjecture, even assuming P ≠ NP, would get an automatic A. The problem remains open but I did years later have a <a href="http://doi.org/10.1137/S0097539793248305">couple</a> of <a href="http://doi.org/10.1145/276698.276737">proofs</a> giving an oracle making BH true. That should be good enough for a B.<br />
<br />
My favorite quote from Juris: "We all know that P is different from NP, we just don't know how to prove it." Still true today.https://blog.computationalcomplexity.org/2018/07/happy-90th-juris.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-372915360611245521Mon, 02 Jul 2018 21:28:00 +00002018-07-02T17:28:01.431-04:00The BREAKTHROUGH on Chromatic Number of the Plane (guest post)(The new SIGACT News chair wnated me to post a letter he send to all SIGACT members on my blog in case you are not in SIGACT. He thinks you should be. I think so to so next year he won't ask me to do this. Here is his letter: <a href="https://dmatheorynet.blogspot.com/2018/07/new-sigact-executive-committee.html">here</a>)<br />
<br />
As many of you know there was a BREAKTHROUGH on the problem of the <i>The Chromatic Number of The Plane. </i>There have been fine blog posts on this by Gil Kalai <a href="https://gilkalai.wordpress.com/2018/04/10/aubrey-de-grey-the-chromatic-number-of-the-plane-is-at-least-5/">here</a> amd Scott Aaronson <a href="https://www.scottaaronson.com/blog/?p=3697">here</a>. Rather than blog on it ourselves we have recruited and expert in the field, Alexander Soifer. He has written a book on the history and mathematics of coloring problems (see <a href="https://www.amazon.com/Mathematical-Coloring-Book-Mathematics-Colorful/dp/0387746404/ref=asap_bc?ie=UTF8">here</a> for the amazon link to the book and <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/soiferrev.pdf">here</a> for my review of the book). The Chromatic Number of the Plane is his favorite problem. Much of the work on it is either by him or inspired by him. Much of the book is on it.<br />
<br />
Alexander also is the editor of a journal on problems like this called GEOCOMBINATORICS (oddly enough. Geometric Combinatorics is a different field). See <a href="http://geombina.uccs.edu/">here</a> for that journal- which I recommend!<br />
<br />
He wrote an 8-page essay, which is a concise version of an essay that will appear in a Special Issue XXVIII (1) of Geocombinatorica (July 2018, 5-17), dedicated to 5-chromatic unit distance graphs. The essay includes contributions from Aubrey D.N.J de Grey, Marijn J.H. Heule, and Geoffrey Exoo<br />
and Dan Ismailescu.<br />
<br />
What I find remarkable is that even though the result is new, the essay contains NEWER results. The modern world moves fast!<br />
<br />
Without further ado, here is that essay: <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/soifer.pdf">here</a>.https://blog.computationalcomplexity.org/2018/07/the-breakthrough-on-chromatic-number-of.htmlnoreply@blogger.com (GASARCH)1tag:blogger.com,1999:blog-3722233.post-7678617942504457868Thu, 28 Jun 2018 22:31:00 +00002018-06-28T18:31:33.090-04:00STOC 50 Part IIOn Wednesday, <a href="http://acm-stoc.org/stoc2018/">STOC</a> had a great complexity session and the best complexity paper of the conference, Cody Murray and Ryan Williams extending Ryan’s <a href="https://blog.computationalcomplexity.org/2010/11/breakthrough-circuit-lower-bound.html">celebrated result</a> separating NEXP from ACC<sup>0</sup>. Cody and Ryan <a href="http://people.csail.mit.edu/rrw/easy-witness-nqp.pdf">show</a> there are problems in quasipolynomial time (2<sup>poly log(n)</sup>) that do not sit in ACC<sup>0</sup>, a near exponential improvement from Ryan’s original work. The key insight shows that if NP has n<sup>k</sup>-size circuits then for some j, each accepting input has a witness describable by a n<sup>j</sup>-size circuit.<br />
<br />
By the way everyone now has full access to the <a href="http://acm-stoc.org/stoc2018/toc.html">STOC Proceedings</a>. Read and enjoy.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://3.bp.blogspot.com/-jluSKVu_Pu0/WzVfxnL8eHI/AAAAAAABg5k/pAq_qOLeJf8DzCUtkM_DXczZ5-HOIZfIgCKgBGAs/s1600/IMG_20180627_201908.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="300" src="https://3.bp.blogspot.com/-jluSKVu_Pu0/WzVfxnL8eHI/AAAAAAABg5k/pAq_qOLeJf8DzCUtkM_DXczZ5-HOIZfIgCKgBGAs/s400/IMG_20180627_201908.jpg" width="400" /></a></div>
<br />
<br />
Before the business meeting, Moses Charikar led a panel reminiscing over the 50 years of STOC. Panelists Dick Karp, Al Borodin, Ronitt Rubinfeld and Avrim Blum talked over memories of the early conferences and the good old days of transparencies and paper submissions.<br />
<br />
Highlights of the business meeting:
<br />
<ul>
<li>About 350 attendees, slightly larger than years past though the organizers hoped for a larger crowd given the 50th celebration and the theory fest.
</li>
<li>112 accepted papers of 416 submitted. There are now 29 PC members--time to rethink the standard in-person meeting.
</li>
<li><a href="https://www.irif.fr/~focs2018/">FOCS 2018</a> in Paris October 7-9. STOC 2019 as part of <a href="https://fcrc.acm.org/">FCRC</a> in Pheonix June 22-28. STOC 2020 likely in Copenhagen.
</li>
<li>New SIGACT executive committee: Samir Khuller (Chair), Eric Allender, Shuchi Chawla, Nicole Immorlica and Bobby Kleinberg.
</li>
<li>Shuchi Chawla taking over <a href="https://thmatters.wordpress.com/catcs/">CATCS</a>. Lots of goodies on the <a href="https://thmatters.wordpress.com/">website</a> for those applying for funding or looking for jobs.
</li>
<li>Sandy Irani is leading a new effort to <a href="https://www.ics.uci.edu/~irani/safetoc.html">combat harrassment</a> in the theoretical computer science community.
</li>
<li>Tracy Kimbrel gave NSF report. The NSF <a href="https://www.hpcwire.com/off-the-wire/nsf-appoints-dr-rance-cleaveland-as-division-director-for-division-of-computing-and-communication-foundations/">recently appointed</a> Rance Cleaveland as head of CCF, the division that includes algorithmic foundations. New rule: You can’t submit to both CRII and CAREER in the same year so pick your poison.
</li>
</ul>
https://blog.computationalcomplexity.org/2018/06/stoc-50-part-ii.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-3577093627049268680Tue, 26 Jun 2018 22:31:00 +00002018-06-26T18:31:24.333-04:00STOC 50 Part IThis week I'm in Los Angeles attending the 50th Symposium on the Theory of Computing. Most attendees weren't even born before the first STOC. Many of them weren't even born when I went to my first STOC in 1986 in Berkeley.<br />
<br />
Most of the festivities come later but let me mention the best paper winners, both of whose titles give the theorem. <a href="https://arxiv.org/abs/1708.04215">A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem</a> by Ola Svensson, Jakub Tarnawski and László Végh won the best paper and <a href="https://arxiv.org/abs/1711.06455">An almost-linear time algorithm for uniform random spanning tree generation</a> by Aaron Schild won the Danny Lewin Best Student Paper Award. For those who don't know, Danny Lewin was an MIT grad student and co-founder of Akamai who <a href="https://www.cnn.com/2013/09/09/tech/innovation/danny-lewin-9-11-akamai/index.html">lost his life on 9/11</a>.<br />
<br />
A nice feature of the STOC theory fest, a tradition started last year, are the many invited talks. This morning we saw Stanford statistician Emmanuel Candes talk about irreproducible scientific results. The scientific method typically makes hypotheses, designs experiments to test predictions, updates the hypotheses and repeat. Today with we automatically generate hypotheses from big data using machine learning techniques which often leads to false positive correlations. Candes talked about his approach to mitigating this problem with <a href="https://statweb.stanford.edu/~candes/papers/FDR_regression.pdf">knockoff variables</a>.<br />
<br />
I also enjoy the senior junior lunch which I had today with students Rachit Nimavat, Jiyu Zhang and Zhixian Lei. Great discussions about the theory life.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://2.bp.blogspot.com/-mftejUg9OnI/WzK-kcbWlNI/AAAAAAABg0s/Tzs_R2umV3ACONRgHq2S1RA0JcdbZaJKwCKgBGAs/s1600/IMG_20180626_132249.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="240" src="https://2.bp.blogspot.com/-mftejUg9OnI/WzK-kcbWlNI/AAAAAAABg0s/Tzs_R2umV3ACONRgHq2S1RA0JcdbZaJKwCKgBGAs/s320/IMG_20180626_132249.jpg" width="320" /></a></div>
<br />https://blog.computationalcomplexity.org/2018/06/stoc-50-part-i.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-4397437624918579778Fri, 22 Jun 2018 17:31:00 +00002018-07-10T13:11:57.868-04:00The Muffin ProblemI've been meaning to post on THE MUFFIN PROBLEM for at least a year. Its a project I've been working on for two years, but every time I wanted to post on it I thought.<br />
<br />
<br />
<i>I'm in the middle of a new result. I'll wait until I get it!</i><br />
<br />
However, I was sort of forced to finally post on it since Ken Regan (with my blessing) posted on it. In fact its better this way- you can goto his post for the math and I get to just tell you other stuff.<br />
<i><br /></i>
The problem was first defined by Alan Frank in a math email list in 2009.<br />
<i><br /></i>
I'll define the problem, though for more math details goto Ken's post: <a href="https://rjlipton.wordpress.com/2018/06/21/muffins-and-integers/">here</a>.<br />
<br />
You have m muffins and s students. You want to give each student m/s piece and<br />
divide the muffins to maximize the min piece. Let f(m,s) be the size of the min piece<br />
in an optimal divide-and-distribute procedure.<br />
<br />
Go and READ his post, or skim it, and then come back.<br />
<br />
Okay, you're back. Some informal comments now that you know the problem and the math<br />
<br />
1) I saw the problem in a pamplet at the 12th Gathering for Gardner. Yada Yada Yada I have 8 co-authors and 200 pages, and a paper in FUN with algorihtms You never know when a problem will strike you and be worth working on!<br />
(The 8 coauthors are Guangiqi Cui, John Dickerson, Naveen Dursula, William Gasarch, Erik Metz,<br />
Jacob Prinze, Naveen Raman, Daniel Smolyak, Sung Hyun Yoo. The 200 pages are <a href="https://arxiv.org/abs/1709.02452">here</a>. The FUN with algorithms paper, only 20 pages, is <a href="http://drops.dagstuhl.de/opus/volltexte/2018/8806/pdf/LIPIcs-FUN-2018-15.pdf">here</a>)<br />
<br />
2) Many of the co-authors are HS students. The problem needs very little advanced mathematics (though Ken thinks it might connect to some advanced math later). This is a PRO (HS students can work on it, people can understand it) and a CON (maybe harder math would get us more unified results)<br />
<br />
3) The way the research had gone is a microcosm for math and science progress:<br />
<br />
We proved f(m,s) = (m/s)f(s,m) (already known in 2009) by Erich Friedman in that math email list)<br />
<br />
Hence we need only look at m>s.<br />
<br />
First theorem: we got a simple function FC such that<br />
<br />
f(m,s) ≤ FC(m,s)<br />
<br />
for MANY m,s we got f(m,s) = FC(m,s).<br />
<br />
GREAT! - conjecture f(m,s) = FC(m,s)<br />
<br />
We found some exceptions, and a way to get better upper bounds called INT.<br />
<br />
GREAT! - conjecture f(m,s) = MIN(FC(m,s),INT(m,s))<br />
<br />
We found some exceptions, and a way to get better upper bounds called ... We now have<br />
<br />
conjecture<br />
<br />
f(m,s) = MIN(FC(m,s), INT(m,s), ERIK(m,s), JACOB(m,s), ERIKPLUS(m,s), BILL(m,s))<br />
<br />
and it looks like we still have a few exceptions.<br />
<br />
This is how science and math works- you make conjectures which are false but the refutations lead<br />
to better and better results.<br />
<br />
Also, we have over time mechanized the theorems, a project called:<br />
<br />
<i>Making Erik Obsolete</i><br />
<br />
since Erik is very clever at these problems, but we would like to not have to rely on that.<br />
<br />
4) I have worked hard on this problem as is clear from this: <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/billmuffins.JPG">picture</a><br />
<br />
<br />https://blog.computationalcomplexity.org/2018/06/the-muffin-problem.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-1193088248712227693Mon, 18 Jun 2018 02:31:00 +00002018-06-18T11:07:40.883-04:00Its good to be mii<div class="separator" style="clear: both; text-align: center;">
<a href="https://3.bp.blogspot.com/-LQZaKnqa-24/Wye95teJDSI/AAAAAAABgmA/MkgtyeUue_w7fa22AHEaYY5127T0bNueACLcBGAs/s1600/WilliamGasarch-MII.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="316" data-original-width="316" height="200" src="https://3.bp.blogspot.com/-LQZaKnqa-24/Wye95teJDSI/AAAAAAABgmA/MkgtyeUue_w7fa22AHEaYY5127T0bNueACLcBGAs/s200/WilliamGasarch-MII.jpg" width="200" /></a></div>
When I taught ugrad Elementary Theory of Computation (Reg, CFL, P, NP, Dec, c.e.) I made 5% of the grade be MEET THE PROF- come to my office, in groups of 3-6 (though sometimes I got 10) just to talk to me. I ask them what there plans are, why they took the course, and they get to ask ME what they want.<br />
<br />
The most common question I got:<br />
<br />
Why is your mii the example of a mii on the Wikipedia entry on mii: <a href="https://en.wikipedia.org/wiki/Mii">here</a> (<a href="https://en.wikipedia.org/w/index.php?title=Mii&oldid=845863614">permalink</a>)<br />
<br />
I was originally hesitant to blog about this because (1) it may go away soon, and (2) I don't know.<br />
<br />
But (1) its been there and stable for a while, and (2) I can speculate:<br />
<br />
1) A prof in my department (not me) made and posted a Wikipedia page about me.<br />
<br />
2) That page used the mii.<br />
<br />
3) The powers that be at Wikipedia took down the mii (along with the list of my grad students who got PhD's). This post is not a rant about this, but I will note that I think they should have allowed the mii since it looks like me. whenever I am going to meet someone at an airport I email them the mii and it always works.<br />
<br />
4) Speculation: since it was on my Wikipedia page this mii was in the public domain and they could easily access it. Hence they used it. Is Wikipedia this arbitrary? Yes.<br />
<br />
5) My darling thinks is unfair that the mii page can use my mii but my page can't. I just think its odd.https://blog.computationalcomplexity.org/2018/06/its-good-to-be-mii.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-8402524769831420181Thu, 14 Jun 2018 19:44:00 +00002018-06-14T15:44:07.053-04:00Hoteling<div class="" style="clear: both; text-align: left;">
</div>
<div class="separator" style="clear: both; text-align: left;">
Thanks to Grigory Yaroslavtsev for taking over the <a href="https://docs.google.com/spreadsheets/d/1P5okKjeNlvkEEFMzX3l8VcL4SHpWBKNFET-5mPTWfDQ/edit?usp=sharing">Theory Jobs Spreadsheet</a>. Details on <a href="http://grigory.us/blog/theory-jobs-2018/">Grigory's blog</a>. Check out who is going where next year.</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://4.bp.blogspot.com/-WgH8PebkshE/WyKBL8Z2AFI/AAAAAAABghg/X2mIdTBiIqEJ0ywaXEWU7R9EEve36h12wCKgBGAs/s1600/IMG_20180216_154918.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1302" data-original-width="1124" height="320" src="https://4.bp.blogspot.com/-WgH8PebkshE/WyKBL8Z2AFI/AAAAAAABghg/X2mIdTBiIqEJ0ywaXEWU7R9EEve36h12wCKgBGAs/s320/IMG_20180216_154918.jpg" width="275" /></a></div>
<br />
<br />
My office has an awesome view of Midtown Atlanta. Midtown has seen considerable construction over the last decade and I get to see the skyline change before my eyes. <a href="https://en.wikipedia.org/wiki/NCR_Corporation">NCR</a> opened an impressive glass building for their new world headquarters just a few months ago not coincidentally a short walk from Georgia Tech. A few weeks ago I got a tour of this facility.<br />
<div class="" style="clear: both; text-align: left;">
<br /></div>
<div class="" style="clear: both; text-align: left;">
Most of the employees in the building do not get their own offices or desks. They have an open floor plan with hoteling. They use an app to reserve a desk up to a few weeks ahead of time. Each desk has a keyboard and two screens that they stick their laptops into. Their cell phones become their main phones. There are many conference rooms of different sizes, even some tiny ones meant for a single person to have a phone call or escape to some quietness.<br />
<br />
Would hoteling work in the academic world? Never, you learn quickly that professors will never give up two things: their office or their parking. When we do talk about hoteling, we talk about a shared office for people who have a main office in a different building.<br />
<br />
With faculty who often travel at far too many conference, or on some days working out of home or coffee shops and rarely using the books in their office, if they have them at all, why do we stick to the old fashioned offices?<br />
<br />
The best academic research require collaboration, between faculty, students, postdocs and other researchers. The best times I've had as a professor is when a student or colleague walks into my office with a question, an idea or sometimes a proof. Better if I have some place to be found and not just a location in an app.<br />
<br />
I'd also miss the view. </div>
https://blog.computationalcomplexity.org/2018/06/hoteling.htmlnoreply@blogger.com (Lance Fortnow)4tag:blogger.com,1999:blog-3722233.post-6021604827359277098Mon, 11 Jun 2018 04:45:00 +00002018-06-11T00:46:54.305-04:00How the Villarino-Gasarch-Regan paper came about(This post overlaps a prior one <a href="http://blog.computationalcomplexity.org/2016/12/the-very-first-ramseyian-theorem.html">here</a>. The paper I am blogging about was also blogged about by Lipton <a href="https://rjlipton.wordpress.com/2018/06/08/hilberts-irreducibility-theorem/">here</a>. The paper itself is on arxiv <a href="https://arxiv.org/abs/1611.06303">here</a>. My slides for a talk I will be giving on this material are <a href="https://www.cs.umd.edu/users/gasarch/hilbertalk.pdf">here</a>)'<br />
<br />
<br />
<br />
Todays post is on how the paper came about. A later post will be about why someone else didn't do it earlier.<br />
<br />
How this paper came about:<br />
<br />
Many years ago Bill noticed that while several books on Ramsey theory (see my prior post for quotes) state that the HCL was the first Ramseyian theorem. I think one source mentioned in passing that Hilbert used it to prove the Hilbert Irreducibility theorem (HIT). Bill could not find a modern English exposition of the proof. So he asked Ken Regan (who not only knows German but can recite The Lewis Carol Poem J<i>abberwocky</i> in German!) to translate it, and then Bill would put it in modern language, and there would be an exposition. Bill got bogged down in some of the math, and they both got bogged down with other things (For Ken catching chess-cheaters, for Bill mentoring HS students, for both of them, blogging.) Many years passed.<br />
<br />
Sometime before 2015 Larry Washington showed me a nice proof that (ignoring mult constants)<br />
<br />
∑ 1/p ≤ ln(ln(n)) + O(1) (the sum is over all primes p ≤n )<br />
<br />
Read that carefully. There are many proofs in the web that the sum isat least ≥ ln(lg n) but I could not find any that the sum was ≤ ln(ln n). Larry Washington told me that the result and<br />
the proof were not new. I told him that, even so, it doesn't seem to be out there. So we agreed to write and and post to arXiv but not publish in a journal. It's <a href="https://arxiv.org/abs/1511.01823">here</a>.<br />
<br />
This arXiv paper caught the attention of Mark since he had an exposition of Merten's proof see <a href="https://arxiv.org/abs/math/0504289">here</a> that that sum diverges. Mertens proof had explicit bounds which are missing from modern proofs.<br />
<br />
I got into an email discussion with Mark about Math and History and I casually mentioned that Ken and I had worked on-and-off on HRL and HIT. A few weeks later he emailed me a translation of the paper. WOW! We worked together on polishing it, combining it with what Ken had done, and later brought Ken back into the project. I say without embarasment that we NEEDED Mark to resolve some of the issues we had and push the paper out the door. A Win-Win-Win.<br />
<br />
And a lesson here--- Larry Washington was reluctant to publish on arXiv a paper on stuff that was already known. I should have told him<br />
<br />
<i>But Larry, if we do that I might find someone to help me finish the Hilbert paper</i><br />
<br />
In a word: Serendipity.https://blog.computationalcomplexity.org/2018/06/how-villarion-gasarch-regan-paper-came.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-7475523893806375286Wed, 06 Jun 2018 23:40:00 +00002018-06-06T19:40:47.448-04:00I tell my class that P is important because... but is that really true?When teaching P vs NP the questions arises (and if not then I bring it up) what if you have algorithm in P that takes n^{100} time?. Or even n^{5} time which might be too long.<br />
<br />
I have given the following answers for years; however, I post this and will use your comments as a sanity check. In fact, I suspect I am wrong on some points.<br />
<br />
1) IF SAT was in P then something very clever was done. Even if its n^{100} it was very clever. That cleverness will almost surely result in other better algorithms. They may only be better in practice by not in theory (it works in practice- if only we can get it to work in theory :-) ), but it will still work and be a great advance.<br />
<br />
2) IF SAT was in P then perhaps we could USE SAT in P to get a better algorithm for SAT in P. This was the theme of a chapter in Lance Fortnow's book <a href="https://www.amazon.com/Golden-Ticket-NP-Search-Impossible/dp/0691175780/ref=sr_1_1?ie=UTF8&qid=1491666026&sr=8-1&keywords=Lance+Fortnow">The Golden Ticket: P, NP. and the search for the impossible</a> and is also likely behind something I once heard (I think it was from Scott but I can't find it on his blog) <i>If P=NP then math would be easy and we would have already found a proof that P=NP. Hence P ≠ NP</i><br />
<br />
The two above really can't be WRONG or even RIGHT or even NOT EVEN WRONG since they are speculations. The next few is where I need my sanity checked<br />
<br />
3) Whenever a real world natural problem is in P it has a low degree poly algorithm OR there are ideas to make it work in practice, if not in theory. When Lance read a prior version of this post he pointed out that `real world natural problem' is not a well defined term. True. Not sure what to do about that. Even so, is this true? roughly true? Something theorists say to be able to sleep at night?<br />
<br />
4) In the real world people say ``OH- the problem is NP-complete. Better look for approx solutions instead'' Or similar things. While this sounds true since I have never worked in the real world I really don't know. Is that what people say? do?<br />
<br />
5) If Lance proves P=NP next week then the consequences are enormous for real people working on real computing problems. But what if Lance proves P NE NP? Would that affect people working on real computing problems? A long time Carl Smith told me <i>If P NE NP was proven then the proof would have great insight into computing which would have a real affect on real people working on real computing problems</i>. My Darling (who is a Software Engineer) is skeptical of that. What do you think?https://blog.computationalcomplexity.org/2018/06/i-tell-my-class-that-p-is-important.htmlnoreply@blogger.com (GASARCH)18tag:blogger.com,1999:blog-3722233.post-4482978010782675334Fri, 01 Jun 2018 18:09:00 +00002018-06-03T11:14:50.186-04:00BQP not in the Polynomial-Time Hierarchy in Relativized WorldsThe quantum complexity world is a rocking with the paper released yesterday by Ran Raz and Avishay Tal, <a href="https://eccc.weizmann.ac.il/report/2018/107/">Oracle Separation of BQP and PH</a>, resolving a question open since quantum complexity got its start over two decades ago. Scott Aaronson's <a href="https://www.scottaaronson.com/papers/bqpph.pdf">2010 paper</a> that sets some of the groundwork for the Raz-Tal result gives a nice overview of the question.<br />
<br />
All of you readers should be familiar with the P v NP question. P is the set of problems efficiently solvable by a deterministic computer. NP are the problems for which there exists a witness that we can verify quickly. The polynomial-time hierarchy (PH) is the constant alternation generalization of NP that has played a <a href="https://blog.computationalcomplexity.org/2005/06/favorite-theorems-polynomial-time.html">major role in computational complexity</a> So why don't we talk about the P vs PH question? That's just equivalent to P vs NP.<br />
<br />
BQP is the the class of problem efficiently solved by a quantum computer. Since P sits in BQP which sits in PSPACE we can't prove outright any separations for BQP without separating P from PSPACE. We can though get an understanding of complexity by allowing the machines access to the same oracle and seeing what we can separate. We already knew BQP doesn't sit in NP relative to an oracle. Same was true for BPP (efficient probabilistic computation) but BPP is in PH for all oracles as are constant round interactive proofs. So we might expect we can have BQP in PH, BQP solvable with constant alternations, relative to all oracles. Raz and Tal refute that hypothesis.<br />
<br />
Raz and Tal's proof builds on the Forrelation concept developed by <a href="https://www.scottaaronson.com/papers/bqpph.pdf">Aaronson</a> (under the name Fourier Checking) and extended by <a href="https://arxiv.org/abs/1411.5729">Aaronson and Ambainis</a>. The oracle isn't complicated: Pick n numbers x<sub>1</sub>,...,x<sub>n</sub> each x<sub>i</sub> chosen from a normal distribution with mean 0 and variance a small ε > 0. Let y=y<sub>1</sub>,...,y<sub>n</sub> be the <a href="https://en.wikipedia.org/wiki/Hadamard_transform">Hadamard transform</a> applied to x<sub>1</sub>,...,x<sub>n</sub>. You then probabilistically round the x's and y's to 1 or -1. A quantum machine can distinguish this distribution from uniform using the fact that quantum machines can do Hadamards easily and Raz and Tal use Fourier show that low-depth alternating circuits (that capture PH) can't distinguish so easily. The <a href="https://eccc.weizmann.ac.il/report/2018/107">paper</a> is well-written if you want details.<br />
<br />
A few questions for further directions:<br />
<ul>
<li>Can you show a relativized world where P = NP (=PH) but P ≠ BQP? I'd suspect it will be a messy but not too hard generalization of this paper.</li>
<li>How far can you push the Raz-Tal result, i.e., for what function f(n) can we show that BQP cannot be solved by f(n)-alternating polynomial-time Turing machines. Can you show f(n) = n<sup>Ω(1)</sup>?</li>
</ul>
<div>
Also see Scott's <a href="https://www.scottaaronson.com/blog/?p=3827">personal take</a> on this new result.</div>
https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.htmlnoreply@blogger.com (Lance Fortnow)2tag:blogger.com,1999:blog-3722233.post-1761435662289905853Thu, 31 May 2018 15:09:00 +00002018-05-31T14:13:25.293-04:00Seventh Grade Math ContestI stumbled upon an old <a href="https://www.lesswrong.com/posts/EdFDwjsLNpgtTMJAp/great-mathematicians-on-math-competitions-and-genius">blog post</a> on the Lesswrong weblog that quotes several famous mathematicians on the connections, or lack thereof, between mathematics competitions and mathematics research. Let me tell you how a seventh grade math contest altered the course of my life.<br />
<br />
In 1975 I attended seventh grade in a middle school in upstate New Jersey. The school divided the students into three tracks, honors, standard and remedial, and I was an unexceptional student in the standard track. We all took a math pretest to determine who would represent the school in a state-wide competition. To everyone's surprise, especially my own, I killed on the test scoring twice as many points as anyone else. The school adjusted my course schedule but because of my not-so-great English skills I became the only student taking honors math and science and standard English and History (with a racist history teacher but that's another story). I think I came in 12th in the state competition.<br />
<br />
I never did well in math contests after that, doing okay but not particularly strong in high school competitions. But the experience drove me to what we now call STEM. I got involved in computers and math in high school which led me to study engineering, <a href="https://blog.computationalcomplexity.org/2005/12/how-i-became-theorist.html">briefly</a>, at Cornell. I did <a href="https://blog.computationalcomplexity.org/2005/12/first-saturday-in-december.html">make the Putnam team</a> as a freshman at Cornell, but scored a zero which pretty much ended my career in math competitions.<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/05/seventh-grade-math-contest.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-2027657983416254684Wed, 30 May 2018 04:22:00 +00002018-05-30T08:00:37.194-04:00Why is someone emailing me an offer to apply to be chair?I recently go the following email (I blocked out identifying information of who send it and what college is involved. I doubt I needed to legally but... you never know.) I include my comments on the email in cap letters.<br />
<br />
I am NOT flattered by the email. I have LESS regard for those who send it.<br />
<br />
I will say that the school is respectable and I had heard of them. I'm just surprised they heard of me.<br />
<br />
(The letter was typeset fine- if there are problems with typesetting below thats on me.)<br />
<br />
---------------------------------------------------------------<br />
Dear Dr. Gasarch,<br />
<br />
XXX Inc. has been retained to assist XXX University in the search for the<br />
next Chair of the Computer Science and Engineering Department.<br />
<br />
ADMIN EXPERIENCE: RUNNING AN REU PROGRAM. NOT NEARLY ENOUGH.<br />
<br />
Your expertise and accomplishments have come to our attention, and we would appreciate the opportunity to speak with you about this position.<br />
<br />
IF THEY MEAN ADMIN-EXPERTISE, THATS JUST SILLY.<br />
<br />
IF THEY MEAN PAPERS AND SUCH... LETS JUST SAY I AM ON THE OBSCURE END OF THEORY AND WONDER WHAT ACCOMPLISHMENTS THEY MEAN. MY MUFFIN PAPER?<br />
<br />
EXPERTISE: MENTORING HS AND UGRAD STUDENTS. BLOGGING? EXPERT OR NOT I"VE DONE IT FOR A WHILE. NOT THE STUFF OF CHAIR'S.<br />
<br />
Could you suggest some times over the next week that<br />
might work for your schedule? We will be very respectful of your time.<br />
<br />
<br />
XXX is located in XXX, XX where the city’s diverse and growing population puts it in the<br />
Top 10 U.S. cities in population and in the Top 5 fastest growing cities. XXX has an endowment of $1.5B and recently completed a $1.3B campaign. The Computer Science and Engineering Department has been targeted for significant advancement and new faculty hires. The next Department Chair will lead and direct this enhancement.<br />
<br />
<br />
The XXX Metroplex is a dynamic region with leading high-technology companies in the aerospace,<br />
defense, energy, information technology, life sciences, semiconductors, telecommunications,<br />
transportation, and biomedical industries. Some of the top companies and research institutes with a strong presence in the XXX area include LONG LIST OF COMPANIES I HAVE HEARD OF.<br />
<br />
THESE LAST TWO PARAGRAPHS WOULD BE A LOT MORE IMPRESSIVE IF I DIDN"T KNOW THEIR WAY TO PICK CANDIDATES TO ASK TO APPLY WAS SO TERRIBLE.<br />
<br />
Please click here to view a two-minute video in which the President, Provost, and Dean of the<br />
XXX School of Engineering at XXX discuss some of the possibilities for research and growth<br />
that the Chair of Computer Science and Engineering will have the opportunity to develop.<br />
Cybersecurity, particularly, is an identified area for growth and hiring to directly complement the XXX Institute for Cyber Security. A full listing of the qualifications and duties of the position can be found in the profile under “Current Searches” at XXX<br />
<br />
CYBERSECURITY- I HAVE TAUGHT A 1-CREDIT MINI-COURSE IN CRYPTO. I HAVE A SURVEY AND A PAPER ON PRIVATE INFO RETRIEVAL. I DOUBT THAT'S WHY THEY CONTACTED ME.<br />
<br />
<br />
Best,<br />
<br />
XXX<br />
-------------------------------------------------<br />
<br />
So why did they email me? Speculation<br />
<br />
1) They meant to email Lance and got confused.<br />
<br />
2) They cast a VERY wide net. The UPSIDE of doing that so is that they might find someone<br />
they would have overlooked. The DOWNSIDE of doing that is... thats the problem with<br />
spam- there is absolutely no downside.<br />
<br />
3) They emailed every computer science professor who has a wikipedia page? a blog? a book?<br />
Some criteria which I happened to fit.<br />
<div>
<br /></div>
<br />
<br />https://blog.computationalcomplexity.org/2018/05/why-is-someone-emailing-me-offer-to.htmlnoreply@blogger.com (GASARCH)5tag:blogger.com,1999:blog-3722233.post-6550933808686728606Thu, 24 May 2018 15:15:00 +00002018-05-24T11:18:12.595-04:00Kolmogorov Complexity and Causation<div class="tr_bq" style="font-family: sans-serif; font-size: 13px;">
<br /></div>
<div style="font-family: sans-serif; font-size: 13px;">
I got an interesting email question.</div>
<blockquote style="font-family: sans-serif; font-size: 13px;">
Suppose I give you a set of points S of the form (x,y). He suggested ideally they would be pairs of a real numbers. Supposing there is a causal relationship between x and y of some kind, we want to know know if it is more likely that the x value causes the y value or the y value causes the x value. One plausible way to decide what the answer should be is by answering the question <b>is the length of the shortest program which maps the x values to their y values shorter than the length of the shortest program which maps the y values to their x values.</b></blockquote>
<blockquote style="font-family: sans-serif; font-size: 13px;">
So, my intuition says that this is clearly undecidable. I'm actually having a hard time thinking of a proof, so do you happen to know of one or if this problem might actually be decidable?</blockquote>
<blockquote style="font-family: sans-serif; font-size: 13px;">
On a related note, since I'm already writing you about this question, do you happen to know about the complexity of any related questions which involve circuit size instead of program length? </blockquote>
Let's use notation from Kolmogorov complexity, letting C(x|y) be the size of the smallest program that takes y as input and outputs x. Now suppose it is decidable to determine whether C(x|y) > C(y|x). Then find an x of length n such that for all y of length n/3, C(x|y)>C(y|x). Such x exist: For any random x, C(x|y)>= 2n/3 and C(y|x) <= n/3.<br />
<br />
Now I claim C(x)>=n/4 for the x you found. If not we have C(x|y)<=C(x)<n/4 but for some y, C(y|x)>=n/3 since there aren't enough shorter programs to cover all the y's.<br />
<br />
Since there is no computable procedure to find x such that C(x)>=n/4, there can't be decidable procedure to determine whether C(x|y) > C(y|x).<br />
<br />
But does this question relate to causality. Pick a random x from strings of length n and y at random from strings of length n/3. We have C(x|y) > C(y|x) even though there is no causality.<br />
<br />
Instead you could look at the information of y in x, how many bit of x does y help describe, defined by I(y|x) = C(x)-C(x|y). This measure correlation since I(y|x)=0 iff x and y are independent but symmetry of information gives I(y|x)=I(x|y) so no hope for causation.<br />
<br />
In short, Kolmogorov complexity won't give you much on causation--you can't avoid the controlled experiments.<br />
<br />
For your last question, there is a notion of Kolmogorov complexity that roughly corresponds to circuit size, KT(x|y) defined as the sum of the program size and running time minimized over all programs p that take y as an input and output x. I'm guessing it's hard to determine if KT(x|y) < KT(y|x) and you could probably show it under some assumption like secure psuedorandom generators. Also symmetry of information isn't believed to hold for KT complexity so maybe there is something there. Interesting questions.https://blog.computationalcomplexity.org/2018/05/kolmogorov-complexity-and-causation.htmlnoreply@blogger.com (Lance Fortnow)6tag:blogger.com,1999:blog-3722233.post-1382101806799648760Mon, 21 May 2018 02:44:00 +00002018-05-20T22:44:17.759-04:00COMPUTER PROOF vs computer proof- Quadratic VDW theorem<b>Quad VDW Theorem: </b>For all c there exists W=W(c) such that for all c-colorings of {1,...,W} there exists a,d such that a and a+d<sup>2</sup> are the same color.<br />
<br />
What is known about W(c)?<br />
<br />
The first proof of Quad VDW was nonconstructive.<br />
<br />
The second proof was constructive but used VDW's theorem and gave terrible bounds, even for W(2).<br />
<br />
EASY: Show W(2)=5<br />
<br />
ON A HS MATH COMP: Show that for all 3-colorings of {1,...,2003} there exists two numbers a square apart that are the same color.<br />
<br />
One can get a bound less than 100.<br />
<br />
With a lot more detailed work one can get W(3)=29.<br />
<br />
None of above was done with a computer.<br />
<br />
SO- what about W(4)? There are three proofs that W(4) exists:<br />
<br />
a) Prove the QUAD VDW theorem. This gives terrible bounds.<br />
<br />
b) I had some students use SAT solvers and they obtained W(4)=58. I am sure they are right and I am glad to know it (especially since it confirms the general mantra that the bounds from proofs in Ramsey theory tend to be much bigger than the reality) but its somehow unsatisfying. I want a <i>HS proof. </i>I wanted to put it on the MD Math Comp for 2017 but wiser people prevailed.<br />
<br />
c) I gave the problem to a Grad Student Zach Price and he came up with a HS proof-- sort of. Look at the following graph: <a href="https://www.cs.umd.edu/users/gasarch/COURSES/858/S18/qvdw4.pdf">here</a>. It shows that in any 4-coloring of N which does not have two numbers a square apart the same color:<br />
<br />
COL(x) = COL(x+290085289)<br />
<br />
from this one can obtain<br />
<br />
W(4) ≤ 290085289<sup>2</sup> (which is MUCH better than the bound from the proof of Quad VDW) and hence a proof of QVDW that does not need a program, except that to FIND this gadget used a program. I doubt a HS student could do this on an exam.<br />
<br />
Is Zach's proof the HS proof I am looking for?<br />
<br />
PRO- once you see it its easy to verify and does not need a program.<br />
<br />
CON- coming up with it needed a program.<br />
<br />
More to the point: which proof do you like better:<br />
<br />
1) The SAT Solver proof. Not a proof you can see or feel, but gives exact bounds.<br />
<br />
or<br />
<br />
2) Zach's gadget proof. Much worse bound but you can see and feel the proof, and verify it after you know the gadget.<br />
<br />
I prefer Zach's proof.<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/05/computer-proof-vs-computer-proof.htmlnoreply@blogger.com (GASARCH)6