A conversation on what theory has done for us

[Inspired by Lance Fortnow’s retrospective post on the “Karp report,” Avi Wigderson’s response, and the Monty Python]

And what has the theory of computing done for us in the last twenty years?

Differential privacy? Apple just announced it will be used in iOS 10

Yes, and the application to preventing false discovery and overfitting is now used in production.

Ok, fine, but apart from differential privacy, what has theory done for us in the last twenty years?

Quantum algorithms? There wouldn’t be such a push to realize quantum computers if it wasn’t for Shor’s algorithm.

And quantum error correcting! There would be no hope of realizing quantum computers without quantum error correction

Very well, but apart from differential privacy and quantum computing, what has theory done for us in the …

Streaming algorithms? It all started with a theory paper and now it is a major interdisciplinary effort.

Yes, fair enough, but apart from differential privacy, quantum computing, and streaming algorithms, what has theory done for us…

Linear time decodable LDPC error-correcting codes? The first generation was not practical, but now they are part of major standards

Sure, ok, but apart from differential privacy, quantum computing, streaming algorithms, and error-correcting codes, what has theory…

Homomorphic encryption? The first-generation solutions were inefficient, but it might be only a matter of time before we have usable homomorphic encryption standards.

Linear-time SDD solvers? Algorithms like this and this are implementable and we may be one more idea away from algorithms that can be put in production.

Sublinear time algorithms like sparse FFT?

All right! But apart from differential privacy, quantum computing, streaming algorithms, error-correcting codes, homomorphic encryption, linear-time equation solvers and sub-linear time algorithms, what has the theory of computing ever done for us in the past twenty years?

. . .

[Could be continued. Indeed, please continue in the comments]

Advertisements

I choose to remember Scalia by what he loved best

His own words:

• On where black kids should go to college
  

  “There are those who contend that it does not benefit African-Americans to get them into the University of Texas, where they do not do well, as opposed to having them go to a less-advanced school, a less — a slower-track school, where they do well”

  Scalia during oral arguments concerning Fisher vs. University of Texas

• Gay sex should be illegal, or else we may have less homophobia
  

  “Today’s opinion is the product of a Court, which is the product of a law-profession culture, that has largely signed on to the so-called homosexual agenda, by which I mean the agenda promoted by some homosexual activists directed at eliminating the moral opprobrium that has traditionally attached to homosexual conduct. ”

  Scalia’s dissent in Lawrence vs Texas

• Native Americans, during their religious rituals, cannot be excluded from obeying the law because of their religious belief
  

  “Conscientious scruples have not, in the course of the long struggle for religious toleration, relieved the individual from obedience to a general law not aimed at the promotion or restriction of religious beliefs. The mere possession of religious convictions which contradict the relevant concerns of a political society does not relieve the citizen from the discharge of political responsibilities. (…) To permit this would be to make the professed doctrines of religious belief superior to the law of the land, and in effect to permit every citizen to become a law unto himself.”

  Scalia’s majority opinion in Employment Division v. Smith

• To counteract the consequences of the above ruling, Congress passed the Religious Freedom Restoration Act, to protect the ability of religious minorities to carry on their rituals. Subsequently, the Supreme Court found that corporations have religious beliefs, and that not providing comprehensive health coverage is a ritual
  

  “By requiring the Hahns and Greens and their companies to arrange for such coverage, the HHS mandate demands that they engage in conduct that seriously violates their religious beliefs. (…) The contraceptive mandate, as applied to closely held corporations, violates RFRA”

  Alito’s majority opinion, joined by Scalia, in Burwell v. Hobby Lobby, inc.

• On the majority opinion in Obergefell v. Hodges
  

  “If, even as the price to be paid for a fifth vote, I ever joined an opinion for the Court that began: ‘The Constitution promises liberty to all within its reach, a liberty that includes certain specific rights that allow persons, within a lawful realm, to define and express their identity,’ I would hide my head in a bag. The Supreme Court of the United States has descended from the disciplined legal reasoning of John Marshall and Joseph Story to the mystical aphorisms of the fortune cookie.”

  Scalia’s dissent in Obergefell v. Hodges

Alexander Grothendieck

Alexander Grothendieck died on Thursday at age 86 in Saint-Girons.

Grothendieck, who started his work in functional analysis, is known for his far-reaching (and still incomplete) program of creating new foundations for algebraic geometry, a work that he led at IHES in the 50s and 60s and that is documented in the thousands of pages of EGA and SGA. If modern algebraic geometry is built on schemes, has applications to number theory, has definitions given in a category-theoretic language, and is completely incomprehensible to the novice, it is all thanks to Grothendieck’s vision.

In his 40s, and the top of his game, Grothendieck left IHES over the issue of military funding, and progressively detached from the mathematical community, while embracing environmental and anti-war causes.

Grothendieck’s life story, from his escaping Nazi Germany, to his revolution in mathematics, to his radical politics and later hermit life, is spellbinding. Some of it is told in a great two-part article in the Notices of the AMS (part 1, part 2) and I would also recommend this more technical essay and this more philosophical one.

Grothendieck has a flair for effective naming, he had a way with words, and he liked elaborate metaphors. Here is his famous “how to break a nut” analogy describing his style of mathematical research

I can illustrate the second approach with the same image of a nut to be opened. The first analogy that came to my mind is of immersing the nut in some softening liquid, and why not simply water? From time to time you rub so the liquid penetrates better, and otherwise you let time pass. The shell becomes more flexible
through weeks and months—when the time is ripe, hand pressure is enough, the shell opens like a perfectly ripened avocado!

This week in history

The great earthquake of 1906 struck San Francisco on April 18, around 5 in the morning. While the earthquake already caused a lot of damage, it was the subsequent fire that ravaged the city: the earthquake had broken the water pipes, and so it was impossible to fight the fire because the hydrants were not working. Except for the hydrant at Church and 20th, which saved my house and a good part of the mission. The hydrant is painted golden, and once a year, on the anniversary of the earthquake, the fire department repaints it and leaves a token of appreciation. (They actually do it at 5 in the morning.)

By the way, there are two faults that can cause earthquakes in the San Francisco Bay Area. One is (our stretch of) the San Andreas fault, which runs close to the ocean, and which caused the 1906 quake and the 1989 one, and which may not be an imminent risk given the energy released in 1989. The other is the Hayward fault, which runs near Berkeley. The Hayward fault had big earthquakes in 1315, 1470, 1630, 1725, and 1868, that is about every 100-140 years, with the last one being 146 years ago…

25 years ago on April 15, Hu Yaobang died. The day before his funeral, about 100,000 people marched to Tiananmen square, an event that led to the occupation of the square, and which culminated in what in mainland China used to be referred to as the “June 4 events,” and now as the “I don’t know what you are talking about” events.

Also, something happened, according to tradition, 1981 years ago.

Ora e sempre resistenza

Today it’s my favorite of Italy’s public holidays.

To keep a long story long, at the start of WW2, Italy, which was an ally of Germany, was initially neutral, in part because its armed forces were completely unprepared for war. At some point in the May of 1940, with German troops advancing into France, and British troops evacuating the continent, Italy decided to join what looked like a soon-to-end war, in order to claim some French territories and colonies.

But then, in 1941, Germany attacked Russia and Japan attacked the US, underestimating what they were getting into, and by the beginning of 1943 the tide was clearly turning against the “axis.” Italy’s king, who was definitely not the “fight until the last man” type, had Mussolini arrested, installed a general as prime minister, and started negotiating Italy’s surrender with the allies (even as Italian troops were fighting with the Germans in Russia and in Africa). Eventually, on September 8, 1943, the king announced a cease-fire. Because of the secrecy of the negotiations, nobody knew what was going in advance, and most of the Italian troops that were fighting with the Germans were taken prisoners, while the rest of the armed forces basically disbanded. German troops came into Italy from the North to occupy it, even as allied troops landed in Sicily and took control of most of Southern Italy. The king fled to the South, and the Germans freed Mussolini and installed him as head of a puppet government in the North.

With the Italian army disbanded, and with the allies neglecting the “Southern front” in Italy as they were plotting the landing in Normandy, guerilla groups were formed in Northern Italy to fight the Germans. Eventually, in April 1945 the German troops were retreating from the Eastern and Western fronts against the advancing American and Russian forces, and the allied made another push in Italy; concurrently, the resistance organizations planned an insurrection that, on April 25, liberated Torino and Milan. All the German forces in Italy surrendered on April 29.

The resistance was the training ground of some of the first generation of politicians of the new Italian Republic (a referendum to abolish the monarchy passed in 1946, and a new Republican constitution was approved in 1948), and it brought people who were willing to die for their ideals into politics. That spirit didn’t last very long, but it remains one of the few bright spots in recent Italian history.

In Theory Celebrates the Turing Centennial

This year there are several festivities on the occasion of Turing‘s 100th birthday, which is next month, including the celebration that took place in Princeton a couple of weeks ago, the ACM-organized event next month, several events at the Newton institute in the UK, and several other events all over the world. Most of Turing centennial initiatives have taken the form of lectures and articles describing how far we have (or not) gone since Turing’s time in our understanding of computation.

Certainly, a big part of Turing’s life was being gay, which was not exceptional among leading British mathematicians of his time, or even among founding fathers of theoretical computer science, although his way of being “out” was (like his research) much ahead of its time.

(I think all readers of in theory are familiar with the story of how Turing’s openness led to his tragic death: after a robbery in his home, Turing told the police that he suspected that a certain 19 year old guy who had been in his home was involved in the robbery; after telling the police the nature of his relationship with said guy, Turing was arrested and prosecuted; despite the intervention of highly-placed people who were aware of the importance of his work, Turing was found guilty and, while he avoided jail time, he was sentenced to a “hormonal therapy” that was a sort of chemical castration, and he lost his security clearance. Shortly afterward he committed suicide by poisoning and eating an apple.)

Within the Turing festivities, I think it would be interesting to talk about how things have changed (or not) since Turing’s time for people who do academic work in cryptography and in the theory of computing and who are gay or lesbian.

So I have invited a number of gay and lesbian colleagues to write guest posts talking about how things have been for them, and so far half a dozen have tentatively accepted. Their posts will appear next month which, besides being Turing’s centennial month, also happens to be the anniversary of the Stonewall riots.

Those who have agreed to participate are a diverse bunch, male and female, junior and senior, and working or coming from the Americas, Europe and Asia.

But I would still be delighted to have additional contributors. The posts could be signed or pseudonymous, personal or political, anecdotal or philosophical, and basically about anything. Explaining why you reject the premise of having such posts in the first place would also be an acceptable topic. I would be particularly happy to have contributors currently working in Asia or Southern Europe. Email me (trevisan at stanford) if you are interested.

In Soviet Russia, computer reboots you

A wonderful scholarly work on the history of computing in the Soviet Union is now available as a free ebook. It doesn’t talk about the “cybernetics” Soviet school of theoretical computer science, except for a section on Akushsky (who worked on computer arithmetic) in which Kolmogorov is mentioned in passing, but it is still a very interesting book.

Happy Sesquicentennial, Italy!

So your prime minister pays underage girls for sex, but you have given the word Enrico Fermi, Sophia Loren, Italo Calvino, Federico Fellini, Luigi Pirandello, early algebraic geometry, neorealismo and futurismo. I’ll call it a tie.

(Related memory: one night during STOC 1997 in El Paso, a group of theoreticians that included Daniele Micciancio and myself goes to Juarez, and walks into the one bar that didn’t seem to have prostitutes sitting outside. Daniele and I are talking, and the man sitting next to Daniele stares at us oddly. Finally, he asks what language we are talking in. “Ah, Italy,” he then says, “Paolo Rossi! Edwige Fenech!”)