# Workshop in Milan Next Week

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:

• where: Bocconi University’s Roentgen Building (via Roentgen 1, Milano), Room AS01
• when: June 15-18
• what: talks on cryptography and graph algorithms, including two hours devoted to Max Flow in nearly-linear time

# The First XL Computer Scientist

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.

# Online Optimization Post 7: Matrix Multiplicative Weights Update

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 ${t}$, we have the option of following the advice of one of ${n}$ experts; if we follow the advice of expert ${i}$ at time ${t}$, we incur a loss of ${\ell_t (i)}$, which is unknown to us (although, at time ${t}$ we know the loss functions ${\ell_1(\cdot),\ldots,\ell_{t-1}(\cdot)}$). We are allowed to choose a probabilistic strategy, whereby we follow the advice of expert ${i}$ with probability ${x_t(i)}$, so that our expected loss at time ${t}$ is ${\sum_{i=1}^n x_t(i) \ell_t(i)}$.

In the matrix version, instead of choosing an expert ${i}$ we are allowed to choose a unit ${n}$-dimensional vector ${v_t}$, and the loss incurred in choosing the vector ${v_t}$ is ${v_t ^T L_t v_t}$, where ${L_t}$ is an unknown symmetric ${n\times n}$ matrix. We are also allowed to choose a probabilistic strategy, so that with probability ${x_t(j)}$ we choose the unit vector ${v_t^{(j)}}$, and we incur the expected loss

$\displaystyle \sum_j x_t (j) \cdot (v_t^{(j)})^T L_t v_t^{(j)}$

# Postdoc Positions

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

# Online Optimization Post 6: The Impagliazzo Hard-Core Set Lemma

(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.)

# The Khot-Naor Approximation Algorithm for 3-XOR

Today I would like to discuss the Khot-Naor approximation algorithm for the 3-XOR problem, and an open question related to it.

# ARV on Abelian Cayley Graphs

Continuing from the previous post, we are going to prove the following result: let ${G}$ be a ${d}$-regular Cayley graph of an Abelian group, ${\phi(G)}$ be the normalized edge expansion of ${G}$, ${ARV(G)}$ be the value of the ARV semidefinite programming relaxation of sparsest cut on ${G}$ (we will define it below), and ${\lambda_2(G)}$ be the second smallest normalized Laplacian eigenvalue of ${G}$. Then we have

$\displaystyle \lambda_2 (G) \leq O(d) \cdot (ARV (G))^2 \ \ \ \ \ (1)$

which, together with the fact that ${ARV(G) \leq 2 \phi(G)}$ and ${\phi(G) \leq \sqrt{2 \lambda_2}}$, implies the Buser inequality

$\displaystyle \lambda_2 (G) \leq O(d) \cdot \phi^2 (G) \ \ \ \ \ (2)$

and the approximation bound

$\displaystyle \phi(G) \leq O(\sqrt d) \cdot ARV(G) \ \ \ \ \ (3)$

The proof of (1), due to Shayan Oveis Gharan and myself, is very similar to the proof by Bauer et al. of (2).

# Buser Inequalities in Graphs

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.

# A Couple of Announcements

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 focs.tot.2021@gmail.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.