1. What led you to academia?

Much to the shock of my fellow students, I have wanted to be a professor since my freshman year in Italy. The pursuit of knowledge and the lifestyle freedom really appealed to me. Naturally, I did not have a clue; but I would do it all over again, changing nothing… alright, almost nothing.

  1. How did you become interested in theoretical computer science?

I was totally hooked to computers since I was eight, and also worked on videogames in my early teens. In high school I didn’t mind math, but it was not my passion: It was mostly calculus which I thought was “only good for physics.” In college I had a first glimpse of theoretical computer science, and I was struck. The field was asking the right questions: What is a proof, what is knowledge, what is randomness, when you are short on time?

  1. What are you currently working on?

The most famous open problem in the field is the P vs. NP problem which can be phrased as asking to prove that Super Mario levels, properly constructed, are hard to beat. The general challenge is to exhibit problems that require a lot of time on computers. Much of my research concerns proving such limitations for restricted models of computers, for example computers with no memory. Even understanding such restricted models has proved enormously difficult, and a good reason for that is that they are extremely powerful, much more so than anyone anticipated.


After my previous post, a reader (who amazingly has a nearly identical playing routine) pointed me to it. It’s great! Much better than chess.com.

No ads, no subscriptions; but open-source and passion.

Are some features reserved to Patrons? No, because Lichess is entirely free, forever, and for everyone. That’s a promise.

It doesn’t get better than that, in this world; and that’s why I love computers and the community surrounding them.

Another good news is that I got tired of 5 | 5! The games are just too slow, and my chess isn’t even worth this much of my time. I am now playing 3 | 2. It’s fun the adrenaline kick I get with every match. Also I got much stricter with my routine, and I don’t lose more than once a day.

Here’s my profile. It’s an anagram of my unpronounceable name which can be loosely translated as …and I loved the clouds.

IMPORTANT: Excessive activity and blunders merely reflect my generous sharing of credentials.

And then I thought, why don’t we automatically analyze existing games to find interesting situations, and present them to the user as a puzzle? Naturally, the beauty — and dismay — of living in the AI (after-internet) era is that… it’s already done.

OK, time for my daily fix.

FOCS 2022

I am on the FOCS 2022 Program Committee, and I am overjoyed that the PC meeting will be virtual. Hopefully, the days are over when the program chair can brush aside all cost-benefit considerations, impose their backyard on far-away scholars who need service items, and then splash their offspring at the welcome party.

I am also overjoyed that we will be implementing double-blind reviews. This issue has been discussed and ridiculed at length. Admittedly, it makes it harder to adhere to Leonid Levin’s 1995 influential STOC Criteria. For example, if a reviewer wanted to trash a paper based on the fact that the authors are not in the position to judge their own work, now they’ll have to check online for talks or preprints to know who the authors are. Given the volume of reviews, it’s reasonable to expect that in some cases the reviewer won’t be able to conclusively exclude that a letter-writer is among the authors. In such a situation they can resort to writing a very long, thorough, and competent review whose most significant digit is the STOC/FOCS death sentence: weak accept.

No, I actually do have something more constructive to say about this. I was — as they say — privileged to serve on many NSF panels. As an aside, it’s interesting that there the track-record of the investigators is a key factor in the decision; in fact, according to many including myself, it should carry even more weight, rather than forcing investigators to fill pages with made-up directions most of which won’t pan out. But that’s another story; what is relevant for this post is that each panel begins with a quick “de-biasing” briefing, which I actually enjoy and from which I learnt something. For example, there’s a classic experiment where the ratio of females hired as musicians increases if auditions hide the performer behind a tent and make them walk in on carpet so you can’t tell what shoes they are wearing. Similar experiments exist that hide names from the folders of applicants, etc. What I propose is to do a similar thing when reviewing papers. That is, start with a de-biasing briefing: tell reviewers to ask themselves whether their attitude towards a paper would be different if:

  1. The authors of this paper/previous relevant work were ultra-big shots, or
  2. The authors of this paper/previous relevant work were hapless nobodies, or
  3. The proofs in this paper could be simplified dramatically to the point that even I understand them, or
  4. This result came with a super-complicated proof which I can’t even begin to follow, or

What other questions would be good to ask?

The story of stuff, and installing Linux on a 32-bit computer from 15 years ago

If you haven’t seen it, now is the time to drop everything you are doing and watch The story of stuff. Computer scientists like myself will latch onto the scene where the old computer which looks like a washing machine is thrashed because a tiny component doesn’t fit anymore. In this spirit, I am happy to announce that after substantial challenges I was able to install Linux on a 32-bit laptop from about 15 years ago. First I tried Ubuntu, but I was saddened to learn that they dropped support for 32-bit platforms. Luckily, Debian still supports it for a number of years, and I went for it. The incidents I had during the installation include missing non-free firmware for the wifi which I had to fetch and stick in random places in the USB stick, and an inexplicable failure of the base installation which can be fixed by mounting the USB stick during it.

When you say these things, you get the familiar shrug which means “In the same time you spent doing this I can write a grant proposal and make enough money to buy two new machines.” While this is true, it does not mean it is the right thing to do. We should strive to prolong the life of computers and their components indefinitely, instead of taking pride in showing off the latest gadget purchase. I am writing this post from an Ubuntu system installed on a 2008 desktop.

Uncharacteristically, I see a bright future in this domain. We can store drivers for every hardware configuration ever assembled, and create easy-to-use installation packages. Moreover, all of this can be automated, while we still are at the stage where human intervention is required. And one thing that gives me a lot of hope and continues to impress me is the amazing network of people that are willing to help each other to get computers to work, especially when they run free software. You can have the most technical question and quickly get — for free — the most caring and expert advice, say by posting on stackexachange.

Terrible things about conferences, ICALP 2022 requiring submissions in LIPIcs style, more terrible things about conferences, and a new life

I’m on the ICALP 2022 program committee (PC) and was apparently the first to complain when I saw the draft call for papers, and I asked that the requirement that submissions must be in LIPIcs style be put to a vote. Despite substantial support among the PC for not requiring the majority of authors to squander their time formatting in an exotic style submissions that will be rejected, the Supreme Court blocked the vote. Their main rationale seems to be ensuring correspondence between submissions and proceedings. Ironically, at the same time other conferences are allowing authors to publish in proceedings an abridged version of the (accepted) submission, to make it easier to publish the paper in a journal (which may not want to have a full version already in a conference). We are at the nadir in history where human effort is systematically wasted to produce versions that do not even pretend to be useful for readers — only to check boxes.

When I was at the IAS and was briefed about logistics, I was stunned when they asked me if I type my own papers, or if I needed help with that. I guess the next level will be if you need help with formatting your submissions.

Picture a 100-year old retired scientist who followed the field for 75 years, and who wants to make one more contribution. Even though they are no match for the raw power of a 15-year old, their ability to draw connections almost makes up for it, and their perspective is invaluable to the community. This scientist, whose equipment consists of a desktop from two human generations ago, miraculously held together and kept working through sheer love and intimate knowledge, is now being asked to format their paper in LIPIcs style… or to ask someone else to do it for them (talk about fostering collaboration).

Here’s a non-exclusive list of true, terrible things about conferences, most of which were discussed earlier on this blog (see tag utopia-tcs):

  1. Requiring submissions in proceedings format.
  2. Pre-registering papers by a deadline different than the submission deadline.
  3. Requiring authors to submit a separate 2-page summary of the paper.
  4. Ultra-strict page limits, summary rejection for any deviation.
  5. Suddenly being forced on a short notice to submit a dummy .pdf so that PC assignments can be made.
  6. Extending the list of topics two days before the deadline.
  7. Moving deadlines.
  8. Forcing authors to check multiple times the call for papers and/or constantly monitor email for any of these last-minute changes.
  9. In the lucky case of acceptance, following up with a barrage of emails involving minutiae such as underfull \hbox.
  10. Writing “this only takes 60 seconds.” For me (and, apparently, many others — otherwise why delay answering emails that take 10 seconds to answer?) attending to any task, following any instruction, even “blink” or “say yes” has a huge fix cost, maybe 30 minutes. So I translate 60 seconds to 31 minutes.
  11. Hosting the conference in places which are inconvenient, for the attendees and planet earth.
  12. Hosting the conference at times which are inconvenient for the attendees.
  13. Requiring in-person PC meetings whose outcome does not justify the costs.

As usual, people in a position of power do not have much incentive to fight to change the very practices that put them in that position in the first place. But even this cynical remark doesn’t tell the whole story, since the practices got worse with time, unlike the case of journals. One impression I have is that people have gotten so used to buggy software, constant updates, and general techno slavery that they just accept all of this as another inevitable misery in life… and by far not the worst! This last point is important, as I think a seeping philosophy that permeates much of the discussion and the decisions is that much more important things are at stake, so who cares about this? If you really want to spend cycles fixing something, then what about X? (It’s fun to think where you end up if you stretch this point.) But another life is possible.

One day, I will throw in my two cents and launch a new journal. Besides being electronic and free (like ToC) it will have the following features.

  1. Papers, if accepted, will appear in the authors’ chosen format. No conversion, and no additional effort, will be required for publication. All the effort will be exclusively directed at improving the content of the paper.
  2. Submissions can be by pdf attachment or by overlay, but not only to arxiv: to *any* repository. In particular, authors will not be required to get their paper to compile on the arxiv.
  3. The identities of the reviewers will be made public (in case of acceptance). This I am still debating, but so far I am leaning towards it. The problem that this is trying to address is that while you get reputation points for being on a program committee or on an editorial board, you don’t get many for being an unknown journal referee who is actually supposedly doing the hard work or finally really checking the proofs. Instead with public identities people can show off the hard work and their role in the community, as happens on more recent platforms like say stackexchange.
  4. Authors will be free to submit anonymously, or not. This choice will be made by the authors, not dictated by a committee.
  5. And perhaps the most consequential thing that I am still debating, should all submissions be public? (Maybe not.)

To finish on a high note, a great thing about conferences is the fast turn-around. It is really depressing — in other fields — to have to wait so long for any quantifiable feedback on your work, and this is definitely something which I liked about the TCS community. But, to come back to the mood of the post, this good aspect (and others) of conferences can probably be kept while rethinking the not so good. (For example, there could be a journal with deadlines similar to conferences, which is also what happens for grant proposals etc.)

Pitassi: “More and more, I’m starting to wonder whether P equals NP.”

It’s refreshing to hear other people are joining our “ranks,” especially after some have said that my belief that P=NP is a publicity stunt. (For context, you may want to read the first two sentences of my post.) I got the quote from the Simons Institute Newsletter, which points to a longer MIT Technology Review article to which I don’t have access. The newsletter article mentions two well-known surprising results (also on my list), and another cool one which came after my post and that I was thinking of adding. For more surprising results, see my list. What do you believe?

“I doubt that there will be eight, I highly doubt there will be eight.”

Says campaign strategist at 1:13 on this clip from almost exactly 3 years ago.

For background readers can look at this tag.

Where are we today? (Official communication.)

  • Union Twist, 1158 Beacon Street in Newton Centre/Four Corners, has been unanimously approved by the City Council for its Special Permit. Union Twist plans to demolish the current building on the site consisting of a dry cleaner and restaurant and build a new 2,300-square foot, one story retail building with 22 on-site parking spaces. For at least the first six months of operation, there will be an appointment only requirement for customers at the store. As their Special Permit has been approved, they can move forward with their state Cannabis Control Commission (CCC) licensing approval process.
  • Garden Remedies, Newton’s first adult-use retail marijuana store, opened at 697 Washington Street in Newtonville more than two years ago in May 2019. Since opening, Garden Remedies has sold to customers by appointment only. The request from Garden Remedies to amend its current Special Permit to remove the appointment only condition for their retail shop was approved by the City Council Land Use Committee. (The vote was 5-0, with three abstentions.) The full City Council will vote on lifting the appointment only condition at their meeting this Monday, Nov. 15.
  • Redi, Newton’s second adult-use retail marijuana establishment (formerly known as Cypress Tree) opened in July 2021 at 24 Eliot Street at the intersection with Boylston Street/Route 9 in Upper Falls. (It was (formerly known as Cypress Tree.) The Special Permit approved by the City Council requires that Redi’s retail customers must have an appointment to shop or pick-up products for at least the first six months of operation. 
  • Ascend, 1089 Washington Street/58 Cross Street just outside West Newton Square, has a signed provisional HCA and an approved Special Permit. Construction is nearing completion and they are awaiting licensing approval by the CCC to open.
  • MedMen, 232 Boylston Street/ Rte. 9 in Chestnut Hill (at the former Shreve, Crump & Low location), has a signed provisional Host Community Agreement (HCA) and an approved Special Permit. They are both awaiting licensing approval by the CCC to open as well as a building permit from the City of Newton to begin work on the building.
  • Green Lady, 740 Beacon Street in Newton Centre, a woman and minority owned business, has a signed provisional HCA and the City Council Land Use Committee is currently hearing its Special Permit application. If their Special Permit is approved, they can then move forward with their CCC licensing approval process 
  • Verilife, 131 Rumford Avenue in Auburndale, has a signed provisional HCA and the City Council Land Use Committee is currently hearing its Special Permit application. If their Special Permit is approved, they can then move forward with their CCC licensing approval process.
  • Nuestra, 1185 Chestnut Street in Newton Upper Falls, has a signed provisional HCA. Nuestra is a Cannabis Control Commission certified Economic Empowerment Applicant. They have not yet started the City Council Special Permit approval process which they need to do before moving forward in the state licensing approval process.

Fibonacci and I

The other day I couldn’t remember Fibonacci’s original motivation/presentation of the sequence now famously named after him. This had to be corrected immediately, because of the picture above and my first publication (1994) which includes a simple algorithm to decompress sounds. The compression algorithm works by storing rather than the sound data — think of it as the key — the difference between consecutive keys. The saving comes from not allowing every possible difference, but only those in… the Fibonacci sequence. Why those differences are the right ones is part of the mystique which makes studying the sequence fun. For further technical but not mystical details see the paper; an implementation of the decompressor is given in the Motorola 68000 assembly code.

This is me on my way to Fibonacci from Rome, some years ago:

I actually find some presentations of the sequence a little hard to grasp, so I came up with a trivially different rendering which now will make it impossible for me to forget:

There are two types of trees: Young and old. You start with one young tree. In one period, a young tree produces another young tree and becomes old, and an old tree produces a young tree and dies. How many young trees are there after t periods?

PeriodYoung treesOld trees

I also couldn’t exactly remember the spiral you can make with these numbers. But you can tile the plane with squares whose sides come from the sequence, if you arrange them in a spiral.

Flu, by Gina Kolata

I enjoyed reading this book. Three themes are dear to me:

First, the macabre. Not that there is any shortage in the news, but the book also contains macabreness of a kind I did not expect.

Second, the drive for scientific research. It always makes for a compelling read when the reader is a scientist. And here it is also tinted with adventure.

Third, (recent) history. As I hinted in some previous posts, I started reading history in my late 20’s, as an unbelievably blank slate, and I haven’t stopped. It is not clear it is very consequential for the present, but sometimes it’s good to know how things “evolve.”