complexity

Physicist Geoffrey West speaks at an FQXi conference on time about complexity and scaling laws. He covers how metabolism, growth and lifespan scale across organisms and how the same mathematics applies to cities and companies.

Tom Murphy's satirical SIGBOVIK 2007 presentation, delivered under a pseudonym, proving that generalized Super Mario Bros. is NP-complete. It is a short, deadpan take on a complexity theory result.

Find the Longest Path is a comedic song by Daniel J. Barrett, a Billy Joel parody that describes the NP-hard longest path problem in informal terms.

Jim Weirich's RubyConf 2012 talk derives the Y combinator step by step, live-coding in Ruby lambdas. It builds up an understanding of functional programming and lambda calculus from first principles.

Meredith Patterson and Sergey Bratus argue that networked software stays insecure because protocols and inputs are too complex to recognize safely. They propose using formal language theory and grammars to build secure, verifiable input handling.

Christopher Domas's Derbycon 2015 talk on the M/o/Vfuscator, a compiler that emits only x86 mov instructions, showing mov is Turing complete. It explains how a full machine is built from mov and why the output is a nightmare to reverse engineer.

Scott Meyers' keynote at DConf 2014, drawing on 25 years of C++ experience to offer the D language community a plea about what it should avoid. It centers on the accumulated complexity and pitfalls of C++ as a cautionary tale.

Tom Stuart's Ruby Manor 3 talk builds FizzBuzz using nothing but Ruby lambdas, working through Church encodings of numbers, booleans and data structures. It is a hands-on introduction to lambda calculus.

David Beazley's PyCon 2019 tutorial derives the lambda calculus from the ground up in Python, using only single-argument functions. He builds booleans, numerals and more with no other language features.

Matt Might's Curry On talk on ending errors in code, both software and the human genome. He covers conservative approximation of the halting problem via static analysis and a computational approach to precision medicine.

A panel with Tony Hoare, Joe Armstrong and Carl Hewitt, hosted by Francesco Cesarini, on the history and future of concurrency. The three creators of CSP, Erlang and the actor model discuss their differing approaches.

The first video in a series on extremely large numbers, introducing the topic with examples. Later parts go deep into the fast-growing hierarchy.

Scott Aaronson's Harvard CMSA talk traces what mathematical truths are knowable, from Godel and Turing to the Busy Beaver function. He covers recent work on Busy Beaver values.

A short demo of a playable Space Invaders game built inside Dwarf Fortress, with a downloadable map. It shows the game's mechanics used as a computing substrate.

Stuart Halloway's satirical talk describes how to protect yourself from industry change by spreading complexity through systems while following idiomatic practice. It uses this inversion to catalog software design anti-patterns.

Yehuda Katz's Railsberry 2012 talk on why Rails is hard to learn and use. He explains that the framework's many features reflect real complexity in web applications that newcomers do not yet see.

Armin Ronacher, creator of Flask, explains how CPython's internals and C API leak into the language's semantics. Using examples like the complexity of the add operation, he shows why Python is hard to optimize or reimplement.

Sam Stephenson's RailsConf 2016 talk on Turbolinks 5, showing how small teams can ship fast Rails apps in the browser and hybrid iOS and Android apps sharing one set of web views.

Alan Kay speaks at the DEMO Founder School session on why real progress takes invention rather than incremental innovation. He argues for problem-oriented thinking and long-term research funding.

Conal Elliott presents his paper on automatic differentiation, deriving a simple, generalized AD algorithm from a natural specification. Varying the representation of derivatives yields forward and reverse mode algorithms that avoid the complexity and statefulness of backpropagation.

John A. De Goes's Scalapeno keynote argues that Scala's popularity is declining because of compile times, complexity and compatibility problems. He proposes a path for Scala to survive, including a simplified functional subset.

Nicholas Zakas of Yahoo discusses architecture for large, modular JavaScript web applications. He lays out the theory behind building front ends that scale in complexity.

Aaron Boodman of Replicache asks why sync engines have not yet fixed web app complexity and what is missing for them to go mainstream. The talk lays out the ideas that led to the Zero sync engine.

A 36C3 talk that systematically evaluates OpenBSD's exploit mitigations, asking how effective they really are and what they cost in performance, complexity and inspectability. It challenges the project's security marketing.

Adam Tornhill's GOTO Copenhagen 2019 talk on how to prioritize technical debt in large codebases. It argues for combining code complexity with change frequency (hotspots) from version control data, rather than trying to quantify debt in the abstract.

Nicolai Josuttis's CppCon 2018 talk walks through the many forms of initialization in C++, including uniform initialization, and how their rules and effects differ. He argues the situation is confusing enough that nobody can say what to teach beginners.