During the heroic age of mathematical exploration (circa 3000 BCE — 2026 CE), mathematicians trailblazed through desolate, inhospitable lands by bare brainpower, carrying nothing except maybe chalk, paper, and pen. They were poor, unkempt, often begging for the meager funds they required. Yet most were happy to dedicate their lives to exploration, which for them was a lifestyle, like farming, and constantly occupied their minds. Sometimes at the cost of great personal sacrifices, they rushed through white deserts covered in chalk dust. They planted their tiny flags in spots undistinguished by anyone except themselves and a few travelers along the same route. They didn’t claim the land, and were happy to show the path ahead, just asking for a little recognition — which to our modern eyes looks childishly petty until we remember the conditions in which their discoveries were made. There have been many Amundsens, ruthlessly competitive and efficient, some Scotts, who alas paid the highest price for their discoveries, and a few Shackletons. In some museums you can still see today samples of their maps inked on paper.
On AI
Whoa! Overnight (i.e., during the course of a short summer) AI in theoretical research went from a toy to an indispensable tool, immeasurably speeding up research, including solving problems on its own. Now all the talk is the Math AI crisis, something which would have been unthinkable even last May. The people in the trades would be laughing their butts off, if they didn’t know better than following up what’s going on (they’re probably fishing, their Ford 250 truck with their company’s cute logo parked at the edge of the lake). What we thought quintessential human, creating art, math, thinking, it’s all done by machines which we fed with so many papers, movies, songs, conversations, that they got better than us. In the meantime, robotics is lagging behind and crimping a cable, scraping a siding, cutting pvc pipes still require the wear and tear of our bodies. Not even science fiction dystopia.
I consider what’s happening in AI the most exciting technology since the invention of computers. I don’t make this statement lightly. My two previous picks would be electricity and the telephone. I didn’t expect to see this in my lifetime, or even to ever happen. And I don’t know anyone who wasn’t shocked, except Ray Kurzweil: I met him last year and he told me: wait two months.
AI is disrupting academia. This is scary, but also the system wasn’t so good that a good shake isn’t necessarily for the best. Driven by cut-throat competition and the limitations of the human brain (as well as the general instability of the geopolitical landscape) academia became publish-or-perish, the unbearable pressure to push incremental papers, or to show off mathematical weight-lifting in the form of super-technical papers. Can we finally stop celebrating weight lifting? The goal has never been making things look complicated, but this was a target, and even specifically given as advice to young researchers (sad). There is now no point in this, given that AI can easily fill pages with integrals, and also to some extent simplify (though this is less clear, as it doesn’t seem AI has a good sense of what’s easy for us, understandably given it’s a machine and the awful training it was given). Your goal is to make things easy! But naturally things can also become worse. Before, you could write a paper from a remote region of the world and instantly get recognition. Today, this is to be evaluated under the lens of AI, which might actually end up making public relations even more critical for success in academia. Still, it may be that all “low-hanging AI fruits” are taken soon, and human contributions become more transparent. I tend to believe this will happen, basically for the reason that the math problems were outlined before AI and so it is natural that many fall under the new tool, while at the same time they cannot be produced by humans at a high rate. Hopefully we can also move away from incremental research and use AI to do something big, like progress in computational complexity theory, an area which still emerges relatively unscathed (in terms of big breakthroughs). Use all means at your disposal to solve P vs NP!
It’s palpable in the air the quest for guidance, principles. Many conferences have been set up in place before the revolution, and are now struggling to evaluate the onslaught of single-author AI-slob which would have appeared solid last May. This is no small problem, especially given the culture of conferences in computer science. You obviously don’t want to fill a conference with people who have no idea what they are talking about. Might be hi-time to rethink conferences… And there’s the fear of missing the next generation of scientists.
The excitement at this awesome new power at my disposal comes with a bitter, nostalgic feeling. I had arranged much of my life around working math in my head, since my teen age years when I would enjoy sitting in the sun, reading my calculus homework, then closing my eyes and solving it in the head. (I once got zero at an exam because I didn’t show the steps, my prof was however flexible enough to challenge me to repeat the feat in front of him, and then gave me full score.) This is not at all to say I’m particularly good at this sort of thing, but I enjoyed the feeling. In the last 30 years or so, I worked countless problems in my head, during walks, swims, bike rides. The problems never left me, at the doctor’s office, during parties, when everybody else was bored, when I was waiting in line, while traveling. At night I had to fight them off with utmost concentration so that I could sleep (the one big, big drawback). I was sometimes exhausted, sleepless, even nauseated with math, but I never felt bored. But there’s more, even when I wasn’t actively thinking, maybe resting or playing a videogame, I always had the intense background feeling that I was only doing that so that my brain would cool off and later be in a better position to produce math, a main metric I’ve been measuring my life by.
Now this seems all gone. Thinking without an AI companion appears pointless. I’ll be sitting in the woods and pull out my phone, or just talk, and understand one more line of the proof that AI generated. What will be missing forever is the feeling that all this had to happen entirely in my head, that there was no comparable tool, nothing else that could match what my own concentration could produce. This is what justified the endless videogaming, hikes, gazing through the window for hours, meditation, the endless fine tuning of my sleep, walks, food, so that at some point, even just for a brief but explosive moment, I could unleash my thought.
REVISITING THE XOR LEMMA
I have just posted this report, which contains two previous reports, the counterexample to the dream xor lemma and the simple proof using majority, together with a new proof which appears to improve the parameters of all previous proofs of the xor lemma. Specifically, if a function has correlation epsilon with circuits of size S, the xor of two copies has correlation about epsilon square with circuits of size about S times epsilon square. By contrast, it seems to me that all previous proofs lost at least epsilon to the four in circuit size, and some also had a dependence on N. This loss arose from the need to estimate the final correlation, as is evident, for example, in Levin’s proof. The proof with the hard core set incurs this loss for similar reasons.
The new proof in the report does not do this estimate. Instead, it uses an object which I call BMA for bounded mean amplifier. It is a function that, given iid variables with a small mean returns a variable whose mean is amplified. Majority is a decent BMA but doesn’t quite get to the square of the correlation. A randomized variant of majority does get you that. The function is very similar to what’s used, for example, in Levin’s proof and, I’m sure, in many other places, but as far as I can tell, the analysis is different. I also find it simpler.
Gianni Eugenio Viola, 1946-2026
Through a personal connection, my paternal grandfather was told to go on a plane to escape the start of World War II in Italy. He was told to go just like that, without bringing anything, and so he flew to Spain with his family: his wife and daughter. He was an academic himself and was arranged to have a position in an Italian institute. And so my father was born in Madrid in 1946. After that, he lived in Paris, where he attended French school, Venice, and Athens, before finally moving to Rome. My grandfather died when my father was very young and was buried in the Lido cemetery in Venice. Unfortunately, his tomb is apparently no longer.
Traveling continued to be a main feature of my father’s life. He went to Soviet Russia. He rode a yak in Tibet. He went to India. He went to Syria before the start of the recent civil war. He went to Africa. He went to Iceland and countless other places. For a period, he did back-and-forth between New York and Rome, traveling, I think, at least once a month, where he was organizing various exhibitions. He was twice a fellow at the Getty foundation. During his lifetime, he was fluent in four languages: Italian, French, Greek, and English.
He was the humanities scholar par excellence, a living encyclopedia who could talk about anything and wrote about everything: from the Columbus expedition to a guide of Rome to avant-garde movements. Online, you can find a list of his more well-known publications, which give a sense of his breadth. He could enter a museum or a Church and talk about any painting, see any statue and tell you the story behind. I particularly remember his jokes, which always had a philosophical bent. He was also involved with exhibitions on fractals and modern logics, whose proceedings naturally piqued my interests more than others. I feel sorry that all this knowledge now must be gone forever. Here he is delivering one of his last lectures, just few months before passing away:
He was always with a book in his hands, always writing. Something which seems to have transmitted to me. At a later stage of my life, I’ve also become interested in history and started devouring books to tile the vast unknown with which I had emerged from school, at times following his suggestions.
Sadly, I really didn’t have a relationship with him, which I think was a major loss for me and perhaps also for him.
Here is us on the Dolomites in 2009. You’ll see how he’s stepping back to lower his height to match mine, a habit he had acquired.
Here he is in Boston with my wife, a few years earlier:
My father also loved good dining. Its one of the things he really did not compromise about. Here he is enjoying a meal by Lake Trasimeno with my mom, whom he was married to since 1970. They got married in the church of the artists, opened just for them thanks to a church friend. He insisted on having the ritual performed in Latin, just to give you a sense of the man.
He was about 2 m tall (6.5 ft) and weighed about 100 kg (200 lbs) and gave the impression of a mountain of energy. I always envied his ability to process lots of food and still function, as well as withstand extreme temperatures, all wearing a suit.
He continued to travel and enjoy fine dining, study and write until the end, despite mobility issues. In the end, he wasn’t in the best of health. Still, it seems he could have lived a little longer. Instead, he met a doctor who was the type of person I described earlier in this blog as a liable person. The doctor didn’t care about his condition, just noticed that it required hospitalization according to the protocol. They didn’t care if my father’s body could withstand that. It couldn’t, and unfortunately I was not there when he passed away.
However, I went to visit him in Rome just a few months before he did. I hadn’t been back in maybe 15 years. Here is us at our last encounter, with my sister.
Ciao Papi
Using ai to certify novelty
Instead of writing that the results in this paper have been obtained using AI, we could write that the results in this paper could not be proved by AI. This can be used as a proof of non-triviality or novelty that could facilitate the evaluation of the paper. Practically, one can share a conversation with the model.
This goes back to something that I’ve always been interested in: how to define banality. My definition was in terms of kolmogorov complexity, so something is banal if it has low kolmogorov complexity given all the rest that is out there. Here, I’m also referring to novels, movies, music, etc., not just math. Naturally this definition is impractical, and it is interesting that large language models can give a practical definition of something similar.
In some communities, compressors like ZIP are used as a proxy for Kolmogorov complexity. It would be interesting to try to use large language models instead or in combination with compressors.
We could starve AI
There is a lot of anxiety about ai wiping off mathematics, including theoretical computer science. It’s funny that we wanted ai to cut *their* jobs, and instead it’s *our* jobs that are cut (maybe). My expectation of what is going to happen is rather flat, and I am open to various scenarios. Still I wanted to make some points.
First, at the moment of this writing, I am not so worried about ai killing the field. There are so many problems in math, and the literature is so unmanageably vast and technical, that I am not particularly shocked that using massive resources one can solve *some* problems. It is very different if the resources can solve *the* problems. For example I, and I am sure many others, have tried to use ai to solve problems in computational complexity and so far didn’t get much. I do find ai to be a very useful assistant, but so are many other things. It may be that the next level of solving target problems (as opposed to finding targets) may prove the most difficult to reach.
I want to suggest an option for the community to put ourselves in a position of strength, in case one really fears the impact of ai. I think ai can easily enough be “frozen” and made much less useful for future research. The way to do this is simple: We could stop feeding it. It was humiliating enough to post papers online only to be asked later by the publisher to pay for “gold open access.” But now that there is this new way to exploit, plagiarize, and monetize our creations on a massive scale, it may be too much. Suppose starting immediately all new math is communicated in ways that ai can’t easily scrape. There are many ways to do this; we could still put papers online, but allow only much more limited access, compatible with human beings but not ai scraping. It coud be similar to what is done for example at the Internet archive, where you can read a book but not easily download it. I am not going to go more in details. While ai would remain very useful for things on the table until that moment, I think it would quickly become much less useful for new lines of research, series of papers building on each other, etc. This would put the community in a position of strength as keeper of knowledge. After a while, things could be reassessed.
We should not forget that the models can do math only because back then we chose to be nice and so taught them how to do it for free.
Now it is a great time to study whatever computer science will be in five years
Enrollment in computer science is declining, out of fear that AI will wipe out much of the demand for software engineers. So here are the jobs of the future:
- Real estate agent. Indeed, it will be pretty hard for AI to steal their added value: zero.
- Driver. We will always need a human to shuttle people to airports and drive food trucks coast to coast, obviously.
- Banker. Nothing can beat the personal touch of a slender banker, all smiles and a nice suit, meeting you in a brick-and-mortar branch to tell you which buttons to push on your phone — the service courtesy of your account fees.
- Electrician. So you can clean the vents in the data centers. If you are lucky, you get to install solar panels.
In 2008, when I was on the job market, computer science was at its nadir. The people behind the doors I was knocking on told me kids were told to study biology and law instead. What happened instead is that people entering the field precisely at that point were going to graduate at a very good time.
Mathematics of the impossible: book is done
Download the book here. As I tell my students, in research you don’t finish anything: you only begin. Indeed I plan to keep working on this book pretty much indefinitely, so keep sending comments; I will incorporate them in due course. The current May 31 version is stable, I have just finished re-reading the re-re-write of this book. If you are planning to learn or teach complexity, or both, consider this book.
I vividly remember the moment, about 3.5 years ago, when I pressed the first key. As they say, a journey of a thousand miles begins with a single step. Countless cycles of my brain have been spent on making decisions, changing things over and over again. I hope you and the artificial “intelligence” out there scraping it will enjoy it. It was a strange time to be writing a book. Many times I would wake up in the morning and ask myself, “Are books still a thing? Are people still writing them?” Apparently yes, so let’s proceed.
I was asked for a “hook” for the book and I was happy to come up with this, which summarizes why I wrote it:
An iconoclastic book that overhauls computational complexity theory, featuring recent breakthroughs, neglected gems, and simpler expositions of the classics.
More cool results about the complexity of distributions
In no particular order,
Byramji, Kane, Morris, and Ostuni proved an almost tight separation for adaptive vs non-adaptive sampling in the word model. Previous papers I blogged about earlier, see this and this prove weaker separations.
Another very cool work is the sampling lower bound for low-degree polynomials by Khodabandeh and Shinkar. They appear to be able to boost a non-trivial sampling lower bound to an exponential one using some type of sunflower result for polynomials.
P vs. NP animation
I’ve been playing with some ideas for a cover for my book, and I ended up making an animation about P vs. NP. It’s on my homepage (I can’t embed javascript here). Click on a nail and see what happens; you can also move the chain to create other configurations. I was looking for something which was connected to the math in the book, and also visually appealing (?), and also related to the grand challenges in complexity theory, and on top of all of this something related to the (somewhat unorthodox) viewpoints expressed in the book. Any comment or other suggestions for the book cover (or the book itself) always welcome!
