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!

Feedback requested for the complexity book “Mathematics of the impossible”

I have just completed a draft of the book. It is the March 4 version on my homepage. CLICK HERE TO DOWNLOAD. (If you downloaded already, check you don’t have the earlier version cached.) I would very much appreciate any feedback on the book, including suggestions on things to include, especially if they fit well and are not overly technical. Please feel completely free to suggest your own results.

After collecting feedback, I plan to do one more pass and then it’s off to the press, so speak now ;-)

Here is the table of contents in case you want to know what the book is about before downloading:

0 Introduction
0.1 Teasers
0.1.1 Computing with three bits of memory
0.1.2 Randomness and derandomization
0.1.3 Proofs and delegating computation
0.1.4 Changing base losing no time and no space
0.2 Notation
0.3 Contents and comparisons
0.4 How to use this book
0.5 Acknowledgments

1 Time
1.1 Word programs
1.2 Complexity classes
1.3 You don’t need much to have it all
1.4 Composing programs
1.5 Universal programs
1.6 The fastest algorithm for Factoring
1.7 On the word size
1.7.1 Factoring with large words
1.8 The grand challenge
1.8.1 Undecidability and diagonalization
1.8.2 The hierarchy of Time
1.9 Problems
1.10 Notes

2 Circuits
2.1 The grand challenge for circuits
2.2 Circuits vs. Time
2.3 Cosmological, non-asymptotic impossibility
2.4 Problems
2.5 Notes

3 Randomness
3.1 Error reduction for one-sided algorithm
3.2 Error reduction for BPTime
3.3 The power of randomness
3.3.1 Verifying matrix multiplication
3.3.2 Checking if a circuit represents zero
3.4 Does randomness really buy time?
3.5 The hierarchy of BPTime
3.6 Problems
3.7 Notes

4 Reductions
4.1 Types of reductions
4.2 Multiplication
4.3 3Sum
4.4 Satisfiability
4.4.1 3Sat to Clique
4.4.2 3Sat to Subset-Sum
4.4.3 3Sat to 3Color
4.4.4 More
4.5 Power hardness from SETH
4.6 Search problems
4.7 Gap-Sat: The PCP theorem
4.8 Problems
4.9 Notes

5 Nondeterminism
5.1 Nondeterministic computation
5.2 Completeness
5.3 From programs to 3Sat in quasi-linear time
5.3.1 Efficient sorting circuits
5.4 Power from completeness
5.4.1 Max-3Sat
5.4.2 NP is as easy as detecting unique solutions
5.5 Alternation
5.5.1 Does the hierarchy collapse?
5.6 Problems
5.7 Notes

6 Space
6.1 Branching programs
6.2 The power of L
6.2.1 Arithmetic
6.2.2 Graphs
6.2.3 Linear algebra
6.3 Checkpoints
6.4 The grand challenge for space
6.5 Randomness
6.6 Reductions
6.6.1 P vs. PSpace
6.6.2 L vs. P
6.7 Nondeterministic space
6.8 An impossibility result for 3Sat
6.9 TiSp
6.10 Computing with a full memory: Catalytic space
6.11 Problems
6.12 Notes

7 Depth
7.1 Depth vs space
7.2 The power of NC2: Linear algebra
7.3 Formulae
7.3.1 The grand challenge for formulae
7.4 The power of NC1: Arithmetic
7.5 Computing with 3 bits of memory
7.6 Group programs
7.7 The power NC0: Cryptography
7.8 Word circuits
7.8.1 Simulating circuits with square-root space
7.9 Uniformity
7.10 Problems
7.11 Notes

8 Majority
8.1 The power of TC0: Arithmetic
8.2 Neural networks
8.3 Amplifying lower bounds by means of self-reducibility
8.4 The power of Majority: Boosting correlation
8.5 Uniformity
8.6 Problems
8.7 Notes

9 Alternation
9.1 The polynomial method over F2
9.1.1 AC0 correlates with low-degree polynomials modulo 2
9.1.2 Using the correlation to show that Majority is hard
9.2 The polynomial method over R
9.2.1 AC0 correlates with low-degree real polynomials
9.2.2 Sign-Approximating Maj-AC0
9.2.3 Using the correlation to show impossibility for Maj-AC0
9.2.4 AC0 has small correlation with parity
9.3 Switching lemmas
9.3.1 Switching I
9.3.2 Switching II
9.3.3 Proof of switching II
9.4 AC0 vs L, NC1, and TC0
9.4.1 L
9.4.2 Linear-size log-depth
9.4.3 TC0
9.5 The power of AC0: Gap majority
9.5.1 Back to the PH
9.6 Mod 6
9.6.1 The power of ACC0
9.7 Impossibility results for ACC0
9.8 The power of AC0: sampling
9.9 Problems
9.10 Notes

10 Proofs
10.1 Static proofs
10.2 Zero-knowledge proofs
10.3 Interactive proofs
10.4 Delegating computation: Interactive proofs for muggles
10.4.1 Warm-up: Counting triangles
10.4.2 Delegating NC
10.5 Problems
10.6 Notes

11 Pseudorandomness
11.1 Basic PRGs
11.1.1 Local tests
11.1.2 Low-degree polynomials
11.1.3 Local tests, II
11.1.4 Local small bias
11.2 PH is a random low-degree polynomial
11.3 Pseudorandom generators from hard functions
11.3.1 Stretching correlation bounds: The bounded-intersection generator
11.3.2 Turning hardness into correlation bounds
11.3.3 Hard-core sets
11.3.4 Derandomizing the XOR lemma
11.3.5 Encoding the whole truth-table
11.3.6 Monotone amplification within NP
11.4 Finding the hard core
11.5 Cryptographic pseudorandom generators
11.5.1 AC0
11.5.2 Circuits
11.6 Problems
11.7 Notes

12 Expansion
12.1 Edge expansion
12.2 Spectral expansion
12.3 Undirected reachability in L
12.4 What do expanders fool?
12.5 On the proof of the PCP theorem
12.6 Problems
12.7 Notes

13 Communication
13.1 Two parties
13.1.1 The rectangle method and the Equality function
13.1.2 Rounds: Pointer chasing
13.1.3 Randomness
13.1.4 Arbitrary partition
13.2 Number-on-forehead
13.2.1 Generalized inner product
13.2.2 The power of logarithmic parties
13.2.3 Pointer chasing
13.3 Problems
13.4 Notes

14 Arithmetic
14.1 Linear transformations
14.1.1 The power of depth-2 xor circuits
14.2 Integers
14.3 Univariate polynomials
14.4 Multivariate polynomials
14.5 Depth reduction and completeness
14.6 Alternation
14.6.1 The power of depth 3
14.6.2 Impossibility results
14.7 Problems
14.8 Notes

15 Structures
15.1 Static
15.1.1 Succinct
15.1.2 Succincter
15.1.3 Impossibility results by ruling out samplers
15.2 Dynamic
15.3 Problems
15.4 Notes

16 Tapes
16.1 On the alphabet
16.1.1 The universal TM
16.2 Multi-tape machines
16.2.1 Time vs. TM-Time
16.3 TMs vs circuits
16.4 The grand challenge for TMs
16.4.1 Communication bottleneck: crossing sequences
16.5 TM-Time hierarchy
16.6 Randomness
16.7 Sub-logarithmic space
16.7.1 The power of sub-logarithmic space
16.8 Problems
16.9 Notes

17 Barriers
17.1 Black-box
17.2 Natural proofs
17.2.1 Examples of proofs that are natural
17.2.2 Ruling out natural proofs under popular conjectures
17.3 Problems
17.4 Notes

18 Speculation
18.1 Critique of common arguments for P ≠ NP

A Miscellanea
A.1 Logic
A.2 Integers
A.3 Sums
A.4 Inequalities
A.5 Probability theory
A.5.1 Deviation bounds for the sum of random variables
A.6 Squaring tricks
A.7 Duality
A.8 Groups
A.9 Fields
A.10 Linear algebra
A.11 Polynomials
A.12 Notes

A Landscape