Some different ideas for marking the Fourth

 “Founding Frenemies” source

John Adams and Thomas Jefferson did not use Zoom. Their correspondence, from 1777 up to their deaths hours apart on July 4, 1826, fills a 600-page book.

Today, Independence Day in the US, we consider the kind of intellectual fireworks represented by the correspondence.

Jefferson and Adams were intellectual opposites as well as political rivals. Adams favored a strong central government to bridle human passions, whereas Jefferson’s support for the French Revolution continued beyond its devolution into the Reign of Terror. They debated many other points of politics, philosophy, and culture.

Abigail Adams, the wife of John, joined in some of the exchanges. Because she often stayed in Massachusetts while he was in Philadelphia or New York or elsewhere, the husband and wife exchanged many letters—over 1,100 in all. His letter to her on July 3, 1776, instituted the use of fireworks to celebrate anniversaries of the Declaration of Independence.

Today there is not much in the way of fireworks displays. Most have been canceled because we cannot allow crowds to view them. In the Buffalo area, some townships are having small displays with limited access, and some displays are being set on high points for possible area viewing. So we felt we should write about fireworks of a different kind, a kind that is not restricted by the pandemic and might thrive through it. But first we’ll make a point about the history of fireworks.

## Fireworks: Ancient, Early, and Modern

Fireworks go back at least 1,100 years to China, where chemists discovered the fun of stuffing volatile compounds into tubes of bamboo or paper and setting them off. Some have pyrotechnics going back another 1,000 years, to about 200 BCE, insofar as bamboo was known to pop with a loud sound when dried and heated. Gunpowder traveled best of the compounds and made its way into Europe at least by the 1200s. The first recorded wide-scale fireworks display in England was in 1486 for the wedding of King Henry VII to Elizabeth of York, which ended the Wars of the Roses. Shakespeare mentions fireworks in Love’s Labours Lost. The Mughals in India from the 1500s to the 1800s made fireworks a diversion for noble women on the Diwali holiday:

 Cleveland Museum of Art source

Our point is that 1776 isn’t even halfway back to the beginning of using fireworks for celebrations, even just in the West. Can we even call it “Early”? Lavish displays to mark major events were common by the mid-1700s. A royal display in 1749 was accompanied by orchestral music commissioned from George Frideric Handel and went ahead despite rain. Over 12,000 people also paid to attend the main rehearsal six days earlier, many braving an hours-long traffic jam on approaches to the London Bridge. That feels quite modern to us. Adams’s letter mentioned other social features we know today:

It ought to be solemnized with Pomp and Parade, with Shews, Games, Sports, Guns, Bells, Bonfires and Illuminations from one End of this Continent to the other from this Time forward forever more.

The pandemic has curtailed others of these. The major North American team sports have not resumed either. Some parades have been run in “reverse” mode: the floats and performers stay put while spectators drive by slowly in cars.

Adams’s letter has another, earlier, passage that chills today. The letter begins by saying that the Declaration was supposed to have been made in December, 1775, and enumerates plans the colonies had made contingent on this. He then says that what caused the plans to be aborted was an outbreak of disease:

All these Causes however in Conjunction would not have disappointed Us, if it had not been for a Misfortune, which could not be foreseen, and perhaps could not have been prevented, I mean the Prevalence of the small Pox among our Troops. . . . This fatal Pestilence compleated our Destruction.—It is a Frown of Providence upon Us, which We ought to lay to heart.

The ellipsis is in the letter—as Ken’s children have pointed out, trailing off thought with dots in letters or e-mails or Facebook posts or texts is a distinctive habit of us older folk. Thus a specific outbreak of a contagious disease changed our history then as now.

## Ideas: Ancient, Early, and Modern

We have remarked on how the pandemic has affected opportunities to exchange ideas and how to compensate. One impacted series that both of us intended to visit this spring has been the series of workshops at the Simons Institute in Berkeley.

Still, the Simons Foundation has continued its other ways to stimulate ideas. Here we offer our congratulations to Venkatesan Guruswami, Omer Reingold, and David Woodruff, who have just been appointed as Simons investigators for 2020.

In briefly talking about their work, we want to make a point about how the pandemic enables taking the long view of ideas—in a way that appointments such as these promote. It is easy to get wrapped up in immediate aspects of a current hot problem and not be aware that it has a history. The history may not involve exactly the same ideas as the problem, but related ideas whose importance was appreciated much earlier. “Early” may not mean the Middle Ages or the 1700s as with fireworks, but it can mean times before any of us were born.

Venkatesan and Omer and David each have done some stellar research, broadly in various parts of theory. They each have many results, but we thought we would highlight just one result each. We picked a result that we think is representative, is deep, is beautiful, and is one that we personally admire the most.

### “Ancient” Times

Venkatesan did important work on a problem that was created before complexity theory existed. Our favorite is his ground-breaking work on list decoding.

What is the best way to encode data to protect it against various kinds of errors? This is still open. But Venkatesan changed the landscape.

The questions about error correcting codes go back to the 1940’s. Usually the first results are credited to Richard Hamming in 1947. Soon the notion of list decoding was introduced. The cool idea is that decoding does not require one answer, but allow a list of possible answers. The hope is that with other information about the message we might be able to select the answer.

Venkatesan and Ken’s colleague Atri Rudra found explicit codes that achieve list-decoding capacity, that is, they have optimal redundancy.

What we like so much is the model is so natural and so powerful. There are many applications of list decoding to complexity theory. See Madhu Sudan’s survey for some additional comments.

### Early Times

Omer did his most important work on problems that were first studied in the early days of complexity theory. Our favorite is his beautiful work on small-memory deterministic graph walks.

Is ${\mathsf{L < NL}}$? This is still open. But Omer made a huge contribution to our understanding of fundamental complexity classes. Romas Aleliunas, Dick Karp, Laszlo Lovasz, and Charlie Rackoff proved earlier that random small space could navigate undirected graphs provided they could flip coins. In a sense Omer removed the coins to get his result that undirected graph connectivity is in ${\mathsf{L}}$. The previous result was easy—I can say that because I (Dick) was a co-author on it—but Omer’s theorem is deep.

Omer’s proof drew heavily on expander graphs and the zig-zag product from his earlier work with Salil Vadhan and Avi Wigderson for creating them.

### Modern Times

David did his most important work on problems that were only created relatively recently. Our favorite is his work on approximately counting distinct elements. This work is joint with Daniel Kane and Jelani Nelson and appeared at PODS 2010. It was the first streaming algorithm with an optimal combination of space usage and update time. Here is the relevant table from their paper (KNW):

Streaming algorithms are relatively new and parts of data science are newer. But working with data is old, as old as codes. This finally leads us to pose an outlandish question:

Can all of this work be usefully interpreted from the standpoint of coding theory?

This is outlandish, because the word “code” does not even appear in either Reingold’s paper or KNW. But part of holding coding theory to be a paradigm, as both Ken and I experienced in graduate school, is that its perspective should expand. Is this capable of creating intellectual fireworks? We’ll see.

## Open Problems

Have a safe and happy fourth of July.

[some small fixes]

1. July 6, 2020 11:10 am

great post!

2. July 11, 2020 11:50 pm

This sentence makes no sense:

>The cool idea is that doing not require an answer, but allow a list of possible answers.

though the idea you are trying to convey comes across.

• July 12, 2020 2:49 pm

Thanks! Looks like “doing” was meant to be “decoding does”—changed accordingly.