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?
PhD in complexity theory with me
This is around the time when people start applying for PhD programs, at least judging from my inbox. If you are applying, consider that we have an amazing theory group , are highly ranked, have tons of resources, and I am looking for students.
“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?
| Period | Young trees | Old trees |
| 1 | 1 | 0 |
| 2 | 1 | 1 |
| 3 | 2 | 1 |
| 4 | 3 | 2 |
| 5 | 5 | 3 |
| 6 | 8 | 5 |
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.”
Chess.com: 5|5 > 1000
Today for the first time, I surpassed score 1000 on Chess.com playing 5|5, which means you start with a 5-minute budget, and every move you get 5 more seconds. For a while I also played 3|2 (2-second increments), but it takes me about 2 seconds to move a piece, which means I lost games in which I knew exactly what to do, but simply couldn’t move the pieces fast enough, which I found frustrating. Longer games I tried but I don’t seem to have the patience for.
I won’t reveal my id, because I feel bad about how much time I am spending losing at chess (and I think you could see all my games with my id, but I am not sure). My self-imposed limit is losing no more than one game a day, which means on average playing 2 games per day. (I had to stop and Google 
However not being a robot, I sometimes get upset at the way I lose. Most of my games are classified as giveaway, which means I was winning according to the computer (and myself), but then because of some stupid mistake I end up losing the game. And so what the heck, I am better than this!, I break the rule and start another match — only to lose again, chess seems not to forgive hot heads.
The main reason why I play seems to be that fast-paced chess has the ability to completely absorb my mind, so it’s a good quick escape. Of course, there are also the little feel-good voices reminding me that it’s better than watching TV and that by playing I sharpen my mind.
While 1000 can of course be a ridiculously low bar by some standard, I found reaching it more difficult than I expected, and I like to think that the 5|5 format attracts stronger players, so that the competition is tougher, even though it may not be true. (But it does seem true that a certain score in a certain format does not correspond to the same score in a different format.) For one thing, I had to familiarize myself with several basic openings. I bought a little cute book Chess openings for kids which is good for people like me whose knowledge of chess openings was “e4 e5.” I don’t do anything fancy, but it was fun to read about common openings. I think I also wouldn’t mind playing random chess, but it seems harder to find opponents.
So why don’t you try and see what is your 5|5 score? And if you want to play sometimes, drop me a line.
Windows never changes
For months, Windows 10 complained that it didn’t have enough space on the hard disk, but the options it gave me to clean up space were ridiculous. Worse, the “storage” function that supposedly tells you what’s taking space wasn’t even close to the truth. This became so bad that I was forced to remove some things I didn’t want to remove, often with a lot of effort, because space was so tight that Windows didn’t even have enough to run the uninstaller! In the end I became so desperate that I installed TreeSize Free. It quickly revealed that crash plan was taking up a huge amount of space. This revealed to be associated to the Code42 program — a program that the system was listing as taking 200MB. Well, uninstalling Code42 freed SIXTY PERCENT of the hard disk space, 140GB.
Data-structure lower bounds without encoding arguments
I have recently posted the paper [Vio21] (download) which does something that I have been trying to do for a long time, more than ten years, on and off. Consider the basic data-structure problem of storing 
can be computed by probing 
As is common in data-structure lower bounds, the proof in [PV10] is an encoding argument. In the recently posted paper, an alternative proof is presented which avoids the encoding argument and is perhaps more in line with other proofs in complexity lower bounds. Of course, everything is an encoding argument, and nothing is an encoding argument, and this post won’t draw a line.
The new proof establishes an intrinsic property of efficient data structures, whereas typical proofs including [PV10] are somewhat tailored to the problem at hand. The property is called the separator and is a main technical contribution of the work. At the high level the separator shows that in any efficient data structure you can restrict the input space a little so that many queries are nearly pairwise independent.
Also, the new proof rules out a stronger object: a sampler (see previous post here on sampling lower bounds). Specifically, the distribution Rank
Building on this machinery, one can prove several results about sampling, like showing that cell-probe samplers are strictly weaker than AC0 samplers. While doing this, it occurred to me that one gets a corollary for data structures which I had not seen in the literature. The corollary is a probe hierarchy, showing that some problem can be solved with zero redundancy (
One of my favorite open problems in the area still is: can a uniform distribution over ![[m]](https://s0.wp.com/latex.php?latex=%5Bm%5D&bg=ffffff&fg=333333&s=0&c=20201002)
References
[Pǎt08] Mihai Pǎtraşcu. Succincter. In 49th IEEE Symp. on Foundations of Computer Science (FOCS). IEEE, 2008.
[PV10] Mihai Pǎtraşcu and Emanuele Viola. Cell-probe lower bounds for succinct partial sums. In 21th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 117–122, 2010.
[Vio21] Emanuele Viola. Lower bounds for samplers and data structures via the cell-probe separator. Available at http://www.ccs.neu.edu/home/viola/, 2021.
[Yu19] Huacheng Yu. Optimal succinct rank data structure via approximate nonnegative tensor decomposition. In Moses Charikar and Edith Cohen, editors, ACM Symp. on the Theory of Computing (STOC), pages 955–966. ACM, 2019.
Questions on the future of lower bounds
Will any of the yellow books be useful?
Book 576 (not pictured) was saved just in time from the paper mill. It was rumored that Lemma 76.7.(ii) could have applications to lower bounds. Upon closer inspection, that lemma has a one-line proof by linearity of expectation if you change the constant 17 to 19. This change does not affect the big-Oh.
Will the study of randomness lead to the answer to any of the questions that are open since before randomness became popular? I think it’s a coin-toss.
Will there be any substance to the belief that algebraic lower bounds must be proved first?
Will the people who were mocked for working on DLOGTIME uniformity, top fan-in k circuits, or ZFC independence have the last laugh?
Will someone switch the circuit breaker and lit up CRYPT, DERAND, and PCPOT, or will they remain unplugged amusement parks where you sit in the roller coaster, buckle up, and pretend?
Will diagonalization be forgotten, or will it continue to frustrate combinatorialists with lower bounds they can’t match for functions they don’t care about?
Will decisive progress be made tonight, or will it take centuries?
Only Ketan Mulmuley knows for sure.
Submitting to ICALP 2021
I am taking advantage of the pandemic to participate in conferences where it’s usually hard for me to participate because they require intercontinental travel. I have a paper in CSR 2021, and now am submitting a paper to ICALP 2021 (I count submission as participation, even in case the paper gets rejected). The latter requires submissions to be formatted in a specific way, a topic discussed at length on this blog.
Begin 12:48
Download the LIPICs package.
Try to compile their sample paper.
Get error message: ! LaTeX Error: File `l3backend-dvips.def’ not found.
Google solution. Says to install packages.
Unfortunately, I am using windows but I only have LyX, and the solution expects MixTeX.
Google how to install packages in LyX.
Can’t find anything simple.
Create a new document on overleaf.
Copy all the LIPIcs files there.
Try to compile their sample.
It works!
Paste my latex.
Usual avalanche of problems to be fixed at the speed of light.
Add dummy section “Introduction” which wasn’t in my paper, otherwise theorem numbers look weird.
Numbers still look weird. Something’s wrong with theorem statements.
Replace {thm} with {theorem}
Looks better. Still some wrong stuff all around, however.
No it wasn’t that. Remove the dummy section. It seems their “paragraph” environment puts strange numbers like 0.0.0.1
Replace \paragaph with \paragaph* everywhere
Actually, looks weird the way they put the ack– put back the dummy Introduction section.
Check page limit: no more than 12 pages, excluding references
I’m a little over. Does this really matter? Apparently, it does! Move last proof to the appendix. Actually, last proof is kind of short, I should move the penultimate proof. Update paper organization (next time I shouldn’t put it).
Final look. Fix a few indentations.
OK, time to actually submit. Go to the easychair website. They want me to re-enter all the information!? Why, after forcing me to enter title, keywords, etc. in their format, are they asking me to do this again? Can’t we just send the .tex file and extract it from there?
Oh come one, it’s just a few seconds of copy-paste.
OK, done, paper submitted.
End: 3:05
Well, next time it will be easier. Perhaps easier, but not easy because as the reader knows there will be another missing package, another incompatible system, etc. And of course, if the paper is rejected, then I won’t even save the time to convert it into camera-ready format. On the other hand, the benefit is non-existent. It would be better for everyone if in order to submit a paper you have to complete a random 1-hour task on Amazon mechanical Turk and donate the profit to charity.
Thoughts 