Thursday, April 16, 2015

PH Infinite Under a Random Oracle

Benjamin Rossman, Rocco Servedio and Li-Yang Tan show new circuit lower bounds that imply, among other things, that the polynomial-time hierarchy is infinite relative to a random oracle. What does that mean, and why is it important?

The polynomial-time hierarchy can be defined inductively as follows: ΣP= P, the set of problems solvable in polynomial-time. ΣPi+1 = NPΣPi, the set of problems computable in nondeterministic polynomial-time that can ask arbitrary questions to the previous level. We say the polynomial-time hierarchy is infinite if ΣPi+1 ≠ ΣPi for all i and it collapses otherwise.

Whether the polynomial-time hierarchy is infinite is one of the major assumptions in computational complexity and would imply a large number of statements we believe to be true including that NP-complete problems do not have small circuits and that Graph Isomorphism is not co-NP-complete.

We don't have the techniques to settle whether or not the polynomial-time hierarchy is infinite so we can look at relativized worlds, where all machines have access to the same oracle. The Baker-Gill-Solovay oracle that makes P = NP also collapses the hierarchy. Finding an oracle that makes the hierarchy infinite was a larger challenge and required new results in circuit complexity.

In 1985, Yao in his paper Separating the polynomial-time hierarchy by oracles showed that there were functions that had small depth d+1 circuits but large depth d circuits which was needed for the oracle. Håstad gave a simplified proof. Cai proved that PSPACE ≠ ΣPi for all i even if we choose the oracle at random (with probability one). Babai later and independently gave a simpler proof.

Whether a randomly chosen oracle would make the hierarchy infinite required showing the depth separation of circuits in the average case which remained open for three decades. Rossman, Servedio and Tan solved that circuit problem and get the random oracle result as a consequence. They build on Håstad's proof technique of randomly restricting variables to true and false. Rossman et al. generalize to a random projection method that projects onto a new set of variables. Read their paper to see all the details.

In 1994, Ron Book showed that if the polynomial-time hierarchy was infinite that it remained infinite relativized to a random oracle. Rossman et al. thus gives even more evidence to believe that the hierarchy is indeed infinite, in the sense that if they had proven the opposite result than the hierarchy would have collapsed.

I used Book's paper to show that a number of complexity hypothesis held simultaneously with the hierarchy being infinite, now a trivial consequence of the Rossman et al. result. I can live with that.

Tuesday, April 14, 2015

Baseball is More Than Data

As baseball starts its second week, lets reflect a bit on how data analytics has changed the game. Not just the Moneyball phenomenon of ranking players but also the extensive use of defensive shifts (repositioning the infielders and outfielders for each batter) and other maneuvers. We're not quite to the point that technology can replace managers and umpires but give it another decade or two.

We've seen a huge increase in data analysis in sports. ESPN ranked teams based on their use of analytics and it correlates well with how those teams are faring. Eventually everyone will use the same learning algorithms and games will just be a random coin toss with coins weighted by how much each team can spend.

Steve Kettmann wrote an NYT op-ed piece Don't Let StatisticsRuin Baseball. At first I thought this was just another luddite who will be left behind but he makes a salient point. We don’t go to baseball to watch the stats. We go to see people play. We enjoy the suspense of every pitch, the one-on-one battle between pitcher and batter and the great defensive moves. Maybe statistics can tell which players a team should acquire and where the fielders should stand but it still is people that play the game.

Kettmann worries about the obsession of baseball writers with statistics. Those who write based on stats can be replaced by machines. Baseball is a great game to listen on the radio for the best broadcasters don't talk about the numbers, they talk about the people. Otherwise you might as well listen to competitive tic-tac-toe.

Thursday, April 09, 2015

FCRC 2015

Every four years the Association for Computing Machinery organizes a Federated Computing Research Conference consisting of several co-located conferences and some joint events. This year's event will be held June 13-20 in Portland, Oregon and includes Michael Stonebraker's Turing award lecture. There is a single registration site for all conferences (early deadline May 18th) and I recommend booking hotels early and definitely before the May 16th cutoff.

Theoretical computer science is well represented.
The CRA-W is organizing mentoring workshops for early career and mid-career faculty and faculty supervising undergraduate research.

A number of other major conferences will also be part of FCRC including HPDC, ISCA, PLDI and SIGMETRICS. There are many algorithmic challenges in all these areas and FCRC really gives you an opportunity to sit in talks outside your comfort zone. You might be surprised in what you see.

See you in Portland!

Tuesday, April 07, 2015

Two cutoffs about Warings problem for cubes

  1. All numbers except 23 can be written as the sum of 8 cubes
  2. All but a finite number of numbers can be written as the sum of 7 cubes 
  3. There are an infinite number of numbers that cannot be written as the sum of 3 cubes(this you can prove yourself, the other two are hard, deep theorems).
Open: Find x such that:
  1. All but a finite number of numbers can be written as the sum of x cubes.
  2. There exists an infinite number of numbers that cannot be written as the sum of x-1 cubes.
It is known that 4 ≤ x ≤ 7

Lets say you didn't know any of this and were looking at empirical data.

  1. If you find that every number ≤ 10 can be written as the sum of 7 cubes this is NOT interesting because 10 is too small.
  2.  If you find that every number ≤ 1,000,000 except 23 can be written as the sum of 8 cubes this IS interesting since 1,000,000 is big enough that one thinks this is telling us something (though we could be wrong). What if you find all but 10 numbers (I do not know if that is true) ≤ 1,000,000 are the sum of seven cubes?
Open but too informal to be a real question: Find x such that
  1. Information about sums-of-cubes for all numbers ≤ x-1 is NOT interesting
  2. Information about sums-of-cubes for all numbers ≤ x IS interesting.
By the intermediate value theorem such an x exists. But of course this is silly. The fallacy probably relies on the informal notion `interesting'. But a serious question: How big does x have to be before data about this would be considered interesting? (NO- I won't come back with `what about x-1').

More advanced form: Find a function f(x,y) and constants c1 and c2 such that
  1. If f(x,y) ≥ c1  then the statement all but y numbers ≤ x are the sum of 7 cubes is interesting.
  2. If f(x,y) ≤  c2 then the statement all but y numbers ≤ x are the sum of 7 cubes is not interesting. 
To end with a more concrete question: Show that there are an infinite number of numbers that cannot be written as the sum of 14 4th powers.

Wednesday, April 01, 2015

Which of these stories is false

I would rather challenge you than fool you on April fools day. Below I have some news items. All but one are true. I challenge you to determine which one is false.

  1. Amazon open a brick and mortar store: Full story here. If true this is really really odd since I thought they saved time and money by not having stores.
  2. You may have heard of some music groups releasing Vinyl albums in recent times. They come with an MP3 chip so I doubt the buyers ever use Vinyl,but the size allows for more interesting art. What did people record on before Vinyl. Wax Cylinders! Some music groups have released songs on wax cylinders! See here for a release a while back by Tiny Tim (the singer, not the fictional character) and here for a release by a group whose name is  The Men Will Not Be Blamed For Anything.
  3. An error in Google Maps lead to Nicaragua accidentally invading Costa Rica. Even more amazing--- This excuse was correct and Google admitted the error. See here for details.
  4. There was a conference called Galileo was wrong, The Church Was Right for people who think the Earth really is the centre of the universe (my spell checker says that `center' is wrong and `centre' is right. Maybe its from England). I assume they mean that the sun and other stuff goes around the earth in concentric circles, and not that one can take any ref point and call it the center. The conference is run by Robert Sungenesis  who also wrote a book on the topic (its on Amazon  here and the comments section actually has a debate on the merits of his point of view.) There is also a website on the topic here.  The Catholic Church does not support him or his point of view, and in fact asked him to take ``Catholic'' out of the name of his organization, which he has done. (ADDED LATER- A commenter named Shane Chubbs, who has read over the relevent material on this case more carefully than I have, commented that Robert Sungenesis DOES claim that we can take the center of the universe to be anywhere, so it mine as well be here.   If thats Roberts S's only point, its hard to believe he got a whole book out of it.) OH- this is one of the TRUE points.

Monday, March 30, 2015

Intuitive Proofs

As I mentioned a few months ago, I briefly joined an undergraduate research seminar my freshman year at Cornell. In that seminar I was asked if a two-dimensional random walk on a lattice would return to the origin infinitely often. I said of course. The advisor was impressed until he asked about three-dimensional walks and I said they also hit the origin infinitely often. My intuition was wrong.

33 years later I'd like to give the right intuition. This is rough intuition, not a proof, and I'm sure none of this is original with me.

In a 1-dimensional random walk, you will be at the origin on the nth step with probability about 1/n0.5. Since the sum of 1/n0.5 diverges this happens infinitely often.

In a 2-dimensional random walk, you will be at the origin on the nth step with probability about (1/n0.5)2 = 1/n. Since the sum of 1/n diverges this happens infinitely often.

In a 3-dimensional random walk, you will be at the origin on the nth step with probability about (1/n0.5)3 = 1/n1.5. Since the sum of 1/n1.5 converges this happens finitely often.

Wednesday, March 25, 2015

News Aplenty

Both the Turing Award and the Abel Prize were announced this morning.

MIT databases researcher Michael Stonebraker wins the ACM Turing Award. He developed INGRES one of the first relational databases. Stonebraker is the first Turing award winner since the prize went up to a cool million dollars.

John Nash and Louis Nirenberg share this years Abel Prize “for striking and seminal contributions to the theory of nonlinear partial differential equations and its applications to geometric analysis.” This work on PDEs is completely independent from the equilibrium results that won Nash the 1994 Nobel Prize.

Earlier this week the CRA released their latest Best Practice Memo: Incentivizing Quality and Impact: Evaluating Scholarship in Hiring, Tenure, and Promotion. In short: Emphasize quality over quantity in research.

The NSF announced their public access plan to ensure that research is "available for download, reading and analysis free of charge no later than 12 months after initial publication".

Sunday, March 22, 2015

Which mathematician had the biggest gap between fame and contribution?

(I was going to call this entry  Who was the worst mathematician of all time? but Clyde Kruskal reminded me that its not (say) Goldbach's fault that his conjecture got so well known, in fact its a good thing! I'll come back to Goldbach later.)

Would Hawking be as well known if he didn't have ALS?  I suspect that within Physics yes, but I doubt he would have had guest shots on ST:TNG, The Simpsons, Futurama, and The Big Bang Theory (I just checked the IDMB database- they don't mention Futurama but they do say he's a Capricorn. I find that appalling that they mention a Scientists Horoscope.) I also doubt there would be a movie about him.

Would Turing be as well known if he wasn't gay and didn't die young  (likely because of the ``treatment'') would he be as well known? I suspect that within Computer Science yes, but I doubt there would be a play, a movie, and there are rumors of a musical. Contrast him with John von Neumann who one could argue contributed as much as Turing, but, alas, no guest shots on I Love Lucy, no movie, no Rap songs about him. (The only scientist that there may be a rap song about is Heisenberg, and that doesn't count since it would really be about Walter White.)

Hawking and Turing are/were world class in their fields. Is there someone who is very well known but didn't do that much?

SO we are looking for a large gap between how well known the person is and how much math they actually did. This might be unfair to well-known people (it might be unfair to ME since complexityblog makes me better known than I would be otherwise).  However, I have AN answer that is defensible. Since the question is not that well defined there prob cannot be a definitive answer.

First lets consider Goldbach (who is NOT my answer). He was a professor  of math and did some stuff on the Theory of curves, diff eqs, and infinite series. Certainly respectable. But if not for his
conjecture (every even number is the sum of two primes- still open)  I doubt we would have heard of him.

My answer: Pythagoras! He is well known as a mathematician but there is no evidence that he had any connection to the theorem that bears his name.

Historians (or so-called historians) would say that it was well known that he proved the theorem, or gave the first rigorous proof, or something, but there is no evidence. Can people make things up out of whole cloth? Indeed they can.

Witness this Mr. Clean Commercial which says:  they say that after seeing a magician make his assistant disappear Mr Clean came up with a product that makes dirt disappear- the magic eraser. REALLY? Who are ``they''? Is this entire story fabricated? Should we call the FCC :-) ANYWAY, yes, people can and do make up things out of whole cloth and then claim they are well known. Even historians.

Commenters: I politely request that if you suggest other candidates for large gap then they be people who died before 1950 (arbitrary but firm deadline). This is not just out of politeness to the living and recently deceased, its also because these questions needs time. Kind of like people who want to rank George W Bush or Barack Obama as the worst prez of all time--- we need lots more time to evaluate these things.