Bill Gasarch Also 1,000

2016 Gathering For Gardner lecture

William Gasarch turned 1,000 earlier this month. Or in October, depending on how you count. That is, he has made 1,000 posts on a theory blog all by himself. Bill is a professor at the University of Maryland Department of Computer Science and is one of the leaders in computational complexity theory, computability theory, computational learning theory, and Ramsey theory.

Today we congratulate Bill on this milestone and convey some of his other work and activities.

Bill joined as Lance Fortnow’s official partner on the Computational Complexity blog in March 2007. His 1,000th from that point was his Jan. 2 post about Betty White and boundaries of time. If we count seven posts from two earlier guest-blogger stints when Lance was on vacation, then his 1,000th Computational Complexity post was this last October 24th about some appearances of mathematics in Gilbert and Sullivan operettas.

As noted here, the Blogger platform does not break down post counts by author, only by label, so I (Ken) resorted to grabbing all the text and counting all the “Posted by” lines. By the same count, Lance has 1,850 posts, and there are blocks by other guest posters.

Other metrics might be interesting: Shall we count equations? theorems? open problems? proofs given in full? conjectures? How about a raw count of numbers used in the posts, apart from words? Anyway, Bill has done a lot more in the public eye than the blog.

Book Reviews

Bill was the book review editor for ACM SIGACT NEWS from 1997 to 2015 before turning the job over to Fred Green, a professor of computer science at Clark University. See Bill’s reviews here. The reviews are wonderful and there are lots of them. He should be thanked many times for the terrific work he did there.

I (Dick) am happy to say that Bill reviewed three of my books:

1. People, Problems, and Proofs, by Richard Lipton and Ken Regan.

2. The P=NP Question and Gödel’s Lost Letter, by Richard Lipton.

3. Ideas that Created the Future: Classic Papers of Computer Science, the book edited by Harry Lewis.

The last one includes one of my strangest papers: “Social Processes and Proofs of Theorems and Programs,” with Rich DeMillo and Alan Perlis in 1977. Rich and I cherish it because it included Perlis as a co-author. He was special to many of us—especially those from CMU. We always will miss him.

New Book and Numbers

Let’s look at Bill’s personal page. He highlights his wonderful newest book Mathematical Muffin Morsels: Nobody Wants a Small Piece. It is joint with Erik Metz, Jacob Prinz, and Daniel Smolyak, who were undergraduate students in Bill’s group, and features contributions by numerous others.

A summary:

Suppose you have five muffins that you want to divide and give to Alice, Bob, and Carol. You want each of them to get . You could cut each muffin into and give each student five -sized pieces. But Alice objects! She has large hands! She wants everyone to have pieces larger than .

Is there a way to divide five muffins for three students so that everyone gets , and all pieces are larger than ? Spoiler alert: Yes! In fact, there is a division where the smallest piece is . Is there a better division? Spoiler alert: No.

This problem takes us through much mathematics of interest, for example, combinatorics and optimization theory. However, the math is elementary enough for an advanced high school student.

What supplements the math is the use of accessibly simple computer programs to do numerical experiments. Some can be found on Bill’s Muffin Website. Among news after our June 2018 post on the muffin problem, Richard Chatwin proved that the value the largest size of the smallest piece—when muffins are divided equally among people—depends only on the ratio . The value left wide open in the post has been proved to equal and other bounds have been closed.

All these sources have tables of what we might—to channel the title of Bill’s other recent book with Clyde Kruskal—call Numbers With a Point. The point is the insight they give about asymptotic growth and likelihood of conjectures. We note in particular a 2020 paper by Smolyak on “The Muffin Problem – Data Analysis of Exceptions” to patterns in the values .

More Numbers

Bill gave a talk in our January 17 workshop on “Seeking an Easier Proof of a Weaker Result in Multiparty Communication Complexity.” The topic is a classic setting in which people each have an -bit number on their foreheads, so that all can see everyone else’s number but not their own. The problem is to compute some function or predicate of the numbers, such as their whether their sum exceeds or equals a given value , while minimizing the total number of bits communicated.

Ashok Chandra, Merrick Furst, and I (Dick) raised these problems in a 1983 paper, which Bill preserves on his site for papers related to Ramsey theory. The trivial way of having one person reveal another’s hidden number giving bound (plus one or more bits needed for that person to speak the result of to all parties). The basic surprising fact is that, as a function of and for the above and other natural predicates , one can do asymptotically much better than .

Bill talked about his own paper with Richard Beigel and James Glenn on the exact- case. It appeared at the MFCS 2006 conference. This paper is really neat because it shows the problem has depth and difficulty and ramifications beyond what I imagined back then. It gives connections to groups and regular expressions, besides refining our original application to branching programs. See also the update that went with Bill’s talk.

Even the case of people is highly nontrivial. The paper gives a chart tracking the constant in the for the result giving with of order . The constant on the closest-known bounding formula seems to stay in the vicinity of (the chart gives its reciprocal), going from to in the last lines. Is that a coincidence? It relates to the density of sets of integers with no arithmetic progression of length 3, for which see this StackExchange item from last year, and this older survey by Bill with Glenn and Kruskal.

Open Problems

Bill is one of the top writers on theory. We owe him some props. Thank you, Bill.