As previously announced, next week Alon Rosen and I are organizing a workshop at Bocconi, which will actually be the union of two workshops, one on Recent Advances in Cryptography and one on Spectral and Convex Optimization Techniques in Graph Algorithms. Here is the program. In short:
Some time ago, I received a message to the effect that I was being considered for membership in the “Academy of the XL”, to which my reaction was, hey, we have all gone out of shape during the pandemic, and body-shaming is never… then it was explained to me that, in this context, “XL” means “forty” and that the Academy of the Forty is Italy’s National Academy of Science.
Italy has a wonderfully named, and well-known within the country, National Academy of Arts and Science, the Accademia dei Lincei, which means something like academy of the “eagle-eyed” (literally, lynx-eyed), that is, people that can see far. The Accademia dei XL is much less well known, although it has a distinguished 240-year history, during which people like Guglielmo Marconi and Enrico Fermi were members. More recently, the much beloved Rita Levi-Montalcini, Holocaust survivor, Nobel Laureate, and Senator-for-life, was a member. Current members include Nobel Laureates Carlo Rubbia and Giorgio Parisi. Noted algebraist Corrado De Concini is the current president.
Be that as it may, the academicians did vote to make me a member, their first computer scientist ever. Next week, at the inauguration of their 240th academic year, I will speak to the other members about randomness and pseudorandomness in computation.
A reminder that I am recruiting for two postdoc positions in my group, and that the strict application deadline is this Friday, December 17. See this previous post for details: https://lucatrevisan.wordpress.com/2021/10/21/postdoc-positions/
This is the seventh in a series of posts on online optimization, where we alternate one post explaining a result from the theory of online convex optimization and one post explaining an “application” in computational complexity or combinatorics. The first two posts were about the technique of Multiplicative Weights Updates and its application to “derandomizing” probabilistic arguments based on combining a Chernoff bound and a union bound. The third and fourth post were about the Follow-the-Regularized-Leader framework, which unifies multiplicative weights and gradient descent, and a “gradient descent view” of the Frieze-Kannan Weak Regularity Lemma. The fifth and sixth post were about the constrained version of the Follow-the-Regularized-Leader framework, and the Impagliazzo Hard-Core Set Lemma. Today we shall see the technique of Matrix Multiplicative Weights Updates.
1. Matrix Multiplicative Weights Update
In this post we consider the following generalization, introduced and studied by Arora and Kale, of the “learning from expert advice” setting and the multiplicative weights update method. In the “experts” model, we have a repeated game in which, at each time step , we have the option of following the advice of one of experts; if we follow the advice of expert at time , we incur a loss of , which is unknown to us (although, at time we know the loss functions ). We are allowed to choose a probabilistic strategy, whereby we follow the advice of expert with probability , so that our expected loss at time is .
In the matrix version, instead of choosing an expert we are allowed to choose a unit -dimensional vector , and the loss incurred in choosing the vector is , where is an unknown symmetric matrix. We are also allowed to choose a probabilistic strategy, so that with probability we choose the unit vector , and we incur the expected loss
The call is out for two postdoctoral positions at Bocconi to work in my group (see below for how to apply). If you are interested and you have any questions, feel free to email me (L.Trevisan at Unibocconi dot it)
The negotiable start date is September 1st, 2022. Each position is for one year, renewable for a second. The positions offer an internationally competitive salary (up to 65,000 Euro per year, tax-free, plus relocation assistance and travel allowance), in a wonderful location that, at long last, is back to more or less normal life. The application deadline is December 17, 2021.
Among the topics that I am interested in are spectral graph theory, average-case complexity, “applications” of semidefinite programming, random processes on networks, approximation algorithms, pseudorandomness and combinatorial constructions.
Bocconi Computer Science is building up a theory group: besides me, we have Alon Rosen, Marek Elias, a tenured person that will join next Fall, and more hires are on the horizon. Now that traveling is ok again, and considering that Alon and I both have ERC grants, we should expect a big stream of theory visitors coming and going through Bocconi from week-long visits to semester or year long sabbaticals.
To apply, go to https://www.unibocconi.eu/faculty-postdoc and look for the position advertised as “BIDSA Informatics”, which looks like this:
and click on “apply online”. Currently it is the second position from the top in the list
(This is the sixth in a series of posts on online optimization techniques and their “applications” to complexity theory, combinatorics and pseudorandomness. The plan for this series of posts is to alternate one post explaining a result from the theory of online convex optimization and one post explaining an “application.” The first two posts were about the technique of multiplicative weight updates and its application to “derandomizing” probabilistic arguments based on combining a Chernoff bound and a union bound. The third and fourth post were about the Follow-the-Regularized-Leader framework, and how it unifies multiplicative weights and gradient descent, and a “gradient descent view” of the Frieze-Kannan Weak Regularity Lemma. The fifth post was about the constrained version of the Follow-the-Regularized-Leader framework, and today we shall see how to apply that to a proof of the Impagliazzo Hard-Core Lemma.)
Today I would like to discuss the Khot-Naor approximation algorithm for the 3-XOR problem, and an open question related to it.
Continuing from the previous post, we are going to prove the following result: let be a -regular Cayley graph of an Abelian group, be the normalized edge expansion of , be the value of the ARV semidefinite programming relaxation of sparsest cut on (we will define it below), and be the second smallest normalized Laplacian eigenvalue of . Then we have
As life is tentatively returning to normal, I would like to once again post technical material here. Before returning to online optimization, I would like to start with something from 2015 that we never wrote up properly, that has to do with graph curvature and with Buser inequalities in graphs.
In the second week of July, 2022, there will be a summer school on algorithmic fairness at IPAM, on the UCLA campus, with Cynthia Dwork and Guy Rothblum among the lecturers. Applications (see the above link) are due by March 11, 2022.
We will soon put up a call for nominations for the test of time award to be given at FOCS 2021 (which will take place in Boulder, Colorado, in early 2022). There are three award categories, recognizing, respectively, papers from FOCS 2011, FOCS 2001, and FOCS 1991. In each category, it is also possible to nominate older papers, up to four years before the target conference. For example, for the thirty-year category, it is possible to nominate papers from FOCS 1987, FOCS 1988, FOCS 1989, FOCS 1990, in addition to the target conference FOCS 1991.
Nominations should be sent by October 31, 2021 to email@example.com with a subject line of “FOCS Test of Time Award”. Nominations should contain an explanation of the impact of the nominated paper(s), including references to follow-on work. Self-nominations are discouraged.
In the second week of November, 2021, the Simons Institute will host a workshop on using cryptographic assumptions to prove average-case hardness of problems in high-dimensional statistics. This is such a new topic that the goal of the workshop will be more to explore new directions than to review known results, and we (think that we have) already invited all the authors of recent published work of this type. If you have proved results of this type, and you have not been invited (perhaps because your results are still unpublished?) and you would like to participate in the workshop, there is still space in the schedule so feel free to contact me or one of the other organizers. For both speakers and attendees, physical participation is preferred, but remote participation will be possible.