Theory of Computing: the Book

Over the past four decades, Avi Wigderson, figuratively, wrote the book on theoretical computer science. Now he has literally done so. I can’t wait for the movie adaptation.

Advertisements

Corrado Bohm

SUP_0236

I was very saddened to hear that Corrado Böhm died today at age 94.

Böhm was one of the founding fathers of Italian computer science. His dissertation, from 1951, was one of the first (maybe the first? I don’t know the history of these ideas very well) examples of a programming language with a compiler written in the language itself. In the 1950s and 1960s he worked at the CNR (an Italian national research institution with its own technical staff), in the IAC (Institute for the Applications of Computing) directed by mathematician Mauro Picone. IAC was the second place in Italy to acquire a computer. In 1970 he moved to the University of Turin, were he was the founding chairman of the computer science department. In 1972 he moved to the Sapienza University of Rome, in the Math department, and in 1989 he was one of the founders of the Computer Science department at Sapienza. He remained at Sapienza until his retirement.

Böhm became internationally known for a 1966 result, joint with Giuseppe Jacopini, in which he showed, roughly speaking, that programs written in a language that includes goto statements (formalized as flow-charts) could be mapped to equivalent programs that don’t. The point of the paper was that the translation was “structural” and the translated program retained much of the structure and the logic of the original program, meaning that programmers could give up goto statements without having to fundamentally change the way they think.

Dijkstra’s famous “Go To Statement Considered Harmful” 1968 letter to CACM had two references, one of which was the Jacopini-Böhm theorem.

Böhm was responsible for important foundational work on lambda calculus, typed functional languages, and the theory of programming languages at large.

He was a remarkable mentor, many of whose students and collaborators (including a notable number of women) became prominent in the Italian community of theory of programming languages, and Italian academia in general.

gruppetto

In the photo above is Böhm with Simona Ronchi, Betti Venneri and Mariangiola Dezani, who all became prominent Italian professors.

You may also recognize the man on the right as a recent recipient of the Turing Award. Silvio Micali went to Sapienza to study math as an undergrad, and he worked with Böhm, who encouraged Silvio to pursue his PhD abroad.

I studied Computer Science at Sapienza, starting the first year that the major was introduced in 1989. I remember that when I first met Böhm he reminded me of Doc Brown from Back to the Future: a tall man with crazy white hair, speaking of wild ideas with incomprehensible technical terms, but with unstoppable enthusiasm.

One year, I tried attending a small elective class that he was teaching. My, probably imprecise, recollection of the first lecture is as follows.

He said that one vertex is a binary tree, and that if you connect two binary trees to a new root you also get a binary tree, then he asked us, how would you prove statements on binary trees by induction? The class stopped until we would say something. After some consultation among us, one of the smart kids proposed “by induction on the number of vertices?” Yes, said Böhm, that would work, but isn’t there a better way? He wanted us to come up by ourselves with the insight that, since binary trees have a recursive definition, one can do induction on the structure of the definition.

In subsequent lectures, we looked (without being told) at how to construct purely functional data structures. I dropped the class after about a month.

(Photo credits: corradobohm.it)

Annuntio vobis gaudium magnum: habemus directors

goldwasser_86278892
(Photo credit: ACM)

Formally ending a search started in March 2016 (and a process started in the Fall of 2015), we are pleased to finally officially announce that Shafi Goldwasser will take over from Dick Karp as director of the Simons Institute for Computing on January 1st, and will return to Berkeley after a 30+ year hiatus.

Shafi is the co-inventor and developer of the notions semantic security in encryption; of zero-knowledge proofs; of pseudorandom functions; of the connection between PCP and hardness of approximation; and of property testing in sublinear algorithms, among others. She has received the Turing award for her work on cryptography and of two Gödel prizes for her work on complexity.

I cannot put in words how happy I am for the Berkeley community, including myself, and for the future of the Institute.

The director search was my first glimpse into how the Berkeley central campus bureaucracy operates, and it was horrifying. The simplest thing couldn’t be done without a sequence of authorities signing off on it, and each authority had a process for that, which involved asking for other things that other authorities had to sign off on, and so on in what at times seemed actual infinite descent.

The announcement linked above was in the works for at least three weeks!

Alistair Sinclair, after two terms as associate director of the Simons Institute, during which his heroic efforts were recognized with the SIGACT service award, also retired from his position at the Institute, and last July 1st was replaced by Berkeley professor Peter Bartlett, a noted pioneer of the study of neural networks.

This weekend, on Saturday, the Simons Institute will host the FOCS reception, which will double as celebration for Alistair’s prize. There will buses leaving the conference hotel at 6:45pm, and there will be plenty of food (and drinks!) at the Institute. There will also be buses taking people back to the hotel, although once you are in downtown Berkeley on a Saturday evening (bring a sweater) you may want to hang out a bit more and then take a rideshare service back to the hotel.

On Norbert Blum’s claimed proof that P does not equal NP

Edited 8/16 to correct attributions to Alon and Boppana and to Tardos, thanks to an anonymous commenter for the correction

Yesterday, Norbert Blum posted a preprint with a claimed proof that {P\neq NP}. An incorrect comment that I made last night and corrected this morning caused a lot of confusion, so let me apologize by summarizing the claims in the paper.

Coincidentally, this week, there is an Oberwolfach workshop on proof complexity and circuit complexity, so I am confident that by the end of the week we will hear substantive comments on the technical claims in the paper.

Recall that if a decision problem is solvable by an algorithm running in time {t(n)} on inputs of length {n} then, for every {n}, it is also solved, on inputs of length {n}, by a circuit of size {O(t^2(n))}. Thus, if a problem is solvable in polynomial time it is also solvable by a family of polynomial size circuits (or, in short, it has polynomial circuit complexity).

The paper claims that Clique has exponential circuit complexity, and hence it has no polynomial time algorithm and {P\neq NP}. The argument leverages known results from monotone circuit complexity.

A monotone circuit is a boolean circuit that has only AND gates and OR gates, but does not have any NOT gates. A decision problem is a monotone problem if, for every fixed input length, it is solvable by a monotone circuit. For example, the problem to decide if a given {n}-vertex graph has a clique of size at least {\sqrt n} is a monotone problem (if the input graph is presented as a boolean adjacency matrix), and so is the problem of deciding if a given graph has a perfect matching.

In the 1980s, Razborov proved that Clique cannot be computed by polynomial size monotone circuits. Later Andreev proved that there is a monotone problem in NP that requires exponential size monotone circuits, and Tardos Alon and Boppana proved that Clique itself requires exponential size monotone circuits. At the time, it was conjectured that if a monotone problem is in P, then it is solvable by a family of polynomial size monotone circuits. Under this conjecture, Razborov’s result would imply that Clique is not in P, and hence {P\neq NP}.

Unfortunately, Razborov refuted this conjecture, by showing that the perfect matching problem, which is in P, does not have polynomial size monotone circuits. Tardos showed that the Alon-Boppana exponential lower bound for clique holds for any monotone function sandwiched between the clique number and the chromatic number of a graph, including the Lovasz Theta function. Since the Theta function is polynomial time computable, and hence has polynomial size circuits, this shows that the gap between monotone circuit complexity and general circuit complexity can be exponentially large. (See first comment below.)

Razborov’s proof of the Clique lower bound for monotone circuits introduced the powerful approximation method. Roughly speaking, his approach was to start from a hypothetical polynomial size family of monotone circuits for Clique, and, from that, build a family of approximating circuits, which are just DNF formulas. The approximating circuits constructed by his method do not solve the Clique problem in general, but they solve a “promise” version of the problem, that is, they solve Clique on a certain subset of graphs. Then Razborov finishes the argument by showing that the approximating circuits are so simple that it is impossible for them to even solve Clique on that subset of inputs, thus reaching a contradiction to the assumption that there are monotone polynomial size circuits for Clique. The approximation method, variously modified, was also used to prove the lower bounds for Andreev’s problem and for matching.

Tim Gowers wrote a wonderful exposition of Razborov’s method, trying to show how one would come up with the various ideas, rather than just presenting the proof step by step.

Berg and Ulfberg simplify the proofs of Razborov, Andreev and Tardos for Clique and Andreev’s problem (but not for matching) by showing how to construct an approximator that has both small DNF complexity and small CNF complexity. The stronger claim makes an inductive argument in the construction easier to establish.

(At this point, I should clarify that I have never properly studies these results, so I am probably getting some details wrong. Please post corrections in the comments.)

The main claim in Blum’s paper is Theorem 6, which claims that if polynomial-size monotone circuits for a monotone problem admit a “CNF-DNF approximator” for a promise restriction of the problem (like the Berg-Ulfberg one), then also general circuits for the same problem admit such an approximator. Thus, if the approximator does not exist, it not only follows that the monotone complexity of the problem is super-polynomial, but also the general circuit complexity of the problem is superpolynomial.

Together with the Berg-Ulfberg approximator for monotone circuits for Clique, this implies that Clique is not in P.

Now, what could possibly go wrong with this argument?

  • What about natural proofs?

    This argument can only applied to (certain) monotone problems, and monotone problems are a vanishing fraction of all problems, hence one does not have the “largeness” property of natural proofs, and the argument is not a natural proof. (This is noted in the paper.)

  • What about relativization and algebrization?

    The argument starts from a boolean circuit for a given problem. If one is given an oracle circuit, with gates that answer oracle queries, or give evaluation of a polynomial extension of the problem, the argument cannot be applied.

  • But this argument is lifting monotone circuit lower bounds to general circuit lower bounds, and so what about perfect matching, which has an exponential monotone circuit lower bound and a polynomial general circuit upper bound?

    It is not known how to make the known lower bound for matching work via a “CNF-DNF approximator” and the claims in the paper only concern monotone lower bounds proved in this way. (Edited to add: but what about the Lovasz theta function?)

  • But didn’t Razborov prove that the approximation method cannot prove a better-than-quadratic lower bound for general circuits?

    Like any no-go theorem, Razborov’s impossibility result makes some assumption on what it means to “apply the approximation method to general circuits” and Blum claims that the assumptions do not apply to his argument.

  • But where is the “heavy lifting” done? Shouldn’t every proof of a major result have one or more steps that are unlike anything done before?

    I don’t have a good answer to this question. All the work is done in the proof of Theorem 6, which is the construction of the approximator starting from an arbitrary circuit. Maybe the argument is right and the heavy lifting was in Razborov’s work and subsequent extension and simplifications, and the fact that one can handle NOT gates at the bottom can be handled with an argument that is syntactically similar to previous work. Or, something goes wrong in the construction. Either way we will probably know soon.

Congratulations

I was really delighted with all the prizes that were announced at STOC this year.

pasinOur own Pasin Manurangsi received the Danny Lewin STOC Student Paper Award for his work on the hardness of the dense k-subgraph problem. This is the problem in which we are given a graph and a number k, and we want to find the set of k vertices that induces the most edges. Pasin, who is co-advised by Prasad Raghavendra and me, discovered a new, simple but ingenious reduction that establishes hardness up to almost polynomial factors.

I received the same award exactly twenty years ago, also for a hardness-of-approximation result established via a simple reduction. (Prasad also received it, nine years ago, for a hardness-of-approximation result established via a difficult reduction.) I then spent time at MIT, where Oded Goldreich was, and, partly thanks to his influence, I did my best work there. Pasin is spending this summer at Weizmann, where Oded Goldreich is, so, no pressure, but let’s see what happens. . .

alistairsinclair01-resize

Alistair Sinclair received the ACM SIGACT Distinguished Service prize, for his work setting up and leading the Simons Institute for the Theory of Computing.

Those who have been to the institute, that is, almost the whole theoretical computer science community, have seen that it is a place uniquely conducive to do good work. If you stop at think about what it is that makes it so, Alistair’s hand is behind it. The open layout of the second floor, with the whiteboards dividing the space and absorbing sound? Alistair worked closely with the architect, for a year, during the renovation, to make sure that the design would best fit the needs of our community. The friendly, competent and responsive staff? Alistair sat in all the interviews when the staff was recruited, and participates in their performance review. So many things happening and never a conflict? You know whom to thank.

More substantially, almost all the programs that we have had were, to some extent, solicited, and Alistair led the conversations and negotiations with all prospective organizers, shepherding promising concepts to approved programs.

Alistair has also been relentless in making people do things, and making them do things by prescribed deadlines, something that is notoriously difficult in our community. The Simons Institute programs have succeeded, in part, because of the tremendous amount of volunteer work that the organizers donated to our community, and while they would all have been extremely generous with their time in any case, Alistair made sure that they were extra generous. A personal anecdote: I was one of the organizers of one of the Fall 2013 inaugural programs. At that point, I was at Stanford and we were beginning to discuss the idea that I could come back to Berkeley. At some point, around October, I get a phone call from Alistair, and I assume he wants to talk about it. Instead, he goes “you know, I haven’t been seeing you much at the Institute so far. We expect organizers to be around a lot more.” A few months later, I got the offer to move to Berkeley, with a 50% affiliation at the Institute. Even knowing who my boss would be, I enthusiastically accepted.

oded Oded Goldreich received the Knuth Prize. I have already said how I feel about Oded, so there is no need to repeat myself, but I will add that I am also really happy for the Knuth Prize itself, that has managed to consistently make really good choices for the past 21 years, which is an outstanding record.

godelFinally, and I can’t believe that it took so long, the paper of Dwork, McSherry, Nissim and Smith, that introduced differential privacy, has been recognized with the Godel prize. I am very happy for them, especially for my matron of honor and former neighbor Cynthia.

Congratulations to all, and by all I don’t mean just the aforementioned awardees, but also our whole community, that nurtures so many great people, inspires so many good ideas, and makes being part of it such a joy (even when Alistair makes me do things).

Chariots of Fire: Silvio Micali on Oded Goldreich and Scientific Collaborations

At the aforementioned Oded Fest that took place at Weizmann a couple of weeks ago, Silvio Micali read from an epic prepared speech, which tied together the early work on foundations of cryptography, ancient Greece, the Renaissance, Viennese cafés, and the movies “Chariots of Fire” and “The Seven Samurai.”

Silvio has given his kind permission to share the speech, and he has put it in a pdf form that includes the pictures that he used as slides.

Here it is

Fests

I have been in Israel for the last couple of days attending an event in honor of Oded Goldreich‘s 60th birthday.

Oded has touched countless lives, with his boundless dedication to mentoring, executed with a unique mix of tough love and good humor. He embodies a purity of vision in the pursuit of the “right” definitions, the “right” conceptual point of view and the “right” proofs in the areas of theoretical computer science that he has transformed with his work and his influence.

A turning point in my own work in theoretical computer science came when I found this paper online in the Spring of 1995. I was a second-year graduate student in Rome, and I was interested in working on PCP-based hardness of approximation, but this seemed like an impossible goal for me. Following the publication of ALMSS, there had been an avalanche of work between 1992 and 1995, mostly in the form of extended abstracts that were impossible to understand without an awareness of a context that was, at that point, purely an oral tradition. The aforementioned paper, instead, was a 100+ page monster, that explained everything. Studying that paper gave me an entrance into the area.

Three years later, while i was a postdoc at MIT and Oded was there on sabbatical, he played a key role in the series of events that led me to prove that one can get extractors from pseudorandom generators, and it was him who explained to me that this was, in fact, what I had proved. (Initially, I thought my argument was just proving a much less consequential result.) For the most part, it was this result that got me a good job and that is paying my mortgage.

Like me, there are countless people who started to work in a certain area of theoretical computer science because of a course that Oded taught or a set of lecture notes that he wrote, and countless people whose work was made possible by Oded nudging, or usually shoving, them along the right path.

The last two days have felt a bit like going to a wedding, and not just because I saw friends that I do not get to see too often and because there was a lot to eat and to drink. A wedding is a celebration of the couple getting married, but it is also a public event in which friends and family, by affirming their bonds to the newlyweds, also affirm their bonds to each other.

I was deeply moved by the speeches given by Silvio and Shafi, and really everybody did a great job at telling Oded stories and bringing to life various aspects of his work and personality. But perhaps the most fittingly weird tribute was Benny Chor presenting the Chor-Goldreich paper (the one that introduced min-entropy as a measure of randomness for weak random sources, and the problem of 2-source extraction) using the original 1985 slides.

IMG_6726

Speaking of public celebrations, there is less than a month left to register for STOC 2017, the “Theory Fest” that will take place in Montreal in June.

Matrix Multiplication Not Yet Doable In Quadratic Time

Last night, a paper appeared on the arXiv titled A \Theta(n^2) time matrix multiplication algorithm.

At first look the paper seemed to score zero on Scott Aaronson’s list of Ten Signs a Claimed Mathematical Breakthrough is Wrong, and it came from a researcher who has worked extensively on the related problem of all-pairs shortest path, so it looked exciting. Unfortunately, it actually scores one on Scott’s list: it contradicts known impossibility results. (Thanks to Yuval Filmus for the references.)

The first step in the algorithm is to show how to compute the inner product of two 3^n-dimensional vectors using n^{O(1)} \cdot 2^n multiplication. This contradicts a lower bound due to Pan (see here the proof of a more general result) that computing the inner product of two N-dimensional vectors require at least N multiplications.

In addition, Raz has proved an \Omega (n^2 \log n) lower bound for matrix multiplication arithmetic circuits, and, to the best of my understanding, the paper’s claims imply an O(n^2) size arithmetic circuit. (Raz’s lower bound assumes that the circuit is not given access to large constants; as far as I can see, the formulas in Han’s paper do not require large constants.)

What’s New at the Simons Institute

This Thursday (December 15) is the deadline to apply for post-doctoral positions at the Simons Institute for the next academic year. In Fall 2017 we will run a single program, instead of two programs in parallel, on optimization. The program will be double the size of our typical programs, and will focus on the interplay between discrete and continuous methods in optimization. In Spring 2018 there will be a program on real-time decision-making and one on theoretical neuroscience.

In a few weeks, our Spring 2017 programs will start. The program on pseudorandomness will have a mix of complexity theorists and number theorists, and it will happen at the same time as a program on analytic number theory at MSRI. It will start with a series of lectures. It will start with a series of lectures in the third week of January. The program on foundations of machine learning has been much anticipated, and it will also start with a series of lectures, in the fourth week of January, which will bring to Berkeley at impressive collection of machine learning practitioners whose research is both applied and rigorous. All lectures will be streamed live, and I encourage you to set up viewing parties.

During the current semester, the Simons Institute had for the first time a journalist in residence. The inaugural resident journalist has been Erica Klarreich, that many of you probably know for her outstanding writing on mathematics and computer science for quanta magazine.

Next semester, our resident journalist will be Pulitzer-prize winner John Markoff, who just retired from the New York Times.