in theory

The FOCS test of time award recognizes each year a paper, or papers, each from the FOCS conference of 10, 20, and 30 years earlier for the impact they have had on theoretical computer science.

It is an important occasion to appreciate the work that has had a long term impact on our field and that, for the 30 year old papers, maybe is not even cited any more and has turned into a “it is well known that…”

If your work has been significantly affected by a great paper appeared in FOCS 2014, FOCS 2004, or FOCS 1994, and the paper fits the nomination criteria, it is a valuable contribution to the community to nominate it.

Here is the call for nominations.

For the Italy-based readers and others that are able to make it to Milan on short notice, I would like to publicize that next week, in Bocconi, there will be a very exciting interdisciplinary workshop on average-case problems from several perspectives: (1) evidence for and against the existence of efficient algorithms in different regimes coming from statistical physics, (2) the evidence for and against the existence of efficient algorithms in different regimes coming from convex optimization techniques, (3) strong evidence of hardness coming from worst-case to averarge-case reductions, (4) applications to cryptography.

On May 31, we are going to hold a Theory Day with a very diverse range of talks by an excellent collection of invited speakers, which includes Cynthia Dwork.

Participation is free for both events, but registration is required.

A question that I am very interested in is whether it is possible to study hypergraphs with techniques that are in the spirit of spectral graph theory.

It is generally possible to “flatten” the adjacency tensor of a hypergraph into a matrix, especially if the hypergraph is -uniform with even, and spectral properties of this matrix give information about the hypergraph, but usually a large amount of information is lost in this process, and the approach can only be applied to rather dense hypergraphs.

If we have a 4-uniform hypergraph with vertices, for example, meaning a hypergraph in which each hyperedge is a set of four elements, its adjacency tensor can be flattened to a matrix. Unless the hypergraph has a number of hyperedges that is at least quadratic in , however, such a matrix is too sparse to provide any useful information via basic spectral techniques.

Recently, a number of results of a “spectral hypergraph theory” flavor have appeared that, instead, apply spectral graph theory techniques to the Kikuchi graph associated to a hypergraph, leading to very impressive applications such as new lower bounds for locally correctable codes.

In this post I would like to show a simple but rather magical use of this approach, that gives a proof of Feige’s conjecture concerning a “Moore bound for hypergraphs”.

In an undirected graph, the girth is the length of the shortest simple cycle, and in the previous post we told the story of trade-offs between density of the graph and girth, such as the Moore bound.

In a hypergraph, an interesting analog to the notion of girth is the size of the smallest even cover, where an even cover is a set of hyperedges such that every vertex belongs to an even number of hyperedges in the set. The reader should spend a minute to verify that if the hypergraph is a graph, this definition is indeed equivalent to the girth of the graph.

To see why this is a useful property, the hyperedges of a -uniform hypergraph with vertex set V can be represented as vectors in in a standard way: a vector represents the set . Under this representation, an even cover is a collection of hyperedges whose corresponding vectors have a linear dependency, so a -uniform hypergraph with vertices, hyperedges and such that there is no even cover of size corresponds to a construction of vectors in , each of Hamming weight , such that any of them are linearly independent. Having large collections of sparse vectors that don’t have small linear dependencies is useful in several applications.

It is easy to study the size of even covers in random hypergraphs, and a number of results about CSP refutations and SoS lower bounds rely on such calculations. Feige made the following worst-case conjecture:

Conjecture 1 (Moore Bound for Hypergraphs) If a -uniform hypergraph has vertices and hyperedges, then there must exist an even cover of size

Where the “tilde” hides a polylogn multiplicative factor. For , for example, the conjecture asserts that a hypergraph with vertices and hyperedges must contain an even cover of size . For , the bound is .

The Feige conjecture was recently proved by Guruswami, Kothari and Manohar using Kikuchi graphs and their associated matrices. In this post, we will see a simplified proof by Hsieh, Kothari and Mohanty (we will only see the even case, which is much easier to analyze, and we will not prove the case of odd , which is considerably more difficult).

1. A spectral proof of the Moore bound in graphs

We will first provide a spectral proof of the Moore bound for graphs, and then we will use Kikuchi graphs/matrices to lift the argument to hypergraphs.

To see how to use spectral arguments to reason about girth, let us start from the simple case of -regular graphs. We want to reason about cycles in a graph, and a spectral concept immediately comes to mind: if is the adjacency matrix of the graph, then is the number of closed walks of length in the graph. If the girth of is more than , then none of those closed walks can be, or contain, a cycle, and this restricts how many such walks can exist. All such walks happen within the local tree that surrounds the start node, and the walk can just traverse part of this local tree. Combining these observations suffices to obtain a non-trivial bound.

First of all, if a graph is -regular, we have and so

and we claim that if the girth is more than we also have

This is because a closed walk of even length , provided that is less than the girth, can be specified by indicating the starting node, of which there are , then for every step of the walk whether we are moving one step closer or one step further from the starting node in the local tree around the node, for which we have choices to enumerate, and, finally, for the steps in which we move one step further, which edge we follow, for which we have choices. When we move closer to the start node, only one edge can be followed and there are no choices to enumerate.

Combining the bounds and taking -th roots, we have , which gives the weak but respectable Moore-like bound

The next step is to make such an argument work for irregular graphs. We would again like to reason in terms of the trace of the power of a matrix, to relate it to counting closed walks, and to show that the count is small if the girth is large. We will need, however, to find the proper normalization, because we cannot use just the adjacency matrix any more.

If is the adjacency matrix of an irregular graph of average degree and is the diagonal matrix of degrees of , so that is the degree of vertex , a common normalization is to look at the matrix , or to the symmetric matrix , which has the same trace and eigenvalues. This is also the transition matrix of the random walk in , so that when we study the trace of powers of this matrix we end up considering the probability that a random walk of a certain length returns to the start vertex. We also know that

so that for every

If we try to analyze the trace of powers of this matrix, however, we run into some technical difficulties, that are greatly simplified by a neat trick which is not totally natural and that I will try to justify.

Let us think about the regular case as analyzed above, except that we work with for consistency. The division by contributes a term to the trace of the -th power, so we “gain” a factor of in each step. We lose it almost entirely when we do a step away from the start node, because we have to account for choices, but we gain it entirely when we take a step closer to the start node, because that is a forced move for which we do not need to enumerate choices. We end up gaining a factor of for each backward step, of which there are , and so we can cleanly say that the trace goes down by a factor of . We pay for the choice of the start vertex and for the choice of when to go forward and when to backward, and the overall bound is which becomes when we take the -th root.

The difficulty in replicating this argument with the same cleanliness in the irregular case is that, when we are enumerating what can happen when the closed walk passes through a vertex , the gain from a backward step from is , which could be much larger than , and it is not straightforward how to “average” things, because we are multiplying terms that are not independent.

It would certainly be very convenient if the normalization in a step from vertex was such that we always gain a factor that is both smaller than , to have a proper account of the backward steps, and smaller than to account for the possible forward steps.

The trick is simply to enforce that with a different normalization: instead of working with or , we define and work with and . With this normalization, a step backward from contributes which is certainly less than while the enumeration of steps forward can still not exceed a contribution of 1.

The only concern about this new normalization is that we divide by a larger matrix and this could cause its norm to drop too much, but fortunately the norm is essentially preserved, as we can see by using the test vector .

We have that the quadratic form is

while the norm squared of the test vector is

so that we have a good lower bound on the norm

To bound the trace of our normalized matrix, we perform a similar enumeration as the one we did in the regular case. We have to enumerate all closed walks where and the edge exists for . We have choices for the start vertex and then choices for whether, at each step, we move one step closer to the start vertex in the local tree, in a unique way, or one step forward, in one of possible ways. We will denote by the set containing the unique neighbor of that is one step closer to the start vertex in the local tree of the start vertex, and by the set containing the neighbors of that are one step further. If represents the binary choice of whether to move further or closer to the start vertex in the walk from node , then is the set of choices that we have to enumerate.

With this notation we can write the trace as

In order to bound the above expression, we see that we have choices for , then choices for , and for each of the steps from a vertex in which we go backward we have a term which is ; for each of the steps from a vertex in which we go forward we have branches, but each multiplied by so that the total contribution is less than 1.

Overall we can say

so that rearranging and taking -th roots we have

that is also equivalent to

which is again a respectable Moore-like bound for irregular graphs.

A final note about this spectral argument is that can still be seen as the transition matrix of a sort of random walk, that is, one that from has a probability of stopping, and probability of proceeding through each neighbor of . The trace of the -th power of computes, up to a factor of , the collision probability of the distribution of the -th step of this walk starting from a random vertex, and the negative logarithm of this probability is called the Renyi entropy of the distribution. This is all to say that this spectral argument is not totally unrelated to the argument in the previous post, in which we computed the entropy of a non-backtracking random walk started at a random vertex.

2. Kikuchi matrices and hypergraphs

We now come to the magic of this post, where we define Kikuchi graphs and associated matrices, and we see how to transfer spectral graph theory techniques to hypergraphs.

If is a -uniform hypergraph with vertices, even, and if we select an integer parameter , the Kikuchi graph associated to and is a graph with vertices defined as follows. We think of each vertex of as a set of vertices of ; if is a hyperedge of , then for every set of vertices we have the edge in , where we use to denote symmetric difference between sets. In other words, the edges of are the pairs of sets of vertices of whose symmetric difference is a hyperedge of .

This feels a lot like a Cayley graph, and in fact it can be seen as a vertex-induced subgraph of a Cayley graph, but this would not give a very enlightening perspective on the content of this post, so we will not pursue this concept furhter.

Necessarily, in an edge of the Kikuchi graph corresponding to an hyperedge , the sets and must each contain vertices of each, and so the construction as described only works for hypergraphs where the hyperedge cardinality is even. We already mentioned that everything becomes considerably more complex in the odd case, which we will not deal with.

For each hyperedge of , there are choices of a set containing vertices of of which are from . Overall, if has hyperedges, is going to have

undirected edges (the factor of 2 comes from the fact that without it we would count and as two different edges while it is the same undirected edge).

If , then the Kikuchi graph construction is analogous to the standard “flattening” of a tensor to a matrix or of a hypergraph to a graph, and it is not immediately clear from the definitions what is gained by choosing a larger and obtaining a larger graph that only seems more redundant and more complex to analyze.

An important gain is that for larger the resulting graph is denser. Indeed the average degree of the Kikuchi graph is

and one can see that for and the bound

holds, showing how larger choices of yield denser graphs.

What about even covers and Feige’s conjecture? Suppose does not have even covers of size , and let us look at a length- closed walk in , where and the edges exist in for each step of the walk. Let us call the hyperedge of corresponding to the edge , so that we have . The key observation is that, iterating the definitions of the edges we have

but we also have and so

From the multiset of hyperedges let us repeatedly remove pairs of identical hyperedges: this process will terminate either with a set of hyperedges occurring each once, or with an empty collection of hyperedges. The former case cannot happen, however, because this set of hyperedges would be a double cover of cadinality less than , so the process must terminate with an empty set, meaning that the multiset is such that every hyperedge occurs an even number of times.

Maybe it is not clear where we are going with this, but we have made all the key observations to be ready to prove the Feige conjecture, because we have related lack of even covers in the hypergraph with restricted properties of closed walks in the associated Kikuchi graph, and we already have spectral techniques that can be applied when we understand restrictions on closed walks in a graph.

3. Proof of the Feige Conjecture

The Feige conjecture will follow from the bounds formalized below:

Lemma 1 (Main) Let be an order , even, hypergraph with vertices and edges. Suppose that there is no even cover of size in . Construct the Kikuchi graph of with parameter , where . Let be the adjacency matrix of , let be its diagonal matrix of degrees, let be the average degree of , define . Then

We already proved the first two inequalities. To deal with the last one we will enumerate the closed walks of length in .

To enumerate all length- closed walks with , we call the hyperedge associated to the edge , and we again associate a vector to each walk, but this time when the hyperedge is old, meaning it has already appeared in the sequence as some with . We let if the hyperedge is new, meaning that it appears for the first time in the sequence .

Note that now the Kikuchi graph does not necessarily have large girth: for example it is easy to see that it has a lot of length-4 cycles. From the discussion in the previous section, however, we know that the sequence is such that every hyperedge that appears in the sequence appears an even number of times and, in particular, the sequence involves at most distinct hyperedges. This will be enough to obtain the claimed upper bound on the trace.

Analogously with the notation used in the previous section, We let be the set of neighbors of that are possible as a next step of the closed walk assuming that the step corresponds to an old hyperedge and the set of neighbors of that are possible as a next step of the closed walk assuming that the step corresponds to a new hyperedge.

With this notation, we can write the trace as

We have choices for and choices for . For each step of the walk, if and the step uses an old hyperedge, then has at most possibilities, corresponding to hyperedges that have been seen so far in the walk and that can be repeated. Each choice contributes a value of , for a total contribution that is at most . Because all hyperedges that are used in the walk are used an even number of times, there have to be at least steps in which we have an old hyperedge. When and we have a new hyperedge at step , then can be at most the set of all neighbors of , and each contributes a value of so that the total contribution is less than one. This proves the claimed upper bound

and establishes the Main Lemma.

After taking -th roots, the Main Lemma says that

We instantiate the construction to

which makes , so that the Main Lemma implies . Recall that we also proved

which combines to

or, equivalently, we have proved the upper bound

provided that there is no even cover of size , which is precisely the Feige conjecture.

Without all the commentary that we added, the even case of the Feige conjecture, already a significant problem that had been open and challenging for a while, is solved in half a page of simple calculations. The magic of the Kikuchi graph comes in the very simple way that even covers in the hypergraph translate to restrictions to what closed walks can look like in the associated graph, and these are restrictions that are usefully exploitable in trace arguments.

As we remarked, something else that is also very useful in the connection is that the size of the sets corresponding to vertices in the Kikuchi graph is a parameter that we can control, and it “densifies” the graph the more it is turned up.

The odd case is considerably more involved, and it is where all the major work is done, though the even case already gives a glimpse of the power of these techniques.

I would like to remark that several technical steps above are taken verbatim from the paper of Hsieh, Kothari and Mohanty, as they are already as simplified and clear as they can be. I want to thank Lucas Pesenti for having explained this proof to me.

Guruswami, Kothari and Manohar recently solved a conjecture of Feige about even covers in hypergraphs, with beautiful techniques that have several applications. I would like to describe some of their ideas in a subsequent post or series of posts.

Feige’s conjecture is about an hypergraph analog of the question of how big can the girth of a graph be relative to its density, and I would like to start by sharing a “proof from the book” about the latter problem.

In an undirected graph, the girth is the length of the shortest simple cycle. If a graph has odd girth , and we perform a BFS in it starting from any vertex, and we stop it after no more than hops, then we are guaranteed to keep finding new vertices at every step of the exploration: if we had two paths of length at most from the same source to the same destination we would actually have a cycle of length . If the graph is -regular, this means that, in this truncated BFS, we see at least

different vertices (because what we are seeing are the first levels of a complete -ary tree). There is a similar expression for even .

This remarkable property of high-girth graphs to look “locally tree-like” is very interesting and it is useful in certain applications, but it clearly puts a trade-off between the number nodes and the number of edges in high-girth regular graphs. Obviously, the total number of vertices of the graph has to be at least the bound (1), meaning that if is the number of vertices and is the degree then the girth can be at most something like .

There are lots of questions about existence and constructions of high-girth graphs, and about the tightness of the above bound, but another really good question, raised by Bollobas, is what happens in irregular undirected graphs. Does a lower bound like (1), which is called the Moore bound, hold in irregular graphs, if we replace the regular degree by the average degree ? It took about 30 years for this question to be positively resolved by Alon, Hoory and Linial.

A simplified proof was then found by Babu and Radhakrishnan, with an information-theoretic approach. I will try to explain how one might have conceived and developed the latter proof. I want to thank Lucas Pesenti for explaining the proof to me.

We have an undirected graph with vertices and edges, where is the average degree, the girth is an odd number , and we would like to say that is large, for the same reason why this is true in the regular case: if we start from any vertex and explore using BFS up to distance , we always discover new vertices at each iteration, the average vertex has degree and, although we cannot say that all these local trees are big, maybe there needs to be some local tree that is big, with a size of the order of .

All the interesting part of the argument (the rest is just a few lines) is already there in proving that there is a tree whose number of leaves is at least

where we just aim to match the number of nodes in the last level of the regular case, and we will focus on this slightly restricted goal.

Let’s put ourselves in an optimistic state of mind and imagine what a reasonably simple proof of such a fact might look like. Maybe actually the average local tree, starting from a random root vertex, is large, and at least as large as if the graph was regular (in the reular case all the local trees are identical copies of truncated complete -ary trees and the average size is just the size, which is the Moore bound). The average size of a local tree of depth rooted at a random vertex is a complicated expression of the degree distribution of the graph, but if it needs to be at least as large as the (achievable) case in which the degrees are all equal, it sounds like we would like to write, or lower bound, the average in terms of a concave function of the degree distribution, so that the bound in terms of the regular case would fall from convexity inequalities.

At this point the idea might come that somehow we should think about entropy and not cardinality, because the former can be used to give a lower bound for the latter, it has nice convexity properties, and it might work better in a probabilistic setting. So the goal might be to take a random start vertex , consider the distribution of a random node at distance from , and then say that the entropy of this distribution (averaged over the choices of ), needs to be at least .

This view has the additional advantage that now, instead of talking about a random local tree, which is a fairly messy object, we are talking about simply picking a random vertex and then a random path of length from , where we call the destination of the path .

In defining this probabilistic process correctly, however, we have to be careful not to think of this path as being generated as a random walk, because a random walk can go back, and loop, and it is not guaranteed to be a simple path, the way paths in BFS trees are.

We can use, instead, the non-backtracking random walk process. In an undirected graph , the non-backtracking random walk is the probabilistic process where, at every step, we keep track of the vertex where we are and the vertex where we were at the previous step, and, for the next step, we choose a new vertex among the neighbors of except for . The vertex becomes the new “previous vertex” and so on.

This means that the states of the walk are the ordered pairs of vertices joined by an edge, of which there are . The transition rules are that we have transitions of the form , where are pairs of edges of with a vertex in common, and such a transition happens with probability , where we use the denote the degree of a vertex .

Notice that if you start a non-backtracking random walk at the root of a tree, the walk will move forward to a random child, then a random child of the random child, until it reaches a leaf and gets stuck. If you do an -step non-backtracking random walk in a graph that has girth , then you will explore a random path and reach a random leaf in one of the local trees that we are interested in, so this is indeed the process that we want.

A final consideration, that is standard in this setting, is that, if we select the start vertex of a non-backtracking walk with probability proportional to its degree, then every step of the walk traverses a uniformly distributed edge, and, at every step, the “current vertex” remains distributed with probability proportional to its degree: these are very convenient conditions to work with.

At this point, we have all the pieces of what could be a proof: we have our undirected irregular graph with vertices of average degree and girth , we consider the process of picking a random start vertex with probability proportional to its degree, we perform an -step non-backtracking random walk , and we would like to say that the expectation over of the entropy of given is at least . We will now prove that and we will interleave the chain of equalities and inequalities with explanations:

because the setup is such that there is only one path of length from to

by the Chain Rule

because the distribution of vertex given the previous vertices is just the uniform distribution of the neighbors of with the exception of , so it is a uniform distribution over possibilities, whose entropy is clearly . The expectation is over the process of selecting the walk. Recall that the walk process is such that, at each step, the “current vertex” always has the same distribution, so, calling the distribution over vertices in which a vertex of the graph is sampled with probability proportional to its degee, the above expression is

where we used linearity of expectation to collect terms under one sign of expectation. Indeed we can now use convexity to get a bound in terms of the regular case. Maybe there is another way that is a bit more transparent, but, following Babu-Radhakrishnan, we open up the expectation and apply Jensen to the convex function , and we have

Success!

I really like the heuristic of thinking about what the cleanest possible approach to a proof would be, make some optimistic assumptions which if true would simplify things, and see where it goes. It almost never works, but it can rarely lead to very nice outcomes.

In terms of the history of this particular result, I think that the proof of Alon et al. is already based on getting to a concave expression so that one establishes a lower bound in terms of the regular case, but it is developed fully combinatorially. The proof of Babu and Radhakrishnan is in some sense mathematically the same, but they recognized that the information-theoretic language simplifies everything quite a lot.

This September, Bocconi will start a new M.Sc. in Artificial Intelligence. It will be a two-year computer science degree meant for students with Bachelor degrees in computer science, engineering, math, statistics, physics and related quantitative fields.

In the first year, courses on algorithms, mathematical methods, optimization, information theory, and software engineering will build a foundation in math and CS, then courses on deep learning, reinforcement learning, natural language processing and computer vision and image processing will go in depth on machine learning and some of its applications. In the second year there are various options and elective courses, with the possibility to study, for example, cryptography and blockchains, or bio-medical applications. As common for the second year of Bocconi’s M.Sc. degrees, there will be options for exchange programs to spend a semester abroad. Students also take a seminar on ethics in AI, a project-oriented AI lab, and a foreign language (not English and not the student’s native language) course. The language of instruction is English.

Tomorrow at 5pm CET there will be an online information session: those interested can sign up here.

More information about the degree are at www.unibocconi.eu/ai-msc.

Applications open today and are due by May 25th.

I am looking for three postdoctoral fellows for the next academic year to work with me at Bocconi.

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. The strict application deadline is January 31, 2023. Each position is for one year, renewable to a second year.

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.

Please contact me if you are interested in these positions and you would like more information.

To apply, go to this link, and then look for the opening for 3 positions dated December 6, 2022, like the one below (unfortunately there isn’t a perma-link to the application form):

Bocconi’s Computing Sciences department has a sizable theory group, that includes Laura Sanità, who works on optimization and approximation algorithms, Alon Rosen, who works on the foundations of cryptography, Marek Elias, who works on online optimization, and Andrea Celli, who works on algorithmic game theory. Next year, Adam Polak who works on fine-grained complexity and analysis of algorithms, will also join us.

Speaking of Alon Rosen, he is also recruiting postdocs for the next academic year, and he has two open positions, that you can find at the same link looking for two positions dated December 14 with an application deadline of February 28:

Next Monday, June 27, I am organizing a workshop on issues around fairness, bias and discrimination in AI and Machine Learning.

Here is a link to the program. Remote participation is possible (link in the website), and in-person participation is free but we ask people to register so we can print badges and order the appropriate number of coffee breaks.

This workshop is being organized in partnership with EDGE, an Italian NGO that works on LGBT rights, and it is the first event of their initiative “A+I: Algoritmi + Inclusivi”, which will feature an awareness campaign and a series of video interviews that will start after the summer.

In next week’s workshop, Oreste Pollicino from Bocconi will talk about the perspective of the legal community around algorithmic discrimination, Symeon Papadopoulos from ITI Patras will give a survey on issues of fairness in image processing and image understanding, Sanghamitra Dutta from J.P. Morgan AI will talk about how to use the theory of causality to reason about fairness, Debora Nozza and Dirk Hovy from Bocconi will talk about issues of fairness in language models and natural language processing, and Omer Reingold from Stanford and Cynthia Dwork from Harvard will talk about modeling and achieving fairness in prediction models.

The last morning session will be a panel discussion moderated by Damiano Terziotti from EDGE about perspectives from the social sciences and from outside academia. It will feature, among others, Brando Benifei, a member of the EU parliament who has played a leading role in the 2021 draft EU regulations on AI. The other panel members are Alessandro Bonaita, who is a data science lead in Generali (Italy’s largest insurance company), Luisella Giani, who is leading a technology consulting branch of Oracle for Europe, Middle East and Africa, Cinzia Maiolini, who is in the national secretariat of CGIL, an Italian Union, and Massimo Airoldi from the University of Milan.

If you are in or near Milan next week, come to what is shaping up to be a memorable event!

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
• how: register for free

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.