Complexity in Oxford

Oxford, 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 wonderful workshop this past week. It's my first trip to Oxford since I came five years ago to celebrate the opening of the Andrew Wiles building, a building that hosted this weeks' workshop as well.

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.

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.

A few highlights of the many great talks.

Sasha Razborov gave a nice discussion of proof systems that help us understand what makes circuit bounds hard to prove.

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 new oracle with Ran Raz, 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 pull out quantumness in relativized worlds.

Toni Pitassi talked about lifting--creating a tight connection between decision tree and 

complexity bounds to export lower bounds from one model to the other. Yuval Ishai talked about the continued symbiosis between complexity and theoretical cryptography.

Ryan Williams talked about his approach of using circuit satisfiability algorithms to prove lower bounds that led to his famed NEXP not in ACC⁰ result. He has had considerable recent progress including his recent work with Cody Murray getting reducing NEXP to nondeterministic quasipolynomial time.

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. 

Need EASY approaches to getting unif random from non-random sources

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

I"m also finding out that the web is great for easy and hard stuff but not so good for medium stuff.

Here is what I want to know so I am reaching out to my readers.

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

if see 00 then DO NOT USE

if see 11 then DO NOT USE

if see 01 then generate 0

if see 10 then generate 1

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.

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?

CRA Snowbird 2018

Marios Papaefthymiou (UC Irvine), Michael Franklin (U. Chicago), Larry Birnbaum (Northwestern) and me.

This week I attended the 2018 Computing Research Association Snowbird conference, a biennial 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.

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.

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.

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 conference harassment policy and many CS communities, including theoretical computer science, 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.

One session focused on pushing metric-based rankings of computer science programs with presentations of Microsoft Academic Search, CRA’s own CS metrics and Emery Berger’s CS Rankings. 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.

Personally I prefer the reputation-based rankings like US News, but I was definitely the tiny minority in the room.

The Mystical Bond Between Man and Machine

You just can't watch a movie these days without being inundated with trailers. First came Axl, a movie about a boys love for a military robotic dog.

 

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

Next came a trailer 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 Herbie movie or Transformers. Spoiler: Transformers.


"There's a mystical bond between man and machine" the voice intones. Followed by action that looks just like Axl.

Movie love for machines is hardly new. You can go back to Her or Short Circuit or even Metropolis in 1927. But in an age that parents worry about their kids being rude to Alexa perhaps this mystical bond is starting to get just a little too real.

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.

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?

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.

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.