Certifying primality in a CONSTANT number of operations

For this post I will only count the operations PLUS, MINUS, MULT. They may be done on rather large numbers.

Recall that from the work coming out of Hilberts 10th problem we know the following: For every c.e. set (used to be called r.e., some people still do) there is a polynomial f in 13 or less variables (we'll assume 13) with coefficients in the integers such that

x in A iff (∃ a1,...,a13))[f(x,a1,...,a13)=0]

In an article about Hilbert's 10th problem written in 1974 by Davis-Matiyasevich-Robinson they note that by this result there is a FINITE number M such that, for ALL primes p, there is a certification that p is prime that uses at most M operations: given p a prime let a1,...,a13 be such that f(p,a1,...,a13)=0. The certification that p is prime is just the evaluation of that polynomial and seeing that its 0.

Is this still the only proof that one can certify primality in a CONSTANT number of operations?

Primes is irrelevant to all of this--- any c.e. set would work. (The result for c.e. sets may qualify as a theorem that is less interesting because its more interesting.) But for primes I am wondering if there is another way to do this- perhaps using number theory, perhaps with a smaller value of M. For the explicit poly for primes, due to Jones, see here.

Ph.D. Attrition

Leonard Cassuto writes in the Chronicle an article Ph.D. Attrition: How Much Is Too Much? He presupposes the answer with the subtitle "A disturbing 50 percent of doctoral students leave graduate school without finishing".

The 50% goes over all fields but the numbers in computer science are somewhat in that range. Computer Science has different issues than humanities and theoretical CS has not quite the same issues as the rest of CS. Certainly we lose several students to start-ups and high-paying jobs. But what about the ones that just have trouble in grad school.

Cassuto writes

Perhaps they lack the temperament to work on their own (which undergraduate work does not test as severely as graduate school does), or perhaps they lack, say, the mathematical chops necessary to succeed at advanced physics. But there will be a number—and if admissions committees do a good job, it will be very small—who won't be able to finish because they're not up to the demands of the task.

Having read through many graduate applications through the year there are very few, perhaps on average one or two a year, that will clearly succeed through graduate school. Almost without exception those students go to MIT or Berkeley.

For the rest of us, you have a choice. You can either take someone who will probably work their way to a Ph.D. but with uninspired research, or those you can take a risk with a student who might have strong potential. Some of those students become great scientists, some of them flame out. You get a higher attrition rate by taking risks but that's not a bad thing.

If you do take a risk in admissions you need to encourage students to "pursue other opportunities" once you realize they won't make it. That's a process that too many of us try to avoid, so we don't take those risks as much as we should.

I gave a poster session at Erdos 100- so how did it go?

In a a prior post I suggested that STOC perhaps have people give posters instead of talks. While I doubt this will ever happen I think its worth thinking about, especially for future conferences that may be founded. I also noted that the NIPS conference they do this.

But enough theory- at the Erdos 100th I GAVE a poster. Here are my thoughts.

1. The paper I did a poster I posted on here and I posted to arxiv here. A bit awkward in that it was submitted to ERDOS 100 as USING THE ERDOS-RADO CAN RAMSEY THEOREM ON A PROBLEM ERDOS ASKED AND A PROBLEM ERDOS SHOULD HAVE ASKED, but by the time the conference came I had much better results (due mostly to co-authors of which I went from 1 to 4) and no longer used ERDOS RADO CAN RAMSEY. Do I do the Poster on what was submitted or what I have now? I picked a very nice proof to concentrate on for the poster that was new but still in the spirit of what was submitted. (The final version is being written- I'll post on this blog about it later.)
   
2. The posters were for TWO days, for TWO hours after lunch. Since it was after lunch they didn't serve food. This seemed to work. They were in two shifts-- some did Tu-Wed and some did Th-Fri (I did Th-Fri).
   
3. My actual Poster was terrible. But me talking about it and pointing to things was good. This was true in general- other peoples posters were hard to understand if the person wasn't there to clarify and explain, but was pretty good if they were. And it was nice to be able to ask questions directly and interrupt, unlike talks.
   
4. As someone LISTENING to a poster talk it was better than a real talk. In one case I listened, went home that night,
   wrote some things down, realized I missed a point, and asked him again the next day.
   
5. As someone GIVING a poster talk... it was very odd. I explained my results and a simple proof of one of them about 40 times in a 2 day period. I happen to like this (note that I've taught VDWs theorem at least W(6,2) times). But even though I like it, it was tiring. You know how it is ---- the first 35 times you explain a theorem you're excited about it, but then it got to be old hat (which would have been fine if it was a talk on a hat problem).
   
6. There were 60 posters.
   

This was overall a positive experience but, again, tiring.

So would this work for STOC/FOCS or other existing conferences? We would have to adjust our mentality to thinking that posters were not less prestigious. I don't think this will happen. But what about a new conference? If some new conference in theory gets started perhaps they should look into this model. A new conference does not have to follow the STOC/FOCS model.

A(nother) nice use of Gen Functions

In a prior post I tried to give a simple example of a proof that uses Gen Functions where there was no other way to do it. For better or worse, before I posted it, my HS student Sam found a better way and I posted both proofs.

I have another example. Noga Alon showed this to be over dinner at the Erdos 100th Bday conference. (He claims that the proof he showed me is NOT his but he doesn't know whose it is. I will still call it Noga's Proof for shorthand.)

Let

A+A = { x+y : x,y ∈ A}

A+*A = { x+y : x,y ∈ A and x ≠ y }

We take both to be multisets.

Assume A is a set of natural numbers. When does A+*A determine A?

If A is of size 2 then NO, A+*A does not determine A as we could have x+y=5 but not know if A is {1,4} or {2,3}.

What if A is of size 3? Then YES:

First determine S=((x+y)+(x+z)+(y+z))/2=x+y+z.

Then determine

x = S - (y+z)

y = S - (x+z)

z = S - (x+y)

What if A has four elements? Does there exists A,B of size 4, different, such that A+*A=B+*B?

YES:

A = {1,4,12,13}

B = {2,3,11,14}

For which n does does A+*A, where A is of size n, determine A?

Selfridge and Strauss showed that this happens iff n is NOT a power of two. I have a write up Noga's proof. The original proof, in this paper, does not use gen functions and also applies to sets of complex numbers. I think Noga's proof can be modified to apply here. Which proof is better? A matter of taste; however, Noga's proof can be sketched on a greasy paper placemat in an outdoor restaurant in Budapest while the original proof cannot.

DUMP YOUR TABLES! (the moral of my story that started with a hat problem)

Recall from my last post:

PROBLEM 1: There are n people sitting on chairs in a row. Call them p1,...,pn. They will soon have HATS put on their heads, RED or BLUE. Nobody can see their own hat color. pn can see p(n-1),...,p1. More generally, pi can see all pj j < i.

Here is the game and the goal: Mr. Bad will put hats on people any way he likes (could be RBRBRB..., could be RRRBBB, could be ALL R's - like when a teacher has a T/F test where they are all FALSE.)
Then pn says R or B, p(n-1) says R or B, etc. When people say the color everyone else can hear it.
They want to MAXIMIZE how many of them say THEIR hat color. The people can meet ahead of time to discuss and agree on a strategy.
Mr. Bad knows the strategy the people will use.

What is the best they can do? Answer: n-1:

pn says RED if the number of REDS he sees is EVEN, BLUE if the number of REDS he sees is ODD. p(n-1) sees all ahead of him, knows the parity of all of them, can deduce his own hat. So can everyone ahead of him- KEY is that they use BOTH what they heard from the people who already spoke and what they see ahead of them. So can do n-1. (NOTE- a nice but not-optimal solution that some people have told me is to use the first log n people to code how many of the remaining hats are RED- this yields n- log(n) correct.)

PROBLEM 2: Same as Problem 2 but now there are c colors of hats.

That hats are colors 0,1,...,c-1. p(n) SUMS up all of the hats ahead of him MOD c. He says that number. p(n-1) heard that answer, See's whats ahead of him and sums that, and can deduce his own color. Again n-1 get it right.

OKAY, that's the problem and the answer. NOW my story and point:

I once had a group of College Students in a summer program working on PROBLEM 1. The plan was that they would first do the people-in-a-row-2-colors version, then people-in-a-row-c-colors version, then other versions. One can learn much math from looking at many variants. They began with the 2-color case and begun working out some examples. They had these tables (Note the word TABLES for later) for the n=3 case - really large decision trees- that (I think) did yield 2 people correct. They then had a table for n=4 where (I think) 2 people correct. They worked out a few more as well, perhaps getting up to n=8. The tables got larger and larger and more complicated. I never did quite understand their tables; however, they may have been doing an ad hoc version of the strategy where
n-log(n) people get the correct hats.)

I let them go on (perhaps too long) since they kept telling me NO BILL, DON"T TELL US HOW TO DO IT, IF YOU KNOW. And I was hoping they would have a breakthrough. But by the end of the second week they still hadn't gotten it (NOTE- this is not an indication that they were bad students--- its hard to tell how hard it is to see the trick once you know it) and asked me if I knew how to do it. I told them the solution above using Parity. I THOUGHT they would say OH, that's very nice, now lets see if we can do something similar for c-colors. But no. They insisted that their solution using tables was more intuitive or more informative or more ... something. None of that is remotely true. What is true is that by that point they were emotionally invested in their tables.

I kept saying DUMP YOUR TABLES now that you have a better way of doing it. They never did. But the phrase DUMP YOUR TABLES I now
use to mean DUMP SOME OLD WAY OF DOING THINGS THAT YOU ARE EMOTIONALLY ATTACHED TO BUT REALLY DOES NOT WORK.
Once you are aware of this phenomena you can see it often.

1. You have a proof that uses a certain technique that you like (in my case perhaps Ramsey Theory) but then a better proof comes along. You have to admit that the new proof is better. DUMP YOUR TABLES.
   
2. Your proof idea is beautiful but it just doesn't work. SHOULD YOU DUMP YOUR TABLES? Hard to tell- might work later.
   
3. You get emotionally attached to a certain way to teach a course. Times change, technology changes, and perhaps you should DUMP YOUR TABLES.
   
4. I have an idea for a blog entry that I think is really good and I begin writing it, and it just isn't working. I SHOULD DUMP MY TABLES.
   
5. Sometimes in a story there is ONE really good idea and the rest is crap. This might be that the author had ONE really good idea
   but could not build a good story around it. He should have DUMPED HIS TABLES.
   
6. You have a phrase that you are fond of but it distracts from the point you are trying to make. You should
   DUMP YOUR TABLES
   (See Here For a case).
   

A problem and later a story and a point.

I have (1) a math problem to tell you about (though I suspect many readers already know it), (2) a story about it, and (3) a point to make. TODAY I'll just do the math problem. Feel free to leave comment with solutions--- so if you haven't seen it before and want to try it, then don't look at the comments. Tommorow or later I will tell you the story and make my points.


PROBLEM 1: There are n people sitting on chairs in a row. Call them p1,...,pn. They will soon have HATS put on their heads, RED or BLUE. Nobody can see their own hat color. pn can see p(n-1),...,p1. More generally, pi can see all pj j < i. They CAN meet ahead of time to discuss strategy.

Here is the game and the goal: Mr. Bad will put hats on people any way he likes (could be RBRBRB..., could be RRRBBB, could be ALL R's - like when a teacher has a T/F test where they are all FALSE.) Then pn says R or B, p(n-1) says R or B, etc. They want to MAXIMIZE how many of them say THEIR hat color. Assume that Mr. Bad knows the strategy the people will use.

What is the best they can do?

Here is a strategy: pn says R if the MAJORITY are R, and B if the MAJORITY are B, and then everyone says what pn says. They are guaranteed around n/2 correct.

Here is a strategy: Assume n is even. pn says the color of p(n-1). p(n-1) then says what pn said and gets it right. then p(n-2) says what p(n-3) has. Then p(n-3) gets it right. You are guaranteed to get around n/2 right.

GEE- can we do better than n/2? Or can one prove (perhaps using Ramsey Theory, perhaps something I learned at Erdos 100 over dinner) that you can't beat n/2 (or perhaps something like n/2 + log(log(n))).

PROBLEM 2: Same as Problem 2 but now there are c colors of hats.

NOTE- there are MANY hat problems and MANY variants of this scenario--- some where you want to maximize prob of getting them all right, some where everyone sees everyones hat but their own. These are all fine problems, but I am just talking about (1) people are in a row, (2) Want to maximize how many they get right in the worst case.

ADDED LATER- WARNING- THE ANSWER TO PROBLEM 1 IS IN THE COMMENTS NOW.
SO IF YOU WANT TO SOLVE IT YOURSELF DO NOT LOOK AT THE COMMENTS.

Combinatorics use to not get any respect. But because of Erdos...

(This blog is based on things I heard at the Erdos 100th Bday Conference)

I have spend the last week at the Erdos 100th bday conference. One point that was made many times: the acceptance of Combinatorics by the mathematics community and Erdos's effect on that.

In the 1950's combinatorics was seen as recreational but not as serious math. In the 1970's you could get a PhD in it but it was still seen as suspect. Even at the time of Erdos's death (September 1996) it was still not that well regarded. Now it is, as evidenced by Szemeredi getting the Abel Prize (Gowers and Tao getting the Fields Medal is also evidence, though not as strong since one could argue that they are not really combinatorists). What changed?

1. I would have thought Szemeredi's theorem (1975) would have turned people around on combinatorics. It didn't. Roth proved the k=3 case in the 1950's, using Fourier Analysis (``Real Math'') but Szemeredi's proof of the general case was ``purely combinatorial'' and hence of less interest. Furstenberg's proof that used Ergodic theory helped put it on the mathematical map (is the Mathematical map a bijection?) but combinatorics still was not well regarded.
   
2. Erdos got many people interested in combinatorics and the connections of it to other areas such as number theory. He had incredibly good taste in problems in that the problems he suggested often lead to deep mathematics of interest, and to more problems of interest. His emphasis on asymptotics, which now seems so natural, was revolutionary at the time and later had applications to computer science. His constant pushing for better and better results, his concept of Proof from THE BOOK his encouraging epsilons and deltas to pursue mathematics, all had a profound affect on mathematics and mathematicians.
   
3. One of the reasons for the disdain was that it was seen as recreational math. This was damming for two reasons (1) the problems were not important, and (2) the proofs were easy. Both are unfair. This may have been true at one time but they became less true over time.
   
   1. Problems not important: P vs NP is certainly important. Ramsey Theory reveals hidden
      regular structure and is important. Much of the work that has gone into better bounds
      on the VDW numbers is very important and involves deep mathematics.
      
   2. Proofs are easy: People are using Fourier analysis and ergodic theory and others tools that are rather difficult. Here we have the No true Scotsman Fallacy where people claim that if it uses these tools then its not combinatorics. This raises the question of if a field is defined by its methods or by its problems. In any case, people are solving problems in combinatorics using hard methods. But even among so-called easy proofs, they often exhibit the NP-phenomena where they are easy to verify and hence LOOK easy, but are hard to come up with.
      
4. One of the reasons for the respect is computer science. Just as Continuous math was just the right tool for physics, discrete math is just the right tool for computer science. This lead to a rich source of problems for combinatorists that in turn lead to interesting techniques.
   
5. Erdos stressed asymptotics which was just the right approach for computer science.
   

How much was Erdos responsible for the respect combinatorics has now? For those who believe in The Great Person theory of history, one person CAN make a difference and perhaps Erdos is one of those people. Would combinatorics have moved into the mainstream without Erdos? I think combinatorics would have gotten respect in year n where n might be large. With Erdos, n is smaller. Perhaps much smaller. I leave it to the reader to work out the proper asymptotics.

AltaVista versus Google

Today Yahoo is closing AltaVista, the best search engine before Google. The news caught me by surprise, AltaVista still existed? A number of commentators attribute bad management for AltaVista losing its dominance to Google. But it was an algorithm that killed the search engine.

AltaVista made its claim to fame in the mid-90's by indexing a large number of web pages. AltaVista did very well for obscure search terms like "fortnow" but didn't do so well for more common searches. I used to run a test on search engines by looking for "Holiday Inn", a popular hotel chain in the US. When you search AltaVista for Holiday Inn, the first thing listed was a Holiday Inn in Buffalo, New York. The Holiday Inn home page was nowhere to be found on the search results.

For searches like Holiday Inn, one had to use Yahoo, which back then was not a search engine but a directory tree of web sites. We needed our own directories as well. Ian Parberry maintained the TCS Virtual Rolodex, a list of home pages of theoretical computer scientists, most of which had names common enough that AltaVista wouldn't find them.

A Stanford professor (I can't remember which one) came to give a talk at the University of Chicago around 1997 and he mentioned a research project at Stanford developing a new search engine known as Google. I tested Google with my Holiday Inn test and was in shock when the Holiday Inn home page showed up as the first time. Google passed every other test I could throw at it and I've rarely used any other search engine since. Google made AltaVista, the Yahoo directory and the TCS rolodex irrelevant. Google's PageRank algorithm simply took search to a new level, like the way that Steve Jobs didn't create the first smart phone but completely changed the game with the iPhone. AltaVista managed to survive for another 15+ years but never recovered market share.

The AltaVista story leads to a lesson we still tackle today. Collecting and storing big data is a huge technical challenge but data by itself is of limited value without the algorithms to find the important parts among the muck.

Computability in Europe

Bill and I are both in Europe this week. I'm in Milan at Computability in Europe and Bill is 500 miles away in Budapest for the Paul Erdős Centenary. The US 4th of July holiday doesn't seem to sway the the Europeans from holding workshops. Bill will report on the star-studded Erdős celebration when he gets back.

So what is "Computability in Europe"? Don't the Europeans use the same Turing machines that we do? Wasn't Turing European?

Or course computation is the same, whether we do it in the US or Europe, Japan or Jupiter, but the emphasis is different. In the US we typically deal with traditional models of computers and see how much time and memory we need to solve various problems. The theme of this year's CiE is "The Nature of Computing" with "nature" being the key word. The conference is co-located with the Unconventional Computation and Natural Computation conference that focuses on different models of computing, especially those that rise from nature like biological computing. The two tutorials this week come from Grzegorz Rozenberg, talking on computing modes based on living cells and Gilles Brassard (whom I didn't recognize without his trademark beard) on quantum models.

Me, I like my computation served straight up on Turing machines, thank you very much.