Feige’s Conjecture and the Magic of Kikuchi Graphs

Posted on by
Reply

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

It is generally possible to “flatten” the adjacency tensor of a hypergraph into a matrix, especially if the hypergraph is {k}-uniform with {k} 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 {n} vertices, for example, meaning a hypergraph in which each hyperedge is a set of four elements, its {n \times n \times n \times n} adjacency tensor can be flattened to a {n^2 \times n^2} matrix, but unless the hypergraph has a number of hyperedges that is at least quadratic in {n} such a matrix is too sparse to provide any useful information with basic spectral techniques.

Recently, a number of impressive 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.

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 on 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 {k}-uniform hypergraph with vertex set V can be represented as vectors in {{\mathbb F}_2^V} in a standard way: a vector {x\in {\mathbb F}_2^V} represents the set {\{ v : x_v \neq 0 \}}. Under this representation, an even cover is a collection of hyperedges whose corresponding vectors have a linear dependency, so a {k}-uniform hypergraph with {n} vertices, {m} hyperedges and such that there is no even cover of size {\leq L} corresponds to a construction of {m} vectors in {{\mathbb F}_2^n}, each of Hamming weight {k}, such that any {L} 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:

If a {k}-uniform hypergraph has {n} vertices and {n\left( \frac{n}{r} \right) ^{\frac k2 -1}} hyperedges, then there must exist an even cover of size {\tilde O( r )} Where the “tilde” hides a polylogn multiplicative factor. For {k=3}, for example, the conjecture asserts that a hypergraph with {n} vertices and {m} hyperedges must contain an even cover of size {\tilde O(n^3/m^2)}. For {k=4}, the bound is {\tilde O(n^2/m)}.

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 {k} case, which is much easier to analyze, and we will not prove the case of odd {k}, which is considerably more difficult).

Continue reading →

The Moore Bound for Irregular Graphs

Posted on by
1

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 {g}, and we perform a BFS in it starting from any vertex, and we stop it after no more than {(g-1)/2} 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 {(g-1)/2} from the same source to the same destination we would actually have a cycle of length {g-1}. If the graph is {d}-regular, this means that, in this truncated BFS, we see at least

\displaystyle n \geq 1 + d \cdot \sum_{i = 0}^{\frac {g-1}2 -1} (d-1)^i \ \ \ \ \ (1)

different vertices (because what we are seeing are the first {\frac {g-1}2} levels of a complete {d}-ary tree). There is a similar expression for even {g}.

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 {n} is the number of vertices and {d} is the degree then the girth can be at most something like {2\log_{d-1} n}.

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 {d} by the average degree {\bar d = 2|E|/|V|}? 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.

Continue reading →

Introducing Bocconi’s new M.Sc. in Artificial Intelligence

Posted on by
1

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.

Postdoc Positions for 2023-24

Posted on by
1

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:

Workshop on Fairness in AI

Posted on by
2

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!

Workshop in Milan Next Week

Posted on by
3

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

The First XL Computer Scientist

Posted on by
6

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

Posted on by
2

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)

Posted on by
6

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.