## Thursday, January 18, 2018

### A Sensitive Game

Last month I posted about the sensitivity conjecture and today I would like to talk about an interesting game developed by Gilmer, Koucký and Saks and independently by Drucker that could yield a proof.

Consider the following game on n bits among three players, Alice, Bob and Carol. The game works as follows: Carol picks a bit position and Alice sets that bit to 0 or 1. Carol then picks another unused bit position and Alice sets that bit as well. This repeats until the last bit which Carol gets to set herself. The bits are then revealed to Bob who has to give a set of bit positions that includes the bit Carol set at the end. Alice and Bob can work out a strategy ahead of time with the goal of minimizing the size of the set.

If Carol can force Bob to give a set of nε bits for some ε>0, this would prove the sensitivity conjecture! Basically a family of functions that give a counterexample to the sensitivity conjecture would give a strategy for Alice and Bob that yields a set of size no(1). You can find the full proof in the papers above.

How well can Alice and Bob do? They can use the following strategy to achieve n1/2: Break up the input positions into n1/2 groups of n1/2 bits each. Whenever Carol picks a bit position, Alice sets that bit to zero unless it is the last bit in that group in which case she sets it to one. Carol can set the last bit in some group anyway she wants. Bob will either see every group having one 1 and will give the set of the positions of all the 1's, or Bob will see a group of all zeros and give the positions in that
group.

Mario Szegedy uses error-correcting codes to improve the upper bound to O(n0.4732). A Georgia Tech undergraduate DeVon Ingram improves the upper bound to O(n0.4696) by generalizing Szegedy's techniques. Ingram's proof comes down to finding a one-to-one function mapping subsets of {1,...,15} of size 4 to perfect codes of length 15 with the property that the bits of the code are 1 for the indices of the subset. Perhaps one could find a clever mapping that has this property but Ingram wrote code using a matching algorithm. A true computer assisted proof. Longer code lengths alas won't yield direct improvements.

The connection to sensitivity doesn't go both ways. An upper bound of no(1) wouldn't necessarily yield a counterexample to the sensitivity conjecture though would tell us the limitation of this game approach. Nevertheless I find it cool that a game that doesn't talk about functions at all could help settle an important question about them.

## Tuesday, January 16, 2018

### Donald Knuth Turns 80 years and 6 days

Celebrating Donald Knuth's 80th birthday, or 80 years + 7 days birthday seems odd. Should we use powers of 2? Hmm- too few, just 32 and 64 really. And having a 32-year celebration for someone is unusual. How about numbers that end in 0 in base 8. 64 would be 100, 72 would  110, 80 would be 120 so AH- we would be celebrating! So lets Celebrate!

LANCE: One of us should blog about Don Knuth turning 80.

BILL: How about both of us, sep posts?

Lance had his post here. Now its my turn.

Donald Knuth was the first person (roughly- history is not as definite as mathematics) to use mathematics to analyse algorithms. This may seem like an obvious thing to do but that's easy to say in retrospect. And he never lost focus: He may have to use some hard math to analyze algorithms but his goal always was to analyze algorithms. He didn't get fascinated with some obscure aspect of math like, say, surreal numbers, and go write a book on it. Oh wait, he did (see here). But, for the most part everything he did was towards faster algorithm and faster typesetting.

In an early draft of a book review of  Companion \to the Papers of Donald Knuth I wrote at the end of it

Donald Knuth has been called the father of Theoretical Computer Science and hence his thoughts are worth knowing

I usually email my reviews to the author so they can make sure I didn't say anything stupid or in some very rare cases have a rebuttal. In Knuth's case I postal mailed it (ask your grandparents what that is) since he does not use email. He mailed back the hardcopy with some corrections in pencil. One of them was to cross out

father of theoretical computer science

and replace it with

father of algorithmic analysis.

I made the correction. That is how he views himself and it would be odd to argue the point.

As a tribute to him I have gathered up all of the book reviews  in my column of books by him (between 10 and 12 depending on how you count) and books clearly inspired by him (1 book- A=B) into one file which I point to  here

## Wednesday, January 10, 2018

### Donald Knuth Turns Eighty

We've kept this blog going long enough that we start repeating our celebrations. Ten years ago Bill celebrated Don Knuth's 70th Birthday and today Donald Knuth turns 80. While he celebrates in Piteå, Sweden with its less than 4.5 hours of daylight, we wish him a happy birthday from stateside.

Looking back in this blog, in 2015 I wrote about the history of the history of computing including this wonderful talk by Knuth, Let's Not Dumb Down the History of Computer Science.

Donald Knuth is known for many things, important algorithms, the brilliant book series The Art of Computer Programming, TeX, the many awards he's won and the award named after him. In my favorite story, back in the 70's when Knuth started working on Volume 4 (still in progress), he wanted a good name for those hard problems that Cook and Karp found. His candidates "Herculean", "Formidable" and "Arduous" didn't get much traction so he ran a contest which had some interesting suggestions before reluctantly going with the name "NP-complete" that came out of a group from MIT.

In his SIGACT News article that described the contest, Donald Knuth was so sure that these hard problems would remain hard, he puts everything on the line, offering anyone who could prove P = NP a live turkey. May Don Knuth and his turkey continue to celebrate many more birthdays.

## Sunday, January 07, 2018

### A new largest prime found!

A new largest KNOWN prime has been discovered and its 23 million digits long.

Nate Silver's website had an article about it (written by Oliver Roeder) here

An article about why people do this is  here

Lance posted about finding large primes in 2006 here

I'll just make some random comments

1) The prime is 277,232,917-1

2) The prime is not much bigger than the previous champion.

3) More generally, the graph (in Oliver Roeder's article) shows from 1600 to about 1951there was slow progress but since then there has been LOTS of progress. See the table in this article. I had wanted to say every year a new prime was found  but, alas, not that simple a pattern. Even so, lots of new records.

4) I"ll list the reasons given for why people do this and my comments on them.

a) Tradition! (Note to self- write a novelty song to the tune of Fiddler-on-the-roof's Tradition about why people work on various mathematical things)

b) For the by-product of the quest. This one does make sense and I am sure has driven and helped test out some research. Reminds me of the spinoffs from going to the moon (see here). Contrary to what I heard as a kid, the orange-powder-drink Tang was not a spinoff. But there were many others. Of course- would these spinoffs have happened anyway? Hard to know.

c) People collect rare and Beautiful items. I don't really see this one. Finding a large prime doesn't make  its yours, it belongs to the ages! And I don't think people get their names on the prime either. The only prime that has someone's name on it is the famous Grothendieck prime which is 57. Oh well. There are sets of primes with peoples names on them: Mersenne primes, Gaussian  primes (which are subsets of Gaussian integers so maybe shouldn't count), Eisenstein primes, and

d) For the glory! Maybe, but given how briefly people hold the record, fame is fleeting.

e) To test the hardware. This one I didn't know! I'll quote the article as to why primes are good for this
Why are prime programs used this way?  They are intensely CPU and bus bound.  They are relatively short, give an easily checked answer (when run on a known prime they should output true after their billions of calculations).  They can easily be run in the background while other "more important" tasks run, and they are usually easy to stop and restart.
f) To learn more about their distribution. The prime number theorem was conjectured from data. We have so many primes now that I wonder if a few more really help formulate conjectures

## Thursday, December 21, 2017

### Having Faith in Complexity

I believe P ≠ NP as much as anyone else. Nevertheless should we worry about trust we put in complexity?

You don't need the full power of P = NP to break cryptography. I don't worry about quantum computers breaking RSA and related protocols. It won't sneak up on us--when (or if) quantum computing gets anywhere close to factoring large numbers, we'll figure out a strategy to change our protocols and to protect the information we already have. However if someone comes up with an algorithm tomorrow that cracks AES, we'll have a crisis on our hands as AES is so well used the algorithm is embedded into computer chips. Perhaps we can mitigate the damage before the algorithm spreads or at take our information off-line until we develop new solutions.

But what about blockchains, the technology that underlies cryptocurrencies such as Bitcoin. A blockchain consists of a series of transactions collected into sequence of blocks, where each block consists of a hash of the previous block with transactions themselves hashed and often encrypted with public-key cryptography. One would hope that breaking the cryptography would be caught quickly and we'd still have a legit record of transactions saved somewhere. The transactions themselves might be compromised especially if anonymity was built into the system.

Bitcoin itself, as I write this, has a total market cap of over \$250 billion based fully on cryptography. The cryptography will probably hold up, Bitcoin investors have more to worry from bad implementations or the pop of a bubble of unrealistic expectations. But as we watch so many exciting advances in computing tackling challenges that we would never have expected to get solved, should we continue to build our economy on the hope that other advances won't happen?

## Sunday, December 17, 2017

### Monkey First!

The following story is not true nor has anyone claimed its true, but it has a point:

A company gets a contract to do the following: train a monkey to sit on a 10-foot pedestal and recite some passages of Shakespeare. After a week they announce they have made progress! They invite their investors to see what progress they have made! They unveil a curtain and there is... a 10-foot pedestal.

This story was in an article about how Google does moonshots-- that is, high-risk, high-reward, innovative work. The article is here. (How the Atlantic makes money when they have stuff online is a mystery to me. Perhaps they do in a very innovative way.)  The point is that its BAD to have tangible results (like the pedestal) that are not getting at the heart of the problem. So Google has various incentives to do the important stuff. Their slogan is MONKEY FIRST.

This also applies to our research.  The following sequence of events is common:

1) Prove some scattered results.

2) Pedastal or Monkey? You could write up what you have, polish it, write up some nice LaTeX macros to make the writing of the paper easier OR you could try to find the unifying principle that would be hard, and might not work, but if it works that would be, as the kids say, Jawesome (Jaw-dropping awesome). The sad answer is that which you do might depend on when the next conference deadline is.

More generally there is a tension between safe do-able research(Pedestal) and high-risk, high-reweard research (Monkey).  Is our incentive structure set up to encourage high-risk high-reward? The Tenure system is supposed to do it and it DOES in some cases, but not as much as it could since there are other factors (salary, promotion to full prof, grants).

Does the system encourage high-risk high-reward? Should it? Could we do better? What are your experiences? I have no answers (especially to the question of what are your experiences) so I welcome your comments.