Comments for Thoughts

Comment on Feedback requested for the complexity book “Mathematics of the impossible” by Manu

Manu — Wed, 04 Mar 2026 22:55:10 +0000

Hi Robert, sure. The table of contents (which I just pasted) and the intro should give a good sense of what the book is about. Let me know if I can say more. Feedback from readers who don't have specific knowledge (but some computer science and mathematical maturity) would also be very helpful.

Comment on Feedback requested for the complexity book “Mathematics of the impossible” by Anonymous

Anonymous — Wed, 04 Mar 2026 22:03:17 +0000

Hi Manu,

Can you give a brief description so folks can determine if they have relevant knowledge knowledge before downloading? Thank you. Robert

Comment on Tree-eval, catalytic computation, simulating time with square-root space by Bruno Loff

Bruno Loff — Tue, 11 Nov 2025 12:59:41 +0000

Yes, that's the algorithm, isn't it so simple and lovely?

For me catalytic is this ingredient where you interrupt a previous computation, use the (full) memory which it is currently using in order to do your thing, return it to its original state, and then resume the computation. But of course, you are right that Barrington/Ben-Or&Cleve are already "catalytic" in this sense, so perhaps it is unnecessary terminology.

Looking forward to teaching from your book!

Comment on Tree-eval, catalytic computation, simulating time with square-root space by Manu

Manu — Fri, 07 Nov 2025 14:17:14 +0000

Bruno, thank you very much for your comment and the pointer! Indeed I have been thinking about simple catalytic results to include. After discussing with Michal I sketched the parityL result, but I much prefer NL! I just glanced at their paper; if I understand correctly, the proof is extremely simple: for each node you have a register which will maintain the # of paths of length i arriving at that node, shifted by some unknown value. You can compute this for i = 1,2,... just going through the edges, and then you can also go back to the original unknown value. Now, if I also do this by first incrementing the register for the start node, I will see a difference only if it's connected to the end node.

Yes I am in the process of reshuffling the book. Chapters 1 - 7 are meant to be in a decent state (I maintain this info on the front page). The others are being reshuffled/absorbed.

Regarding "catalytic." What I was trying to say is that Cook-Mertz is an extension of Barrington/Ben-Or Cleve, so I find it a little odd to use the term "catalytic" for that, since it would apply just as well to the previous results. Other than that I like the term and the analogy.

Comment on Tree-eval, catalytic computation, simulating time with square-root space by Bruno Loff

Bruno Loff — Fri, 07 Nov 2025 13:45:50 +0000

The name "catalytic" is because you use the full memory as part of the computation, but then get it back at the end (like the catalyst in a chemical reaction).

From the draft for your book, which you linked above, it seems that you are still in the process of writing down chapter 11? In that case, let me suggest that you start by showing that directed reachability is in catalytic logspace using the algorithm in the following paper by Cook and Pyne: https://arxiv.org/abs/2509.06209

It is the simplest proof I know that directed reachability is in CL.

Comment on mathematics of the impossible: Revision. Feedback welcome especially on chapters 1,2,3 by Manu

Manu — Wed, 15 Oct 2025 12:41:26 +0000

Thanks! I am also not satisfied with that section.

Comment on mathematics of the impossible: Revision. Feedback welcome especially on chapters 1,2,3 by Anonymous

Anonymous — Mon, 13 Oct 2025 01:19:00 +0000

In the teaser section you begin talking about computing with 3 bits, but you shift to the MAJ problem and time and don't have a transition like

ENOUGH on 3-bits, not lets talk about power time

or something like that

bill g.

Comment on Minimalistic combat, and Sifu by Manu

Manu — Mon, 08 Sep 2025 13:13:19 +0000

Update: I am playing Brawlhalla. About the opposite of what I am looking for, seems each character/weapon combination has moves with different ranges, e.g. only upwards, or diagonal etc. and it is important to know them (?). What do you think is the deepest aspect of this game? Is it knowing the character/weapons, or something else?

Comment on Minimalistic combat, and Sifu by Manu

Manu — Sat, 30 Aug 2025 14:50:14 +0000

In reply to Bruno Loff.

Thanks. I heard of it but never tried it. Not minimalistic though. If you want a combat game that can stress you I can highly recommend sifu.

Comment on Minimalistic combat, and Sifu by Bruno Loff

Bruno Loff — Thu, 28 Aug 2025 18:00:43 +0000

There's this game, Brawlhalla, I was obsessed with, having played more than 400h of it during 2015-2016. It is very deep, to watch an advanced player (ca. 2000 hours) do his thing makes you understand just how clueless you are, even after so many hours. I made it to early platinum elo for a couple of weeks, but never again after. Eventually I quit the game because it stressed me out :-)