Abel to win

Many of you will have seen the happy news today that Avi Wigderson and László Lovász share this year’s Abel Prize (which now contends with the Fields Medal for the highest award in pure math). This is only the second time that the Abel Prize has been given wholly or partly for work in theoretical computer science, after Szemerédi in 2012. See also the articles in Quanta or the NYT, which actually say most of what I would’ve said for a lay audience about Wigderson’s and Lovász’s most famous research results and their importance (except, no, Avi hasn’t yet proved P=BPP, just taken some major steps toward it…).

On a personal note, Avi was both my and my wife Dana’s postdoctoral advisor at the Institute for Advanced Study in Princeton. He’s been an unbelievably important mentor to both of us, as he’s been for dozens of others in the CS theory community. Back in 2007, I also had the privilege of working closely with Avi for months on our Algebrization paper. Now would be a fine time to revisit Avi’s Permanent Impact on Me (or watch the YouTube video), which is the talk I gave at IAS in 2016 on the occasion of Avi’s 60th birthday.

Huge congratulations to both Avi and László!

27 Responses to “Abel to win”

  1. Gerard Says:

    Scott

    When you call the permanent a “low-degree polynomial” what is your definition of “low-degree” ?

    I mean all of its terms are actually degree n (considering the matrix elements to be the variables of the polynomial), right. That doesn’t seem particularly low-degree to me.

  2. Boaz Barak Says:

    Thanks Scott for bringing back memories of that workshops and all the other great times I’ve had in Princeton, much of it intersecting with you and Dana. So many of us in the community have a similar “Avi story”, how a single talk or piece of advice he gave us had a lasting effect. He is really one of a kind and I feel very lucky to also know him as a postdoc advisor, mentor, and friend.

  3. Scott Says:

    Gerard #1: I mean, of low enough degree that it’s useful to regard it as a polynomial rather than just some arbitrary function of finite field elements. In the present context, that means of degree polynomial in n.

  4. Raoul Ohio Says:

    Congratulations Avi and László !!

  5. fred Says:

    When I saw that news I was pretty sure Scott would be connected to it in some way. Nice!

  6. anon Says:

    The news piece about the prize on AMS website also claims that P=BPP has been proven.

  7. Gerard Says:

    Would it be accurate to characterize GCT as an attempt to reduce computational complexity conjectures to the complexity of representation of certain mathematical objects, thus divorcing them from the full power of the TM computational model ?

    For example you could ask if there is some way to represent the exponentially many terms of the permanent polynomial using only a polynomial number of arithmetic operations. At first glance this seems unlikely, except when you realize that the determinant (whose calculation is in FP) contains all the same terms, just with different signs. But though the determinant can be computed in P-time, does it have a simple representation in terms of algebraic operations ? If the answer is no then it seems somewhat doubtful that computational complexity can be reduced to the complexity of mathematical representations.

  8. Scott Says:

    Gerard #7: What you wrote would apply to pretty much all computational complexity, or at least all arithmetic complexity. GCT is a more specific program that aims to use geometric invariant theory and representation theory to show, e.g., that the permanent “lacks the right kinds of symmetries” to be embedded as the determinant of an only polynomially larger matrix.

  9. Gerard Says:

    Scott #8

    But isn’t that objective too narrow to alone prove that the permanent is not in FP ?

  10. Job Says:

    The P=BPP statement on AMS site is probably the result of misreading the prize citation, but still.

    It’s important to get these things right. Imagine having your most important contributions over-represented, then downgraded.

    But speaking of P vs BPP.

    Suppose there is a machine that can tell you the probability of the output register having its current value (it outputs x,p(x) pairs).

    That seems sufficient to factor integers, but what else can it do? It seems weaker than NP, and alot weaker than #P, but how does it compare to BQP?

    Do you know if there is a corresponding complexity class?

  11. Will Says:

    @Gerard #7

    Yes, the determinant has a simple representation in terms of algebraic operations. You can express the usual algorithm to evaluate the determinant using Gaussian elimination straightforwardly in terms of addition, multiplication, subtraction, and division, and this takes only polynomially many steps.

  12. Job Says:

    I guess for decision problems it would be #P since knowing the probability of a “no” is good enough?

    Wondering how you can make this weaker such that it can only solve period-finding.

  13. Scott Says:

    Job #12: Yes, your problem is #P-complete. I only know of a few models that can do period-finding efficiently but not NP or higher; two examples are BQP and SZK.

  14. Scott Says:

    Gerard #9: No, the whole point of Valiant’s work in the 1970s was that it’s already enough to prove the algebraic analogue of P≠NP! See e.g. my paper for more.

  15. Ryan Alweiss Says:

    Amazing! A well deserved prize for Avi and Laci!

    Avi is a fantastic human being.

  16. Gerard Says:

    Will #11

    Doesn’t Gaussian Elimination require making decisions based on the values in the matrix ? That means that in addition to the basic algebraic operations your circuit will need to include the the equivalent of if/then/else branches and it seems like that could result in a circuit of exponential size.

    If you know of a paper or reference that reduces the calculation of the determinant of an arbitrary nxn matrix to a polynomial sized circuit I’d be interested in seeing it.

  17. Gerard Says:

    Will #11

    Sorry, I should have looked at Scott’s paper from comment #14 before responding to yours. It looks like that has all the references I need on the subject of circuits for computing the determinant.

  18. Man To Research Says:

    Can P=BPP be asked in GCT? Isn’t GCT asking for impossibility of PP in P? So it can explain why it can avoid BPP not in P?

  19. Cheerful News in Difficult Times: The Abel Prize is Awarded to László Lovász and Avi Wigderson | Combinatorics and more Says:

    […] (and many other places); blogs:  In theory (Finally, a joy), Computational Complexity (Ohh Boy), Shtetl Optimized, Igor […]

  20. Pierre Says:

    Out of curiosity, what has changed and upgraded the Abel Prize to a rival of the Fields Medal in recognizing achievement in pure mathematics?

  21. Scott Says:

    Pierre #20: The Abel Prize fixed two massive problems with the Fields Medal—that it’s only given to mathematicians age 40 or younger, and only once every 4 years—and it had an order of magnitude more money behind it than the Fields to boot. After that, I suspect it was only a matter of the Abel Prize continuing for a couple decades, building up an unimpeachably impressive list of laureates, for it to acquire a Fields-like cachet.

  22. Timothy Chow Says:

    Naturally, I am delighted that Avi Wigderson and László Lovász have won the Abel Prize.

    Before the Abel Prize was established, I had my own private list of “greatest mathematicians never to have won the Fields Medal.” Almost everyone on that list (who hasn’t died in the meantime) has since won an Abel Prize. But here’s someone that hasn’t been awarded either prize: Saharon Shelah. I hope he wins the Abel Prize someday.

  23. Congrats Avi and Laci on the Abel Prize | Gödel's Lost Letter and P=NP Says:

    […] reported on the Abel Prize, including some of our fellow bloggers: Gil Kalai here, Scott Aaronson here, Lance Fortnow and Bill Gasarch here, plus Kevin Hartnett for Quanta […]

  24. Man To Research Says:

    May I ask why Turing award winners did not get the award and conversely why the winners did not get Turing award?

  25. Scott Says:

    Man To Research #24: The Turing Award is for all of CS (including systems-building that isn’t mathematical at all), while the Abel Prize is for all of math (including parts that have nothing to do with CS). Even when we restrict ourselves to CS theory, the Turing Award puts more emphasis on connections to practical problems (cryptography, machine learning, etc), the Abel Prize on mathematical depth. There are surely people who are plausible candidates for both, but not many!

  26. gentzen Says:

    Timothy Chow #22: Saharon Shelah gave the Paul Bernays Lectures 2020 (the Paul Bernays Lectures 2019 were given by our host Scott). Avi gave the Wolfgang Pauli Lectures 2012, so maybe Saharon will win the Abel prize in 2030.

  27. Man To Research Says:

    ‘just taken some major steps toward it’ is there anywhere written about it?

Leave a Reply

Comment Policy: All comments are placed in moderation and reviewed prior to appearing. Comments can be left in moderation for any reason, but in particular, for ad-hominem attacks, hatred of groups of people, or snide and patronizing tone. Also: comments that link to a paper or article and, in effect, challenge me to respond to it are at severe risk of being left in moderation, as such comments place demands on my time that I can no longer meet. You'll have a much better chance of a response from me if you formulate your own argument here, rather than outsourcing the job to someone else. I sometimes accidentally miss perfectly reasonable comments in the moderation queue, or they get caught in the spam filter. If you feel this may have been the case with your comment, shoot me an email.

You can now use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations.