# Just coincidence?

Proving lower bounds is one of the greatest intellectual challenges of our time. Something that strikes me is when people reach the same bounds from seemingly different angles.  Two recent examples:

• Static Data Structure Lower Bounds Imply Rigidity, by Golovnev, Dvir, Weinstein.  They show that improving static data-structure lower bounds, for linear data structures, implies new lower bounds for matrix rigidity.  My understanding (the paper isn’t out) is that the available weak but non-trivial data structure lower bounds imply the available weak but non-trivial rigidity lower bounds, and there is absolutely no room for improvement on the former without improving the latter.
• Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity, by Dinur and Meir.  They reprove the $n^3$ bound on formula size via seemingly different techniques.

What does this mean?  Again, the only things that matter are those that you can prove.  Still, here are some options:

• Lower bounds are true, and provable with the bag of tricks people are using.  The above is just coincidence. Given the above examples (and others) I find this possibility quite bizarre. To illustrate the bizarre in a bizarre way, imagine a graph where one edge is a trick from the bag, and each node is a bound. Why should different paths lead to the same sink, over and over again?
• Lower bounds are true, but you need to use a different bag of tricks. My impression is that two types of results are available here.  The first is for “infinitary” proof systems, and includes famous results like the Paris-Harrington theorem. The second is for “finitary” proof systems, and includes results like Razborov’s proof that superpolynomial lower bounds cannot be proved in Res(k). What I really would like is a survey that explains what these and all other relevant proof systems are and can do, and what would it mean to either strengthen the proof system or make the unprovable statement closer to the state-of-the-art. (I don’t even have the excuse of not having a background in logic.  I took classes both in Italy and in the USA.  In Italy I went to a summer school in logic, and took the logic class in the math department.  It was a rather tough class, one of the last offerings before the teacher was forced to water it down.  If I remember correctly, it lasted an entire year (though now it seems a lot).  As in the European tradition, at least of the time, instruction was mostly one-way: you’d sit there for hours each week and just swallow this avalanche of material. At the very end, there was an oral exam where you sit with the instructor — face-to-face — and they mostly ask you to repeat random bits of the lectures.  But for the bright student some simple original problems are also asked — to be solved on the spot.  So there is substantial focus on memorization, a word which has acquired a negative connotation, some of which I sympathize with.  However a 30-minute oral exam does have its benefits, and on certain aspects I’d argue it can’t quite be replaced by written exams, let alone take-home.  But I digress.)
• Lower bounds are false. That is, all “simple” functions have say $n^3$ formula size.  You can prove this using computational checkpoints, a notion which in hindsight isn’t too complicated, but alas has not yet been invented.  To me, this remains the more likely option.

What do you think?

# An interview

The Italian newspaper Il fatto quotidiano just published online an interview with me, part of a series about Italian expats.  You can read it in English by pasting it into Google Translate. Please do not take every sentence, including the opening, as absolute.  Besides what is lost in translation, some thoughts have been de-contextualized, without my opposition, I think to make the narrative more gripping.

The main difference? “That in America, the degree you buy it. In Italy you must deserve it “. Emanuele Viola left Italy in 2001, during his doctorate at the Sapienza University of Rome. “I gave up a scholarship for a PhD at Harvard – he recalls -. Then I moved to Princeton, Columbia and Boston. ” Today he is a professor of theoretical computer science at Northeastern University in Boston. Return? “Yes, I hope to come back one day”.

Emanuele, born in 1977, was born in Rome. At 14, he programmed the video game Nathan Never, followed by Black Viper. At the age of 24, he traveled to the United States for a doctorate in computer science at Harvard University, followed by a postdoc at the Institute of Advanced Study in Princeton and one at Columbia University. “Then I became a professor at Northeastern University in Boston, where I received my professorship a few years ago.”

The typical day may vary based on academic work. “Personally, I work better if I spend a lot of time at home in almost complete isolation – explains Emanuele -. If I do not have to teach, I usually stand in front of a blank sheet trying to solve some problems – continues – until finally it’s time for my walk in the woods, so at least in one thing I can feel close to Einstein and Darwin, “he smiles. “I go to university a few days a week to teach or to attend various meetings. But I often connect via Skype “.

Italy misses him a lot, has less time to visit and the difference with the American academic world is drastic: “American universities are direct as companies in competition with each other, constantly looking for more money, better teachers and better students. Here, after you’ve been admitted, it’s almost as if you already had a degree in your pocket. It’s not exactly like this in Italy: of the 200 of my course – he recalls – I was the only one who graduated in five years, that is, not going out of course “.

For Emanuele then, the academic world and Italian research has not only fund problems. Rather. “A hundred years ago, it was typical for an American scholar to spend a period of training in Europe – continues Emanuele -. In a few generations, the situation has exactly reversed “. In this sense the problem of Italy is also that of the rest of Europe and other parts of the world. “America has amassed so many brilliant minds from all over the world that it is very difficult for another nation to be competitive, regardless of funding. Indeed, those in the European community are substantial and competitive. Right now “in America there are not many funds – he specifies – especially for the theory”.

The situation is reversed for the doctorate. “Here it does not have a fixed duration: if you do not throw yourself out, you go out when you have competitive publications, so it can take you even six or seven years. In Italy, the pre-established duration is three years, once absolutely insufficient to produce competitive publications “. This difference is also due to the fact that in the United States the salary of the student comes from the advisor, in Italy mainly from a government grant.

If we talk about training, in short, the subject changes. “Personally, I consider the instruction I received almost gratuitously at Sapienza, much more solid than the typical American preparation. This however reverses completely for advanced studies. Here there are more chances for deserving students. In Italy there is very little research in my field “.

The most beautiful memories? The rare moments when the clear sensation of solving a mathematical problem arrives. “It happened to me once while rolling on my ball and three times while walking through cemeteries,” he smiles. The goal for Emanuele is to return to Italy, even if with the family in America it is not easy. “For some time I have been planning a sabbatical year in Italy. I hope to get in touch with the contacts and that maybe one day not too far they will translate into a return “.

The environment in a private university where taxes exceed 50 thousand dollars a year is completely different from “what I remember from my student days”. Yet Emanuele is keen to say something: “No, I do not want to give the impression that money makes a big difference. The fact is that America has succeeded in attracting the best minds from all over the world – he concludes -. And no other country has succeeded “.

# Hardness amplification proofs require majority… and 15 years

Aryeh Grinberg, Ronen Shaltiel, and myself have just posted a paper which proves conjectures I made 15 years ago (the historians want to consult the last paragraph of [2] and my Ph.D. thesis).

At that time, I was studying hardness amplification, a cool technique to take a function $f:\{0,1\}^{k}\to \{0,1\}$ that is somewhat hard on average, and transform it into another function $f':\{0,1\}^{n}\to \{0,1\}$ that is much harder on average. If you call a function $\delta$-hard if it cannot be computed on a $\delta$ fraction of the inputs, you can start e.g. with $f$ that is $0.1$-hard and obtain $f'$ that is $1/2-1/n^{100}$ hard, or more. This is very important because functions with the latter hardness imply pseudorandom generators with Nisan’s design technique, and also “additional” lower bounds using the “discriminator lemma.”

The simplest and most famous technique is Yao’s XOR lemma, where

\begin{aligned} f'(x_{1},x_{2},\ldots ,x_{t}):=f(x_{1})\oplus f(x_{2})\oplus \ldots \oplus f(x_{t}) \end{aligned}

and the hardness of $f'$ decays exponentially with $t$. (So to achieve the parameters above it suffices to take $t=O(\log k)$.)

At the same time I was also interested in circuit lower bounds, so it was natural to try to use this technique for classes for which we do have lower bounds. So I tried, and… oops, it does not work! In all known techniques, the reduction circuit cannot be implemented in a class smaller than TC$^{0}$ – a class for which we don’t have lower bounds and for which we think it will be hard to get them, also because of the Natural proofs barrier.

Eventually, I conjectured that this is inherent, namely that you can take any hardness amplification reduction, or proof, and use it to compute majority. To be clear, this conjecture applied to black-box proofs: decoding arguments which take anything that computes $f'$ too well and turn it into something which computes $f$ too well. There were several partial results, but they all had to restrict the proof further, and did not capture all available techniques.

Should you have had any hope that black-box proofs might do the job, in this paper we prove the full conjecture (improving on a number of incomparable works in the literature, including a 10-year-anniversary work by Shaltiel and myself which proved the conjecture for non-adaptive proofs).

### Indistinguishability

One thing that comes up in the proof is the following basic problem. You have a distribution $X$ on $n$ bits that has large entropy, very close to $n$. A classic result shows that most bits of $X$ are close to uniform. We needed an adaptive version of this, showing that a decision tree making few queries cannot distinguish $X$ from uniform, as long as the tree does not query a certain small forbidden set of variables. This also follows from recent and independent work of Or Meir and Avi Wigderson.

Turns out this natural extension is not enough for us. In a nutshell, it is difficult to understand what queries an arbitrary reduction is making, and so it is hard to guarantee that the reduction does not query the forbidden set. So we prove a variant, where the variables are not forbidden, but are fixed. Basically, you condition on some fixing $X_{B}=v$ of few variables, and then the resulting distribution $X|X_{B}=v$ is indistinguishable from the distribution $U|U_{B}=v$ where $U$ is uniform. Now the queries are not forbidden but have a fixed answer, and this makes things much easier. (Incidentally, you can’t get this simply by fixing the forbidden set.)

### Fine, so what?

One great question remains. Can you think of a counter-example to the XOR lemma for a class such as constant-depth circuits with parity gates?

But there is something more why I am interested in this. Proving $1/2-1/n$ average-case hardness results for restricted classes “just” beyond AC$^{0}$ is more than a long-standing open question in lower bounds: It is necessary even for worst-case lower bounds, both in circuit and communication complexity, as we discussed earlier. And here’s hardness amplification, which intuitively should provide such hardness results. It was given many different proofs, see e.g. [1]. However, none can be applied as we just saw. I don’t know, someone taking results at face value may even start thinking that such average-case hardness results are actually false.

### References

[1]   Oded Goldreich, Noam Nisan, and Avi Wigderson. On Yao’s XOR lemma. Technical Report TR95–050, Electronic Colloquium on Computational Complexity, March 1995. http://www.eccc.uni-trier.de/.

[2]   Emanuele Viola. The complexity of constructing pseudorandom generators from hard functions. Computational Complexity, 13(3-4):147–188, 2004.

# Black Viper

Over at the Amigospodcast, dreamkatcha posted a series of five posts on the defunct Italian software house Lightshock software. This post is about Black Viper, a game which I coded up back in the 90’s. The last post is about what happened to us afterwards. I have contributed to the posts the following (which you can also read there among nice pictures):

Black Viper is the second game I coded up, after Nathan Never. I vividly remember when I turned down an offer to work on Nathan Never 2. In hindsight, I think it’s been a mistake. True, my experience with Nathan Never had not been very pleasant. The producers did not pay half of what was promised on the contract (something for which I subsequently sued them, in vain). The person who most closely directed the works did not have much experience with games, but understandably was mostly interested in the publicity that would come from the title (Nathan Never is a popular comic book in Italy). I was also threatened extortion if I didn’t finish the game in time.

But on the positive side, after some difficulty they had shipped me an A3000T to complete the game. And most importantly of all, the game got down in six months! Black Viper instead took three ominous years.

But when I made the decision I was 15 and I really had no idea. I had always wanted to work on a beat’em up, and at some point Marco Genovesi and I even had a small demo. My impression is that we ended up working on a bike game because neither of us liked it. We did like the post-apocalyptic atmosphere though.

So we started working on this project again during our high school (the game finally hit the shelves during my first year of college). Our initial name was “Dark Blade” and the game had disproportionate depth, including bets, tournaments, and race against radioactive magma. It was again great to work with Marco, one of the most talented persons I have ever met. We were in the same classroom in high school every day (Italian high school has or at least had a rigid system thanks to which you spent all your time with the same people). Classrooms had desks for two people, and I think the first year Marco and I even shared the desk. If I remember correctly we were both somewhat timid and we naturally ended up together (but here I may be stretching my memory). We would exchange floppy disks in class and generally chat about the game and sketch ideas. Interaction wasn’t always easy, but it was always rewarding.

Our professors took note of what we were doing, and said nothing. I believe in almost any other environment they would have jumped on the students and push them hard to their full potential.

Soon, completing Dark Blade without a however horrible software house proved quite difficult. I don’t remember exactly how we got to Lightshock Software. I think it was through some personal connection. In any case, at some pint this software house materialized, they liked the game, and had some connection to sell it in the broader European market through NEO. So we decided to go with them. We had quite a few fun trips from Rome (where we were based) to Prato (where Lightshock Software was) to discuss the game and our subsequent expansion and world domination. It was also fun to connect with more game developers. They worked with us to make the game better, and to add some extras for the AGA and CD32 versions.

One fond memory I have is when I needed help to hunt down a bug. Basically, the game would occasionally hang up. I had never given that much thought, since it was quite rare. But, of course, the last version of the game systematically crashed exactly at the last level. It’s hard to imagine anything worse. First, reproducing the bug wasn’t the easiest thing. Second, the code was three years old, and it consisted of a single, colossal file in assembly, commented as thoroughly as only a 15-year-old can.

So it was arranged for me to go spend some days at their headquarters and work with Marco Biondi, another Amiga coder. He hosted me at his quaint house in Florence, and together we had a few days of intense debugging. He had no idea of the code whatsoever of course, and was horrified to see certain parts of it which reflected my complete lack of training (my only source had been the Amiga Hardware reference manual, brought to me years ago by Marco Genovesi when I had sprained my ankle jumping from the top of a swing). But Marco Biondi was quite helpful. Eventually, we were able to freeze the machine right before the crash, and we went through one assembly instruction at the time. Amazingly, at some point the instructions became complete gibberish. We exulted. Someone entered the room and proposed something, perhaps going out. I remember Marco Biondi saying no, now “lo teniamo per le palle” (we grab it by the balls).
We looked at how long the gibberish code was, and it turned out to be exactly the length of one of the rectangular elements that made the road. This quickly led us to investigate the code that builds the road. And there I found an assembly subroutine where the register d0 was used instead of a0, which would cause problems if I remember correctly with the carry-around when you increment it. We fixed it and the game didn’t crash anymore. Amazingly, that subroutine was one of the very first which I had written. Throughout the day, we had been playing continuously the same clip of about ten seconds of a heavy metal song.

I think the my share of the sales amounted to the equivalent of \$500 today, much less than what I had made with Nathan Never.

Towards the end of Black Viper, and after it, I also worked with other people on a 3D engine. We used things like binary-space-partition trees, and had a demo working both on PC and Amiga. But then it quickly became clear that the only way to even hope to produce anything competitive would be to work on the project full time, which was also difficult because we worked on different parts of Rome and there was no internet. It had been much more convenient to share floppy disks in class with Marco Genovesi!

At some point I also got an offer from Lightshock software to move to their Belluno headquarters to work full time on programming games. They promised a hefty salary and considerable freedom. I thought about it, but in the end I did not go for it. I was in the middle of my college studies which were going well and I didn’t feel like abandoning them (my parents also advised me against). Again I remember the phone call during which I turned them down, perhaps another mistake. I had always wondered what had happened to Lightshock software!

Afterwards I was in touch with other wanna-be software houses, but it was clear that they did not have the capacity that Lightshock software had, and I think they did not end up producing any game.

So I completed my studies, I got interested in mathematics and theoretical computer science, and ended up doing a Ph.D. at Harvard University, and have stayed in the US ever since. I still program, and occasionally I toy with the idea of being involved again with a computer game (besides as a player of course, that has never stopped).