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ó!
Follow
Comment #1 March 17th, 2021 at 10:51 pm
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.
Comment #2 March 17th, 2021 at 10:51 pm
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.
Comment #3 March 17th, 2021 at 11:10 pm
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.
Comment #4 March 17th, 2021 at 11:14 pm
Congratulations Avi and László !!
Comment #5 March 18th, 2021 at 11:12 am
When I saw that news I was pretty sure Scott would be connected to it in some way. Nice!
Comment #6 March 19th, 2021 at 2:01 am
The news piece about the prize on AMS website also claims that P=BPP has been proven.
Comment #7 March 19th, 2021 at 8:55 am
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.
Comment #8 March 19th, 2021 at 1:28 pm
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.
Comment #9 March 19th, 2021 at 2:42 pm
Scott #8
But isn’t that objective too narrow to alone prove that the permanent is not in FP ?
Comment #10 March 19th, 2021 at 3:51 pm
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?
Comment #11 March 19th, 2021 at 4:07 pm
@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.
Comment #12 March 19th, 2021 at 4:07 pm
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.
Comment #13 March 19th, 2021 at 4:37 pm
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.
Comment #14 March 19th, 2021 at 4:46 pm
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.
Comment #15 March 19th, 2021 at 5:01 pm
Amazing! A well deserved prize for Avi and Laci!
Avi is a fantastic human being.
Comment #16 March 19th, 2021 at 7:41 pm
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.
Comment #17 March 19th, 2021 at 8:12 pm
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.
Comment #18 March 20th, 2021 at 6:09 am
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?
Comment #19 March 20th, 2021 at 1:29 pm
[…] (and many other places); blogs: In theory (Finally, a joy), Computational Complexity (Ohh Boy), Shtetl Optimized, Igor […]
Comment #20 March 20th, 2021 at 5:11 pm
Out of curiosity, what has changed and upgraded the Abel Prize to a rival of the Fields Medal in recognizing achievement in pure mathematics?
Comment #21 March 20th, 2021 at 5:58 pm
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.
Comment #22 March 21st, 2021 at 4:29 pm
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.
Comment #23 March 26th, 2021 at 11:23 am
[…] 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 […]
Comment #24 March 26th, 2021 at 4:59 pm
May I ask why Turing award winners did not get the award and conversely why the winners did not get Turing award?
Comment #25 March 26th, 2021 at 7:36 pm
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!
Comment #26 March 30th, 2021 at 6:27 pm
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.
Comment #27 April 1st, 2021 at 10:43 am
‘just taken some major steps toward it’ is there anywhere written about it?
Comment #28 June 8th, 2021 at 3:58 pm
Sorry what mathematics is needed to understand the scaling algorithm for perfect matching of column and row renormalization and converge speed issues? It is really amazing the algorithm exists but how to understand the convergence is in polynomial time? Is it convex geometry analysis?