Make schools safe again

Here’s an interesting piece on gun violence, worth reading.

These days I am playing a lot of Fortnite (I managed to get to gold in ranking, but naturally it’s a completely hopeless battle, plus I play with controller instead of mouse and keyboard). I have been thinking of two ways in which media promotes gun culture. The first one is the obvious realistic gore and splatter, dead bodies everywhere, well-known at least since the Iliad. The second is more sneaky, and that’s what’s used in Fortnite. You don’t show any blood, instead you mix war with emoji, toy weapons like slingshot, and general cartoony themes, so you get a teen rating, and familiarize everybody with the differences between a shotgun, an msg, an assault rifle in terms of ranges, reload times, and spread. You know, it might come in handy.

The Simpsons, S02E09 – “Itchy & Scratchy & Marge” has a hilarious exchange about the responsibility of media in violence. I can’t find the text online, but basically, the fact that there was violence before cartoons is put forth as a startling discovery which obviously invalidates any link between media and violence. Worth watching.

Symmetric Distributions from Shallow Circuits

Another cool recent work on sampling: Kane, Ostuni, and Wu have recently posted a neat characterization of the symmetric distributions that can be approximately sampled in NC^0: A symmetric distribution can be sampled iff it’s a combo of i.i.d. with dyadic bias a/2^i, and uniform with sum = b mod 2, for various a,b.

This result is related to a recent work that Horacsek, Lee, Shinkar, Zhou and myself have recently posted. We show that any product distribution with dyadic weights can be sampled in NC^0 using a number of input bits that is close to the entropy of the distribution. This can be thought of as a local version of Shannon’s coding theorem (specifically, the decoding of the source can be done locally).

There is no shortage of questions, can we generalize these results to other models and distributions?

Returning to the first paper I mentioned, a couple of comments on the write-up (in case you read it):

  1. Their opening sentence makes me happy that I wrote myth-creation-the-switching-lemma
  2. For my perspective on sampling and especially the relationship with some previous works see this.

Sampling Permutations is Hard

Today I woke up a little earlier than usual, and now I know why: Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov have just posted what looks like an amazing paper. They prove a sampling lower bound for permutations, something which had resisted many attacks. I suspect their result introduces new techniques in the area which will find more applications. In a nutshell, a uniform permutation locally looks like a uniform function. Because a uniform function is easy to sample, it is hard to prove a lower bound. We did have lower bounds for *non-adaptive* samplers of permutations, and also lower bounds for *adaptive* samplers of other functions (all this is discussed in their paper), but due to the proximity to a uniform function, the techniques broke down for adaptive samplers of permutations. My reading list keeps growing…

Tree-eval, catalytic computation, simulating time with square-root space

A series of exciting papers [CM24, Wil25, Sha25] shows how to simulate time t on a multi-tape machine in space about √t. This simulation was already known for 1-tape machines (did you know?), and it still isn’t known for RAMs (=Time). The result for 2 tapes is significant, as we know less about this model, for example we don’t have strong lower bounds.

The first paper to state this simulation is [Wil25], but a similar simulation follows easily from [CM24], as pointed out in [Sha25]. This is all presented in my book, see Chapter 7. Specifically, [CM24] gives a simulation of what I call word circuits (they don’t talk about word circuits, but tree eval, possibly one reason why this connection wasn’t realized before). Any circuit of size s can be turned into a word circuit of depth s∕b with word size b by dividing the gates into blocks of b. Now apply [CM24] to give a space-efficient simulation. Multitape machines are a special case of circuits by previous simulation (also in my book).

This gives a simulation in space about s2∕3. A relatively simple transformation of the circuit gets you space √s [Sha25]. This is all for non-uniform space algorithms; I haven’t thought much what happens for uniform but I don’t see a roadblock.

Returning to [CM24], the term “catalytic computation” is often used but I don’t find it useful.  [CM24] is a brilliant extension of some of my favorite results [Mix89, BC92]. The exposition in my book puts it in this context.

References


[BC92]    Michael Ben-Or and Richard Cleve. Computing algebraic
formulas using a constant number of registers. SIAM J. on
Computing, 21(1):54–58, 1992.


[CM24]   James Cook and Ian Mertz. Tree evaluation is in space o(log n
⋅ log log n). In STOC, pages 1268–1278. ACM, 2024.


[Mix89]   David A. Mix Barrington. Bounded-width polynomial-size
branching programs recognize exactly those languages in NC1. J. of
Computer and System Sciences, 38(1):150–164, 1989.


[Sha25]   Yakov Shalunov. Improved bounds on the space complexity of
circuit evaluation. arXiv preprint, 2025.


[Wil25]   Ryan Williams. Simulating time in square-root space. Electron.
Colloquium Comput. Complex., TR25-017, 2025.

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

I have been working on a major revision of the book, to be published by Cambridge University Press. The latest Sep 29 version is here. Chapters 1,2,3 (Time, Circuits, Randomness) have been rewritten almost from scratch. Feedback on those is especially welcome. Some later chapters have been revised as well, and some others are in a confused state and I am still working on amalgamating them, but I kept them for reference.

Some major changes include no mention of Turing machines (called tape machines). All the theory is developed for word RAMs (called word programs). Tape machines appear only much later in the book as a restricted model. (Word programs have always been the main model in this book, but in the previous version of Chapter 1 I was still discussing tape machines as well; I am grateful for the stark comment of an anonymous reviewer that rekindled my desire to focus entirely on word programs.)

The chapter on randomness uses different problems and proofs that require minimum mathematical background. (Similar story here.)

Let me know what you think. The plan is to keep releasing revised versions of chapters in the next few months.

I beat sifu, and more on minimalistic combat

I just beat Sifu. The last boss was hard. I got there with about my actual age, so it was sort of personal that I could still beat Yang. (In Sifu your character ages when you lose, and it’s game over at 70, I hope this is one of the more unrealistic aspects of the game; I enjoyed this mechanism). It took many trials, and I had to carefully study his timings and moves. But in the end, the experience has confirmed my thoughts in the previous post, that we need to rethink combat systems to make them much more fun and engaging. Strong as he was, Yang was stupid. He should have noticed that after a specific combo, I was almost always able to land a few hits. This made the fight quite dull, in the end.

So I am planning to update my scratch game to better illustrate, and the next step would be to put some AI in it, for which I guess I need to port it to C++ or something, I suspect it’s not easy to do that in Scratch.

Liable man

We have witnessed the demise of homo sapiens and the emergence of liable man. The distinctive features of homo sapiens — creativity, adaptivity, empathy, intelligence — have been replaced in liable man with a single function: delivering utterances and performing actions that are in compliance with laws and regulations, to shift any possible blame and avoid liability. This replacement has had a fleeting evolutionary advantage which is ending imminently, with digital expert systems rendering liable man obsolete.

The ancestor of Liable man is the thrifty and servile bureaucrat. But in his current invasive form he has taken over every human profession. Doctors, principals, real-estate agents, contractors, have all but morphed into a slow interface for consulting laws and regulations, providing no added value but significant attrition. Liable man answers the question “What would you do if it was your life” with brief, affected sympathy, then doubles down playing by the playbook. He turns communities into lifeless towns of suspicious zombies, where all services are outsourced.

Be the change, volunteer in your community, add value, or be pointless.

Minimalistic combat, and Sifu

Click to play the game https://scratch.mit.edu/projects/1172034203/

carview.php?tsp=

These days I am playing Sifu, on a PS5, on a huge projected screen. The game is so amazing that it is easy to forget all that I am about to write and just enjoy the game.

Still, it is sad that such a great game hasn’t quite been able to revolutionize combat systems. Some obviously annoying things:

  1. Enemies perform combos in the air. The enemy starts a combo, I dash 20 feet away, and then the enemy still has to finish the combo hitting the air? That’s even more unrealistic than me taking on 20 bad dudes armed with machetes.
  2. Your frenetic opponents suddenly freeze just to watch you execute a lengthy and complex finish combo.
  3. More generally, the AI is average (i.e., poor): the enemies are very predictable, even though the game isn’t easy (When I played God of War some years ago, I set the difficulty to maximum and beat it straight, without thinking twice. I tried to play “maestro” with Sifu but I was forced to go back to “normal” difficulty… at least for the time being.)

This has reminded me of one project that I have been thinking about forever, on and off, without ever giving it any serious thought. If you are a student who like me likes gaming, especially combat games, and is looking for a crazy project, this could be for you.

An obvious approach is to use some heavy hammer like deep learning and see if you can get better AI for the characters with their existing moves. I am not sure to what extent this has been tried and I’d be interested in references. But here I am looking for something a little different.

In short, I ask what is a simplest combat system where people can be consistently ranked and exhibit different gaming strategies; as for example in chess, where people are ranked, and players play differently, some are more aggressive than others, and so on. Also, I’d like to be able to train AI to perform like humans, at various levels and exhibiting different strategies.

I am thinking something extremely basic, like rock-paper-scissors but based less on chance and more on skill and in particular reflexes and speed, or bullet 1-d checkers, but more like combat. Perhaps, a system involving only two moves (high or low attack) and maybe a parry. Skill could be a matter of memory (like, players incrementally build their combos, and the opposite player has to parry in the right sequence) or a matter of reflexes (like, moves get faster and faster, the player with the fastest reflexes will prevail) or a matter of precision (like you need to get exactly the right distance), or obviously some combination of this.

I coded up such a minimalistic combat that you can play at top. As time passes the moves get faster and faster. So it’s your guess when enough time has passed and you think your attack can’t be blocked. The action could look like opponents studying each other, waiting for the right time to strike. You can either parry or strike. Being hit halves (or something) your speed, parry multiplies by 1.5 (or something). Both parrying and attacking cost you speed. First to go below a threshold loses. As always, any comment is very much appreciated.