Educational media list, 08/15 to 08/31
Here I’m listing much of the media I’ve read/watched/listed to/etc., and learned something from. This list will cover the next half month. Generally, if I list something here I’m recommending it. If not, I’ll try to mention it.
I’m not going to give a big explanation of each item, because that’ll probably get in the way of me posting. Generally, I’m just going for media type, creator, title, possibly venue, possibly a brief description.

Review Video: Debunking Pentagon UFO Videos by Corridor Crew. VFX artists review videos of Unidentified Arial Phenomena, conclude that they are camera artifacts/birds/etc.

Experiment Video: Gauge Blocks under Vacuum by Applied Science. Gauge Blocks are highly polished metal blocks that stick together when they are pressed against each other.

Law Podcast: Pearls are in the Eye of the Beholder, by Bobby Chesney and Steve Vladek, law professors at UT Austin. Usual roundup of topics, at a really high level, very enjoyable, multiple perspectives.

Tutorial Video: Beyond WorstCase Analysis I and Beyond WorstCase Analysis II, by Tim Roughgarden at the Simons Institute. Lots of different kinds of analysis of algorithms beyond worstcase analysis. My research fits nicely in this model  adversary chooses the distribution, nature samples the distribution. I think there’s something interesting that could be done with a smoothed analysis of multiserver SRPT where arrival times/sizes have a little bit of noise.

Tutorial Video: Understanding the Empirical Hardness of NPComplete Problems I and Understanding the Empirical Hardness of NPComplete Problems II, by Kevin LeytonBrown at the Simons Institute. Followup to the above, but more heuristic.

Tutorial Video: The Mathematics of Lattices I and The Mathematics of Lattices II, by Vinod Vaikunatanathan, my Master’s thesis advisor, at the Simons Institute. An introduction to Lattice Cryptography.

Website & Game: OriMaze, by John Tromp. Also known as Unit Rush Hour. A game with very interesting and open complexity.

Book: The Scout Mindset, by Julia Galef, cofounder of the Center for Applied Rationality. Listening on audiobook. This is the best explanation of rationality I’ve seen. Much better than more famous ones.

Research Article: The Gittins Policy in the M/G/1 Queue, by Ziv Scully and Mor HarcholBalter, my frequent collaborators. The first fully general proof of the optimality of the Gittins policy in the M/G/1. Schedulingfirst, not multiarmedbanditfirst.

Tutorial Video: Hardness of easy problems, by Virginia Williams, at the Simons Institute. A gentle introduction to finegrained complexity.

Tutorial Video: Circuit Analysis Algorithms, by Ryan Williams at the Simons Institute. Apparently MajorityofXORs is a symmetric function? This isn’t literally true.

Blog Article: Crawl Doubling Damage, by Collin. In an incredibly hard game that never changes, will anyone notice if something does change?

Research Article: NEXP not in ACC, Appendix A, by Ryan Williams. I wanted to see what was up with majority of XORs. The real statement is that majority of XORs can be simulated a symmetric function of ANDs, with polylog overhead or so. For instance,
MAJ(a xor b, c xor d) = f((a+b)^2+(c+d)^2) = f(a+2ab+b+c+2cd+d)
, where f is the “not 0 mod 4” function and MAJ breaks ties towards 1. Here I’m usingx^2
as my degreeamplifying function. There are only 6 different inputs after symmetry, so this is easy to check. 
Wikipedia Article: Haven. I know understand treewidth better. A graph has treewidth at most k iff k + 1 pursuers can chase down a pursued, where the pursued can move through the graph edges, but can’t move through the pursuers’ nodes, and both sides know where the other is. Pursuers occupy k nodes while 1 pursuer moves. Tree decompositions are strategies for the pursuers, while havens are strategies for the pursued.

Tutorial Video: FPT Algorithms, by Daniel Mark at the Simons Institute.

Research Discussion: On the purported inconsistency of Peano arithmetic, by Edward Nelson and Terry Tao. Tao points out the flaw in Nelson’s proposed proof of the inconsistency of Peano arithmetic. Highlevel, polite, effective discussion.

Research essay: Two Cultures of Mathematics, by Timothy Gowers. I think a similar split between problem solvers and theory builders exists in TCS, though not nearly as severe. Also, I think problemsolvers have more representation in TCS, while theory builders dominate in math.

Tutorial Video: Prime Gaps by Terry Tao at UCLA. Very nice intro to the area.

Puzzle Video: The Legend of Question Six by Simon Pampena on Numberphile. The question, from the 1988 IMO, is “Let a, b be positive integers such that (a^2+b^2)/(ab+1) is an integer. Prove that it is a square.” I paused the video when they posed question and solved it, based on illremembered intuitions from hearing about the question previously. Lots of fun to solve that way, obviously way easier than solving from scratch.

Research Article: Gradient descent = CLS = PPAD ∩ PLS, by Fearnley, Goldberg, Hollender, and Savani. This paper is very exciting, but a bit less exciting than it sounds. PPAD, PLS, and CLS are well known and important complexity classes. This paper shows that CLS is equal to the intersection of PPAD and PLS, which was not previously known, by showing that the problem of “Find a local approximate optimum of the gradient descent algortihm” is equal to both. Note that this is not the same as the problem “sample the distribution of Gradient Descent’s output given a random initializer”, which is the algorithm people actually use in practice. But nonetheless, this is a super cool result.

Research review: Large scale quantum experiments, by Quanta Magazine. Experimenters are working on placing ever larger objects into quantum superposition. The previous record was several thousand atoms. Now, they’re working on hundreds of millions. If this works, it could probe the regime of quantum gravity for the first time.

Tutorial Video: Circuit Complexity and Connections I and II, by Ryan Williams, at the Simons Institute. Algorithms for circuit analysis and bounds on the power of circuits are very closely connected.

Blog post: More number gossip, by Tanya Khovanova, the creator of [Number Gossip])(http://numbergossip.com/).

Textbook chapter: Algebra of Orders, by Josh Hawkins. A very gentle introduction to order theory.

Blog post: Metarationaliy, by David Chapman. All about Bingard problems, which consist of coming up with good explanations for why two sets are divided the way they are. I think the nebulosity stuff is overblown and highfaluting.

Research essay: Fraud in Honesty Study, by Uri, Joe, Leif and an anonymous team of researchers. Proves that a major study on honesty was fradulent, in extensive detail. Responses from the original authors are very interesting, with none disputing the analysis.

Research Interview: [Black Hole Information Paradox Resolved] (https://www.quantamagazine.org/nettaengelhardthasescapedhawkingsblackholeparadox20210823/), interviewing Netta Engelhardt.

Tutorial Video: What makes averagecase NP problems hard? I and II Boaz Barak at the Simons Institute. From both the physics and CS perspectives.

Explanatory Blog Post: Pin and Unpin in Rust, by Adam Chambers. Explaining one of Rust’s trickier concepts.

Research Paper: Discovery of glycoRNA, by Ryan Flynn et al. Discovery of glycoRNA, RNAs with sugars attached. Previously unknown because no one was looking.

Research Blog Post: Narrowing in on Planet Nine, by Konstantin Batygin and Mike Brown. Overview of a research Article which narrows down the potential locations of Planet Nine and shows the observed clustering of asteroids is not produced by observational bias.

Educational Podcast: Dysentery, by Erin Welsh and Erin Allman Updyke. A wonderfully friendly and wellsearched podcast about disease, especially epidemic disease. This episode is similarly great.

Research Slides: Erdos’s Ternary Digits Conjecture, by Jeff Lagarias. Erdos conjectured that all powers of 2 above 256 have a 2 when written in base 3. Amenable to SAT solving?

Research Popularization: Clocks and Entropy, by Natalie Walchover. The fundamental limits of clocks.

Research Popularization: Cardinals between N and R, by Martin Goldstern and Jakob Kellner. Exploring cardinalities between that of the naturals and the reals.
Updated through 08/31.