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