Thursday, July 12, 2018

The 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 here 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.

How many degrees of separation were there from his work and the so called application.

  1. The best (at the time) Matrix Multiplication algorithm used 3-free sets.
  2. 3-free sets are used to get lower bounds on VDW numbers.
  3. Lower bounds on VDW numbers are related to upper bounds on VDW numbers
  4. Upper bounds on VDW are related to upper bounds on PVDW numbers.
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.

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 degree and application.

Monday, July 09, 2018

Soliciting answers for THIRD survey about P vs NP



I have done two surveys for SIGACT NEWS Complextiy Column (edited by Lane Hemaspaandra)
on P vs NP and related topics.  Lane has asked me to do a third. I annouced it in my open problems column here For those who don't read SIGACT news

1) You should!

2) Here is where to go to fill out the survey: here

bill g.

P.S. (do people use P.S. anymore? Do young people know that it means Post Script, and that it
does not refer to ps-files?)

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).

Okay, enough babbling -- the point is that I should have a deadline for those who read the blog later than now.

DEADLINE: Oct 1, 2018. STRICT!

P.P.S - does anyone use P.P.S anymore?




Thursday, July 05, 2018

Happy 90th Juris!

Juris Hartmanis turns 90 today. Hartmanis with Richard Stearns received the 1993 Turing Award for their seminar work On the Computational Complexity of Algorithms. I've talked about that paper before, 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.

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.

In that same semester I took Introduction to Linguistics. Chomsky and context-free languages in both classes. Seemed cool at the time.

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 Berman-Hartmanis Isomorphism Conjecture. 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 couple of proofs giving an oracle making BH true. That should be good enough for a B.

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.

Monday, July 02, 2018

The 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: here)

As many of you know there was a BREAKTHROUGH on the problem of the The Chromatic Number of The Plane. There have been fine blog posts on this by Gil Kalai here amd Scott Aaronson here. 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 here for the amazon link to the book and here 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.

Alexander also is the editor of a journal on problems like this called GEOCOMBINATORICS (oddly enough. Geometric Combinatorics is a different field). See here for that journal- which I recommend!

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
and Dan Ismailescu.

What I find remarkable is that even though the result is new, the essay contains NEWER results. The modern world moves fast!

Without further ado, here is that essay: here.