The Institute for proving Graph Isomorphism is in P

(This post was inspired by Adam Winklers awesome book
Gunfight: The Battle over the Right to Bear Arms in America.
Disclaimers one: Adam Winkler is my cousin and I got a free copy.
Question: Should I give him a free copy of my VDW book when it comes out?
Disclaimer two: Scott did a post on a related matter here.)

If someone started an Institute to prove Graph Isomorphism is in P that would
be very odd since it could be that GI is not in P.
If someone started an Institute to study Graph Isomorphism that would be
much less odd (though still somewhat odd).

Does it make sense to have an openly biased think tank?

1. If a pro-gun-control person writes a book that proves that there weren't that many
   guns in America in the early 1800's would you believe it?
   
2. If an anti-gun-control person writes a book claming that the more guns there are
   the less crime there is, would you believe it?
   
3. The CATO Institute: A Libertarian Think Tank.
   If they did an honest study of gun control and concluded that it does reduce
   crime then would they publish it? I honestly do not know.
   If they did an honest study of gun control and concluded that it increases
   crime then would anyone believe it? Being openly biased might undermine their credibility.
   
4. The Tobacco Institute (they no longer exist). They produced reports
   claiming that smoking was not unhealthy (or perhaps that the evidence is incomplete).
   They were employed by the Tobacco industry. Did they ever have any credibility?
   Did they do any unbiased science, perhaps on non-smoking issues?
   I honestly don't know.
   

It is tempting to say Scientists should not have an opinion before they do a study. But this is clearly not correct in theory or practice. Scientists do indeed have an opinion, even an interest, in what a study will tell. Why is that different from the Tobacco institute?

1. An honest scientist's preconceived notions are hopefully also based on science and not on who is paying him and not on other non-science factors.
   
2. An honest scientist, when faced with evidence that they are wrong, will hopefully pursue that evidence and perhaps change their mind. This might be easier in math than in science since Proof is our accepted criteria. For example, I doubt there are diehards who still think that NL ≠ coNL.
   

The New Patrons

A few centuries ago if you wanted to do science and not independently wealthy you needed help.

Most of the important astronomers and natural philosophers (as well as artists) in the 16th and 17th centuries depended on the patronage of powerful religious or political figures to fund their work. Patronage networks extended all the way from Emperors and Popes to regional nobles to artisans to peasants; even university positions were based to some extent on patronage. Scholarly careers in this period were driven by patronage, often starting in undistinguished universities or local schools or courts, and traveling closer or farther from centers of power as their fortunes rose and fell.

Today most scientists have salaried positions at universities and get funded by the government but with sequestration and budget cuts, scientists have to seek out other sources, such as industrial funds. We've long had various scholarships endowed by private donors: Sloan, Packard, MacArthur. Recently though we've seen some new patrons, the upper 1%, who want to help out where other funds are limited. Some of these work through endowed positions at universities, but we also see some who create foundations dedicated to funding directed at research.

In the past few months I came face-to-face, or at least in the same room, as two of them: Landon Clay in Oxford for the opening of the new Maths Institute partially funded by his foundation and Jim Simons, when I visited Stony Brook and had lunch in the Simons Center for Geometry and Physics. The Clay Mathematics Institute funds several mathematicians and offers the million dollar bounty on P v NP and other open questions. The Simons Foundation supports a few theoretical computer scientists, not to mention the Simons Institute in Berkeley.

Of course the more money coming into our field, the more research we can do. But patronage does have its other side.

Patronage, and the desire for more, also shaped the work and publications of scientists. Effusive dedications to current or potential patrons can be found in almost every scholarly publication, while the interests of a patron in a specific topic was a strong incentive to pursue said topic—or reframe one's work in terms of it. Galileo, for example, first presented the telescope as a naval instrument to military- and commerce-focused Republic of Venice; when he sought the more prestigious patronage of the Medici court in Florence, he instead promoted the astronomical potential of the device (by naming the moons of Jupiter after the Medicis).

 How much do the lessons of the 16-17th centuries still apply today?

Local Reductions

With the STOC deadline passing on Monday, now is a good time to look at the arXiv to see what has been posted since then. Hamid Jahanjou, Eric Miles and Emanuele Viola have a new paper, Local Reductions, that gives a new reduction from NTIME(t) to 3-SAT formulas of size t polylog(t). The twist to their new reduction: there is an NC⁰ circuit C that maps the number i to the ith clause. NC⁰ means every output bit depends on only a constant number of input bits. The proof uses old-fashioned parallel routing.

Should have some interesting applications. It does save a step in Williams' proof that ACC⁰ ≠ NEXP but the combined proofs are longer.

In other news, I've been getting several email from other CS chairs looking for students to hire as faculty in their departments. The latest CRA News is 59 pages, 50 of them are faculty job ads. It's a good year to be on the job market.

Four answers to the Recip problem

In my last post I asked you to solve the following question which
was from the Maryland Math Competition:

The inequalities 1/2 + 1/3 + 1/6 = 1 and 1/2 + 1/3 + 1/7 + 1/42 = 1
express 1 as a sum of three (resp. four) reciprocals.

Find five positive integers a,b,c,d,e such that
1/a + 1/b + 1/c + 1/d + 1/e = 1.

Prove that for any positive integer k GE 3 there exists positive intgers numbers d1,d2,...,dk
such that 1/d1 + ... + 1/dk.

The HS students had the following solutions.
I list the answers to part b first.  I sketch the proofs. They are all by induction.

1) Use 1/n = 1/(n+1) + 1/n(n+1).  This was the most common solution.  This leads to (2,3,7,43,1806) for part a.

2) Since the question itself gives the solution for m=2 and 3 we only need P(k) --> P(k+2)
Use 1/n =  1/2n + 1/3n + 1/6n.  This leads to (2,3,12,18,36).
One of the students later told me that knew the solution (i) but did it this way to
avoid having to multiply 42 by 43 which is needed to get part a using that solution.

3) Inductively that the largest denom n is even Use 1/n = 3/3n = 1/3n + 2/3n = 1/3n + 1/(3n/2)
Less than five students did 2b this way.  This leads to (2,3,7,63,126) for 2a.

4) If (d1,...,dn) is a solution then so is (2,2xd1,...,2xdn).
Only two student did it this way.  It leads to (2,4,6,14,84), which they both used.

NOBODY did in the non-inductive way mentioned in the last post.

There were THIRTY TWO solutions to 2b.  Several people had their part 2a and 2b not
related to each other at all.  This was far more solutions than I anticipated.
While grading I got good at adding reciprocals.
I list them in lex order along with how many people did that answer.
(This is likely approx- I may have miscounted a bit, but its basically right)

(2,3,7,43,1806) - 91 (linked to solution 1 above)

(2,3,7,48,336)  - 3

(2,3,7,56,168)  - 1

(2,3,7,63,126)  - 6 (linked to solution 3 above)

(2,3,7,70,105)  - 1

(2,3,8,25,600)  - 1

(2,3,8,30,120)  - 1

(2,3,8,32,96)   - 6

(2,3,8,36,72)   - 5

(2,3,8,42,56)   - 11

(2,3,9,21,126)  - 2

(2,3,9,24,72)   - 4

(2,3,9,27,54)   - 3

(2,3,10,20,60)  - 5

(2,3,11,22,33)  - 1

(2,3,12,15,60)  - 1

(2,3,12,16,48)  - 1

(2,3,12,14,84)  - 2 (linked to solution 4 above)

(2,3,12,18,36)  - 12 (linked to solution 2 above)

(2,4,5,25,100)  - 3

(2,4,5,30,60)   - 1

(2,4,6,14,84)   - 3

(2,4,6,16,48)   - 1

(2,4,6,18,36)   - 2

(2,4,6,20,30)   - 1

(2,4,7,12,42)   - 4

(2,4,7,14,28)   - 2

(2,4,8,12,24)   - 6

(2,4,8,10,40)   - 2

(2,5,6,10,30)   - 1

(2,5,6,12,20)   - 2

(3,4,5,6,20)    - 3

A problem on Reciprocals

(I thought I had posted this a while back but I can't find it in past blogs
so I think I did not. I DID post a diff problem on reciprocals.)

Here is the question I graded a while back on a  Maryland Math Olympiad.
I request that you do it and post your answer as a comment- I'll be curious
how your answers compare to the students who took it.
I will post the solutions the students used in my next post and comments
on how they were similar or different than yours.
The students had two hours to do five problems.
This was problem 2.

The equalities 1/2 + 1/3 + 1/6 = 1 and 1/2 + 1/3 + 1/7 + 1/42 = 1
express 1 as a sum of three (resp. four) reciprocals.

PART A: Find five distinct positive integers a,b,c,d,e  such that

       1/a + 1/b + 1/c + 1/d + 1/e = 1.


PART B: Prove that for any positive integer k  GE 3 there exists k distinct positive intgers numbers d1,...,dk such that

1/d1 + 1/d2 + ... + 1/dk = 1.

A Theorist Goes to SOSP

Monday I attended the 24th Symposium on Operating Systems Principles, the lead conference for computer systems research. Why would a nice theorist go to SOSP? Trying to recruit a few good systems faculty for Georgia Tech.

I really enjoyed the day in ways I didn't expect. I found several of the talks interesting, even from a theory perspective. Austin Clements, in the first and one of the best paper talks, said he had a theorem and proof (roughly if operations scale there is an implementation that scales well on multicores), though purposely left the formalization and proof out of the talk and focused on implementations. Kay Ousterhout built on some theoretical tools for job scheduling. In a talk after I left, a group from Texas takes a step towards practical proof-based verifiable computing. I never expected to be cited in a SOSP paper.

When I go to a theory conference I see so many people I know that I don't spend enough time meeting new people. At SOSP, I knew a handful of people and just had a great time talking to people I haven't met before, particularly students.

Only thirty papers get presented in single track in this conference held every two years. STOC/FOCS accepts over 300 papers in the same time period. Having an SOSP paper is a really big deal. Despite having only thirty talks and traditionally held in hard-to-reach places (this year an hour and a half drive from Pittsburgh), there were 628 attendees split 42% students, 42% non-student academics, 15% industry and one member of the press.

The 2013 SOSP is the first ACM conference will fully open proceedings and the authors retained full rights to their paper, the gold standard espoused by many in our community. It didn't come cheap, the conference put up $1100/paper to the ACM to pay for the privilege.

My Pope Number is 2: The Smaller World Hypothesis

I proofread Piergiogrio Odilfreddi's book (which is on Lance's List of Favorite Complexity Books) for which I got a generous acknowledgment. I have also
visited him in Italy, though not for a while. 

Benedict.Pope Emeritus (I think that's what he is still called) broke his silence with a letter to Odilfreddi, see here.

Hence I am two handshakes away from Pope Benedict.  It used to be said that there were Six degrees of separation-- for all people a,b there is a path of length at most 6 that links them. The graph varies with you you ask, but it tries to pin down that a and b know each other.

Is six now too big? One measure is how many Google hits
`X degrees of separation' gets

• Six degrees gets 1,760,000 hits
• Five degrees gets 97,300 hits
• Four degrees gets 159,000 hits
• Three degrees gets 605,000 hits
• Two degrees gets 843,000 hits

The last one may not be quite fair- there was an episode of Pokemon
with the title `Two degrees of Separation' and also a company with that name.


How well two people know each other has to be defined carefully.

1. Erdos Numbers- Put an edge between a and b if they have a paper together.
2. Bacon Numbers- Put an edge between a and b if they appear in the same movie.
3. Handshake Numbers (I am not sure its every been called that)- Put an edge between a and b if they have shaken hands.
4. knows-number (likely not defined). Put a DIRECTED edge from a to b if a will return b's phone calls and/or email.
5. Twitter Numbers (Not sure if its ever been defined). But a directed edge between a and b if a follows b on twitter.

Odilfreddi may be an articulation point in the handshake graph or the knows-graph since he is in math AND known to the public (at least in Italy) as an outspoken atheist, so he connects two worlds. Another articulation point might be David Seetapun who has a PhD in computability theory (he worked on Recursive Ramsey Theory which is how I know of him), Finance (Goldman Sacks), Gambling in Las Vegas, and swordfish fishing (he won the Golden Fly Tarpon Tournament). He may be the key to connecting mathematicians to fisherman.

The following is probably known but I couldn't find it- what is the longest distance between two websites (number-of-links to go from one to the other)?
The average? Are these numbers getting larger or smaller?

ADDED LATER: Christian Sommer emailed me the following two
RELEVENT links:

Diameter of the web and

Tools to study the web graph

The first link claims the avg diameter of the web is 19.

Andrzej Mostowski (1913-1975)

Andrzej Mostowski was born 100 years ago today. While Mostowski worked in many areas of logic, including early fundamental work on model theory, for our readers he's best known for co-discovering the arithmetic hierarchy, sometimes called the Kleene-Mostowski hierarchy.

The arithmetic hierarchy has a few different equivalent definitions but let's use one based on computability. We define inductively there hierarchies, Σ_i⁰, Π_i⁰ and Δ_i⁰. Σ₀⁰=Π₀⁰=Δ₀⁰ are the computable sets and

1. Δ_i+1⁰ are the sets computable with a Σ_i⁰ oracle.
2. Σ_i+1⁰ are the sets computably enumerable with a Σ_i⁰ oracle.
3. Π_i⁰ = co-Σ_i⁰.

In particular, Δ₁⁰ are the computable sets and Σ₁⁰ are the computably enumerable sets. The halting problem is Σ₁⁰-complete under computable reductions, the set of Turing machines that accepting infinite sets are Π₂⁰-complete.

We completely know the structure of the arithmetic hierarchy, for i > 0, Σ_i⁰ ≠ Π_i⁰ and for i ≥ 0, Δ_i⁰ = Σ_i+1⁰ ∩ Π_i+1⁰.

The arithmetic hierarchy inspired the polynomial-time hierarchy in complexity theory. Unlike the arithmetic hierarchy, separations in the polynomial-time hierarchy remain open and any separation implies P ≠ NP. While we have relativized worlds which do quite a few different separations and collapses in the polynomial-time hierarchy the following remains open: Does there exist a relativized world where the polynomial-time hierarchy looks like the arithmetic hierarchy, i.e., for i > 0, Σ_i^p ≠ Π_i^p and for i ≥ 0, Δ_i^p = Σ_i+1^p ∩ Π_i+1^p?