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.

STOC 2022, and other theory events

Below is the call for participation to STOC 2022, which will take place in Rome in the third week of June.

If you would like to come to Italy a few days in advance, Alon Rosen and I are organizing two co-locating workshops on graph algorithms and on cryptography in Milan on June 15-18 (details forthcoming). If you want to stay longer, I am organizing a mini-workshop on fairness in AI in Milan on June 27 (more details about it in a few days). Registration will be free for both events. There are several high-speed trains every day between Rome and Milan, taking about 3 hours.


Call for Participation 

54th ACM Symposium on Theory of Computing (STOC 2022) – Theory Fest 

June 20-24, 2022 

Rome, Italy 

The 54th ACM Symposium on Theory of Computing (STOC 2022) is sponsored by the ACM Special Interest Group on Algorithms and Computation Theory and will be held in Rome, Italy, Monday June 20 – Friday, June 24, 2022.

STOC 2022 – Theory Fest will feature technical talk sessions, 6 workshops with introductory tutorials, poster sessions, social events, and a special joint session with “Accademia Nazionale dei Lincei”, the oldest and most prestigious Italian academic institution, followed by a reception and a concert at the Academy historic site

Registration

STOC 2022 registration is available here.

Early registration deadline: April 30th. 

STOC 2022 is sponsored by Algorand, Amazon, Apple, Google, IOHK, Microsoft, Sapienza University of Rome. 

Renato Capocelli (1940-1992)

Thirty years ago, I was in the middle of the second semester of my third year of undergrad, and one of the courses that I was enrolled in was on information theory. I was majoring in computer science, a major that had just been established at Sapienza University when I signed up for it in 1989, organized by a computer science department that had also just been established in 1989. A computer science department was established in 1991.

The new Sapienza computer science department was founded mostly by faculty from the Sapienza mathematics department, plus a number of people that came from other places to help start it. Among the latter, Renato Capocelli had moved to Rome from the University of Salerno, where he had been department chair of computer science.

Capocelli worked on combinatorics and information theory. In the early 90s, he had also become interested in the then-new area of zero-knowledge proofs.

Capocelli taught the information-theory course that I was attending, and it was a very different experience from the classes I had attended up to that point. To get the new major started, several professors were teaching classes outside their area, sticking close to their notes. Those teaching mathematical classes, were experts but were not deviating from the definition-theorem-proof script. Capocelli had an infectious passion for his subject, took his time to make us gain an intuitive understanding of the concepts of information theory, was full of examples and anecdotes, and always emphasized the high-level idea of the proofs.

I subsequently met several other charismatic and inspiring computer scientists and mathematicians, though Capocelli had a very different personality from most of them. He was like an earlier generation of Southern Italian intellectuals, who could be passionate about their subject in a peculiarly non-nerdy way, loving it the way one may love food, people, nature, or a full life in general.

On April 8, 1992, Renato Capocelli died suddenly and unexpectedly, though his memory lives on in the many people he inspired. The Computer Science department of the University of Salerno was named after him for a period of time.

This Year, for Lent, Bocconi Gave Up Not Having a CS Department

Yesterday, Bocconi’s Rector signed the decree that created the new Computing Sciences department. This is only the ninth department to be created in our 120 year old university, and the first, I believe, in a couple of decades. It is the first department with an engineering and science mission (the other eight department are, in random order, Accounting, Marketing, Finance, Economics, Managements, Social Sciences, Law, and Decision Sciences).

A few weeks ago, we were joined by Francesca Buffa and Marc Mezard.

Francesca, a computational biologist formerly at Oxford medical school, is now the fourth out of four computer science tenured faculty in our new department to have an active ERC grant.

Marc’s work has spanned theoretical physics, information theory and computation, including his collaboration with Giorgio Parisi’s Nobel Prize winning work, and he has been most recently the president of the Ecole National Superieure in Paris. When we asked for letters for his tenure case, one of the reviewers wrote, more or less in so many words, “you would be lucky to have Marc in your university, though it’s very unlikely that he will accept your offer”. At that point Marc had already accepted.

Bocconi is hiring Assistant Professors of Computer Science

Bocconi University is recruiting for tenure-track positions in computer science.

Some details are here. Candidates must apply online by January 15 (end of day Central Europe time) for the application to be considered. To apply online, go to https://jobmarket.unibocconi.eu/ and look at the only opening that has a Jan 15 expiration (currently it is at the top of the list). The negotiable start date is September, 2022. By that time the new Computing Sciences department will be fully operational.

We are interested in all areas of computer science. Alon Rosen, Dirk Hovy and I are very happy to talk to prospective candidates about what the university is like and what are its plans for developing computer science.

The university pays internationally competitive salary and provides relocation assistance. The language of instructions of all computer science courses at both undergraduate and graduate levels is English.

Scholars of any nationality who have not lived in Italy for the past two years and who move to Italy to take a university tenure-track or tenured position pay almost no income tax for six years, or more if they buy a home in Italy and/or have children under the age of 18.

For Italians working in Italy: this position is governed by a private-law contract with Bocconi, which is not the same as a RDTA or RDTB position, although the terms are similar.

Subject to a successful mid-term review (which usually happens after three years), and a successful tenure review (which happens within five years from the mid-term review, or possibly earlier depending on the background of the candidate), assistant professors are promoted to associate professors with tenure. (For those familiar with the Italian system, the latter positions are fully recognized as professore associato by the ministry of university.)

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)}

Continue reading

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

Continue reading