Wednesday, March 14, 2018

Stephen Hawking (1942-2018)

Stephen Hawking passed away earlier this morning in Cambridge, England. As a brilliant theoretical physicist and best-selling author all while dealing with a debilitating disease, Hawking rose to be the best-known scientist of his time. 

I'll leave it to the physics blogs to talk about his research. Hawking inspired me through his 1988 book, A Brief History of Time. Hawking told Time magazine before the magazine's publication "Someone told me that each equation I included in the book would halve the sales. In the end, however, I did put in Einstein’s famous equation E = mc2. I hope that this will not scare off half my potential readers.”

So you read the book and he manages to describe his highly mathematical-based view of the universe without resorting to mathematics, by far the best written popular science book I have read.

A Brief History of Time came out when I was in grad school so it didn't play a role in me becoming an academic but it did make me realize that science has a story to tell. From the preface of my own book.
I took inspiration from Stephen Hawking's A Brief History of Time, which explains physics not through formulas and technicalities but with examples and stories. I attempt to do the same here to explore the spirit and importance of the P versus NP problem.
I am under no illusion that I came even close to Hawking's level of exposition.

A poll taken last year showed most Americans could not name a single living scientist but among the 19% that could, the scientist they named most often was Stephen Hawking. We lost not only a brilliant physicist but one of the great symbols for science of our generation.

Monday, March 12, 2018

Wanted: An Easy Proof of a Weak Theorem in NT so that I can get another VDW--> Primes infinite proof to be really easy.

(All math in this article is here)

A while back I posted about a proof that Van Der Waerden's theorem implies the number of primes
is infinite (see the post here). That post brought up some logical issues.

More recently there is another proof that the primes are infinite that raises (for me at least) some number theory results and proofs. The proof uses the following theorem:

There are no 4-length Arithmetic Progressions consisting of squares.

This is attributed to Fermat. All of the proofs I've seen of it look difficult.

Here is a sketch of the proof of infinite number of primes from VDW and the theorem above.
Assume that {p1,...,pm} are all of the primes.  Let vi(n) be the power of pi in the factorization of n.

We define the following 2m coloring of N

COL(n) = ( v1(n) mod 2, ... vm(n) mod 2)

There exists a monochromatic 4-AP.  We leave it to the reader to show that you can use this to get a 4-AP of squares.

Using Fermats 4-AP theorem is hard!  In the write up I show how to use a stronger VDW theorem and a weaker (at least easier to prove in my opinion) result in Number Theory to get a different proof.

VDWPlus: for all k,c there exists W such that for all c-colorings of [W] there exists a,d such that

a, a+d, a+2d, ..., a+(k-1)d AND d (that's the PLUS part) are all the same color.

Now to prove primes are infinite. Assume not. p1,...,pm are all of the primes.

Let vi(n) be as above

COL(n) = (v1(n) mod 4, ..., vm(n) mod 4)

just apply this to the k=1 case so we have

a, a+d, d all the same color.  Say the color is (b1,...,bm) where bi in {0,1,2,3}

mult all three by p1^{4-b1} ... pm^{4-bm}.

now we have A, A+D, D all four powers. call them x^4, z^4, y^4 and you
contradict the n=4 case of Fermat'ls last theorem (this is the easiest case and was proven by Fermat)

TO DO: find an even easier theorem in Number Theory to use with a perhaps more advanced form of VDW theorem to get a proof that primes are infinite.

Coda: Cute that I replace one theorem by Fermat with another theorem by Fermat.

Friday, March 09, 2018

Data-Driven Programming

Five years ago I posted about Flash Fill, a then new Microsoft Excel feature that would reformat data based on examples. I just checked the latest version of Excel and Flash Fill is still there just working by making suggestions when appropriate. It uses a programming language approach finding the simplest string manipulation program consistent with the examples.

I loved the idea of example-based programming but it did seem pretty limited at the time. With the machine learning revolution we've gone full circle. We solve a number of problems with data and examples alone: voice recognition, face recognition, spam detection, playing Chess and Go from scratch in ways we wouldn't even know how to program.

That's not completely true: Designing a good machine learning program requires programming to get data in a good format and creating the right network structure to learn is still considerably an art. But the real magic does happen when the deep learning process happens creating a neural net that works well in ways we can't fully understand even when we look at the final network produced.

Now "it's all about the data". This hit me when I got an email invitation for the Uber visa card. Unlike other branded cards it gives you no particular discounts or rewards for Uber. Rather it gives you significant cash back for dining and travel, in other words for giving Uber the data about you that can make Uber itself more valuable to you.

Nothing in this post should be new to you readers. But every now and then just take a breadth and realize who much our notions of computing and data have changed over even the past five years.

Programmers aren't going away. Machine learning works well for things humans do well instinctively. But for actual number crunching, simulations and manipulation, even what Flash Fill does, machine learning has much more to do.

Wednesday, March 07, 2018

When the Wrong People raise the issue

On my discrete math final in Spring 2017 I had a question:

Prove that sqrt(2/3) is irrational.

A student emailed me the folloing (I paraphrase and am prob not as elegant or as long as he was)

Dr. Gasarch

I received only 2 points out of 20 on Problem 3 of the final- the one that asked us to prove that sqrt(2/3) is irrational. This was graded rather harshly, and the reason is endemic to the entire course. It was unclear what we could and could not assume in this problem. That has been unclear all semester.

I responded (I leave out the name for privacy)

Mr. Student

Come by my office and we will look over  your final. At the same time, bring by your HWs and Midterms to look at. The deadline for regrading those is up; however, either you are correct and I will learn how to run a better course by looking over your HWs and midterms, or you incorrect and you will be enlightened by us looking over them.

We agreed to meet. The Student came all ready to  argue not just points on the final but also about the course in general. I looked forward to this since either I would learn about how to run the course better OR I would enlighten a student!

STUDENT:  I used the obvious fact that the ratio of two irrationals is irrational. How was I supposed to know I had to prove something so obvious!!!!!!!! And only 2 points!!!!!!! Really!!!!!!

BILL: What is the ratio of \sqrt{8} to \sqrt{2}.

STUDENT:  sqrt(8)/sqrt(2) = sqrt(8/2) = sqrt(4) = 2. Why is that relevant?

BILL: You just showed that the ratio of two irrationals could be rational.


BILL: Lets look over your HW and midterm and see there were times when it was not clear what you could assume OR if not then I can clear up some misconception you had.

STUDENT: Uh, Uh. Nevermind.

BILL: You are here with your HWs and midterms, lets take a look.

He really didn't want to. I think he really just wanted more points on the final But since he phrased it as a philosphical debate about how the course was run, I took him at his word.  Everything he showed me was either clearly wrong or clearly unclear. None of it fell into the category of `not clear what you can assume'.

This disappointed me. I suspect someone could make a case that my course sometimes does not make it clear what you can assume. Other students with a similar story as above claim my course is to pedantic. But the examples they show me of this are usually just wrong, not marked wrong for being to pedantic.

There is a more general problem here. The students who complain about a  course may well have a valid point to make!  But its usually students who are not very good making the complaint, and hence they are not the ones who could make a good argument.  One thing I have done when a student has a complaint about how I run the course is then ask my TAs about it. This has been helpful sometimes but they are on the other end -- the course is easy for them so its hard for them to see the problems.

Having said all of this I will own up to one flaw I've had which the students complained about incoherently  (see here) and my TA pointed out the fair objection.  I had taught ONE type of Pigeon hold argument and tested them on a very closely related but different type -- as a way of testing if they understood pigeon hole and were not just memorizing. It was a fair question BUT my TA said
(correctly) I was more interested in getting a good test question then, you know, TEACHING them the Pigeon hole principle -- so I should in the future (and I have) teach them LOTS of versions, make sure they understand them, and then if on the exam I give them a variant its more fair. But more importantly he pointed out that I (and this is correct, or was) have a QUESTION I really want to put on the midterm and then teach the course so that it makes sense to do so. The question is fair, but this is NOT the point (which is why the students objections were incoherent- the question was fair). I am setting (some of them) up to fail.  I have CHANGED my Teaching style and exam style since them.

But my point is that the students could not possibly have raised that objection-- partly because the students complaining are not very good, but also because they do not see what goes on behind the scenes.

UPSHOT- if your students have an incoherent complaint there may be something to it and you should ask your TAs.

Thursday, March 01, 2018

Me and My Bolt

On Tuesday I got a knock on my car's window. Rolling it down someone asked if I liked my car as he was thinking of buying one himself. Was I driving the latest Tesla? No, the Chevy Bolt, General Motor's newest fully electric car.

On March 31, 2016 me and 180,000 of my closest friends put $1000 down sight unseen on the Tesla 3. As an east coast resident with no prior Tesla I am well down the list even though I made a reservation on the first day. I got disillusioned by early production problems and delays and bait-and-switch emails.
Now that some more details regarding Model 3 came out, I wanted to gauge your interest in coming in for a test drive in a Model S. An incredibly well equipped Model S can be had for under $80k and with the $7500 federal tax credit and $1000 referral code from a current owner, you can get into a Model S for close to $70k, meanwhile a Model 3 can cost up to $60k. Model S is considerably quicker and has an incredible amount of space to seat 5 comfortably. It is our flagship vehicle and has 5 years of manufacturing behind it to perfect the build quality of the car. Not to mention a quick turnaround time on delivery. I would love to host you in our showroom so I can showcase some of the incredible features in the Model S.
Meanwhile a GM executive on the Georgia Tech College of Computing's advisory board suggested I take a look at the Bolt. I was skeptical but he arranged for a local dealer to bring down a car to test drive. I got sold and bought my own Bolt in December.

It's an all electric car with no transmission so quick smooth acceleration. The Bolt has a one pedal driving mode as the "gas" pedal also works as a break which slows down the car by pulling power to the battery. The car doesn't even pretend to be mechanical, a screen boots up when I turn the car on, you can shift into park by pressing a button. The rear view "mirror" is really a camera. When driving slowly there is a simulated view from above. A little freaky but it helps with parking. With Android Auto I basically have Google Assistant and Maps in the car which I prefer to an in-car navigation the Bolt doesn't have.

I get over 200 miles on a full charge and can plug in overnight to get enough power to get to work and back. The car has considerable safety features that warn about cars in blind sports or getting too close to the car in front of you or if you drift from lanes. The Bolt lacks any autonomous features even adaptive cruise control or parking assist. I suspect you could get significant autonomous behavior with a software upgrade but I doubt GM would ever do so.

The car is missing some basic features like power seats and a garage door button. No problem, I rigged up Google Assistant to open the garage door when I say the magic words. Far cooler than pressing a button.

It's not as sleek looking as a Tesla and nobody will shoot it into space but I'm driving the future and it is amazing.

Sunday, February 25, 2018

When students are wrong but have a valid point, encourage them

I often have the class VOTE on a statement (the choices are usually TRUE/FALSE/UNKNOWN TO SCIENCE/Stewart-Colbert-2020)

I ask the students who voted incorrectly (some say anything except Stewart-Colbert-2020 is an incorrect vote, though I'm partial to Bee-Oliver, though John Oliver was not born in this country so he's not eligible, though our current president might say that neither was Obama so thats not a bar to the presidency) why they vote the way they do to get a good discussion going. I give some examples. I use real first names but decided to not give last names for reasons of security. The people involved all agreed. If you have examples of students being WRONG but HAVING A POINT, leave an intelligent comment about it!

1) In Discrete Math they  vote on: is Q, the rationals, countable?One of the NO votes was named Alice (really!).

Alice: The rationals, like there are SO many of them. They are just so crammed in their. I mean really!

Bill: I think you want to say that between any two rationals is a rational.

Alice: Thats what I said!!

Bill: Great! And realize that  a set is countable if there is a bijection from the  set to N. So what you are really saying is-----

Alice: There is a bijection between N and Q but not an order preserving Bijection!

2) In Formal Lang theory they vote if alpha is a reg expression and L(alpha) is the lang generated by alpha then is there a reg exp beta such that L(beta) is the complement of L(alpha). One of the NO votes was named Andrea (nickname Andy).

Andy: Given alpha I just don't see an easy way, or for that matter any way, to create beta.

Bill: I will soon prove that regular expressions are equivalent  to DFA's. So what one would do is take the L(alpha), form the DFA, complement the DFA, then convert back to a regular expression.

Andy: Oh, yes that works, but it seems complicated.

Bill: It is! You though it would be complicated so it was false. Even though its true, your intuition that its complicated is correct! In fact, there are reg expressions of length n such that the complement lang has a rather large reg expression.

3) Formal Lang theory again. Not a vote this time. I had on the board the regular expression

(a UNION b)(a UNION  b )^*

A student Dolapo thought it could be simplified:

Dolapo: Can't you write that as the regular expression (a union b)^+ ?

Bill: Yes and no. Yes the lang is (a UNION b)^+, but + is not allowed in regular expressions.

Dolapo: Why not?

Bill: First off, they really could have been defined that way and perhaps should have. So why weren't they? I go with historical accident, but some people disagree- see my blog post here

Thursday, February 22, 2018

NP is Hard

You don't get much press by stating conventional beliefs--there is no "round earth society". Nevertheless there are serious researchers out there trying to say that it is reasonably possible if not likely that P = NP. Don't believe it.

Emanuele Viola just outright states I Believe P = NP. He starts with a similar argument that we've seen from Richard Lipton: We've had surprising results in the past so why should the convention wisdom that P ≠ NP be true? I have two major problems with this line of reasoning:
  • These arguments cherry pick certain results and ignore the vast majority of theorems that went the way we expected. It's akin to saying that because there have been lottery winners in the past, the ticket I hold in my hand is likely to be a winner.
  • All the major surprises in complexity have occurred early in first two decades of the P v NP era. We've seen no surprises at that level since the early 90's. We have seen surprise proofs of results like Primes in P, Undirected Connectivity in Log Space and NEXP not in ACC0 but the theorems themselves surprised no one. 
Viola also makes the argument that we've seen fewer significant lower bound results than upper bounds. This doesn't surprise me--an upper bound requires a single algorithm, a lower bound requires showing an infinite number of algorithms can't work. I fully agree that we're unlikely to see a proof that P ≠ NP in the near future. But this isn't a reason to think they are the same. And we've seen no non-trivial algorithms for general NP problems like circuit-SAT.

Which takes me to Ryan Williams Some Estimated Likelihoods For Computational Complexity where he gives 20% probability (which I consider nearly 20% too high) that P = NP based on similar logic. Ryan surprises me even more by giving a whopping 80% chance that NEXP = coNEXP. That would imply every easily describable tautology has a short proof of being a tautology (for the appropriate definitions of describable and short) which I find hard to fathom.

If I would guess collapses that might happen, I would suggest L = NL (directed connectivity in log space) or one that Ryan gives even odds, TC0 = NC1. TC0 captures constant-depth neural networks and as we've seen from the ML community, those neural nets look awfully powerful. 

Sunday, February 18, 2018

The web bad/People using it bad.

I was going to write a post about how hard it was to find what grades mean at different schools (e.g., at UMCP W (for withdraw) means the student dropped the course, but at UT Austin its Q (for Quit?)) but then I found that my Googling

Name of school grade key

I could find it.  Okay, so grade keys are not that hard to find.


However, course descriptions are. Both questions (what grades mean and course desc) came up when I do admissions for my REU program.  If a student has a course in Discrete Mathematics that could mean a course where you learn how to prove simple things OR it could mean a course where you proof  the graph minor theorem (actually I doubt that) or something in between. Similar for Principles of Programming languages and Software Engineering in that they could mean a variety of things. I think math and physics are more standardized, but even there you have the problem that Advanced calc could be either multivar or a course with proofs or something else. There is a great related XKCD here.


Fellow blogger Scott Aaronson recently posted about Vivek Wadhwa's Washington post column on quantum computing (the post is here) The article by Vivek told the tired and utterly false story that QC can be used to solve TSP by looking at all possibilities. Should Vivik have known better by looking at the web? At first I thought YES he should know better. But then I thought -- I should try to see what he might have done. Maybe the web has this one wrong. In fact, some of my students Iwho, I should add, are not writing articles on QC for the Washington Post)  tell me that they don't need to learn the proof of the Cook-Levin theorem since Quantum Computers can solve SAT anyway.  So I decided to pretend I didn't know anything about QC and went to the web to see what I could find.  First stop: Wikipedia. I found the following quote in the QC article:

BQP is suspected  to be disjoint from NP-complete and  a strict superset of P though this is not known.

So, the first place I look I find that BQP is suspected to NOT solve SAT or TSP or... Realize that Wikipedia is not some obscure source of  hidden knowledge. It is literally the first place one would look.  Hence, no excuse, even if other experts told him otherwise (which seems to be the case, though `experts'  should be in quotes) the Wikipedia quote should at least give pause.

So even when Wikipedia gives the right information, not everyone looks there.