"Next post (or two, or three): More on Steve Frank’s paper: Understanding distributions via their information content, and the method of maximum entropy. Our cast of characters widens to Poisson, Exponential, and Gamma distributions. Where power laws come in. What all this has to do with scaling, and why we should care."

"In my next several blog posts I want to talk about scaling, especially about the very recent controversies surrounding claims of power-law scaling of particular phenomena [...] All this is going to require some forays into the wild and unruly land of statistics and data analysis. My goal in the next series of posts is to make sense of the following quite important papers in complex systems, which, taken together, form a kind of mini-course on scaling. Understanding ideas from these papers is essential in one’s education as a complex-systems scientist or informed “consumer” of this field."

"“To put it bluntly: this book rocks! It's 900+ pages of awesome. It somehow manages to combine the fun of a popular book with the intellectual heft of a textbook, so much so that I don't know what to call it (but whatever the genre is, there needs to be more of it!).” —Scott Aaronson" (ok, i'm sold!)

"Me thinks the gentleman doth protest too much. In my opinion, Dennett, and some others who adhere to a strict Darwinian adaptationist program, may be trying to find in nature a nonexisting pattern that shows us—Homo sapiens—as the nearly inevitable result of evolution. Dennett's crane of relentless natural selection is, for him, a skyhook—"a 'mind-first' force or power or process" that, run over and over, would produce us again and again."

"In this paper, we use tools from Kolmogorov complexity and algorithmic information theory to show that sampling and search problems are essentially equivalent. More precisely, for any sampling problem S, there exists a search problem RS such that, if C is any "reasonable" complexity class, then RS is in the search version of C if and only if S is in the sampling version."

"But there is one compensating advantage for the people who escape the old system: when the ecosystem stops rewarding complexity, it is the people who figure out how to work simply in the present, rather than the people who mastered the complexities of the past, who get to say what happens in the future."

"I present many new results on sample complexity bounds (bounds on the future error rate of arbitrary learning algorithms). Of theoretical interest are qualitative and quantitative improvements in sample complexity bounds as well as some techniques and criteria for judging the tightness of sample complexity bounds. On the practical side, I show quantitative results (with true error rate bounds sometimes less than 0.01) for decision trees and neural networks with these sample complexity bounds applied to real world problems. I also present a technique for using both sample complexity bounds and (more traditional) holdout techniques. Together, the theoretical and practical results of this thesis provide a well-founded practical method for evaluating learning algorithm performance based upon both
training and testing set performance."

"This page documents the time-complexity of various operations in current CPython. "

"To read more about metabolism and power laws, see chapter 17 of Complexity: A Guided Tour."

"Our findings indicate that, before controlling for size, the results are very similar to previous studies: The metrics that are expected to be validated are indeed associated with fault-proneness. After controlling for size, none of the metrics we studied were associated with fault-proneness anymore. This demonstrates a strong size confounding effect and casts doubt on the results of previous object-oriented metrics validation studies. It is recommended that previous validation studies be reexamined to determine whether their conclusions would still hold after controlling for size and that future validation studies should always control for size."

"Today's deep thought is: how much of modern computer science is about making the complexities in our world simpler and more understandable - and how much is making the world more complex and more opaque? And how complicated can a system be and still be controlled, maintained, and regulated by human beings?"

"A knowledge representation system provides an important service to the rest of a knowledge-based system: it computes automatically a set of inferences over the beliefs encoded within it. Given that the knowledge-based system relies on these inferences in the midst of its operation (i.e., its diagnosis, planning, or whatever), their computational tractability is an important concern. Here we present evidence as to how the cost of computing one kind of inference is directly related to the expressiveness of the representation language. As it turns out, this cost is perilously sensitive to small changes in the representation language. Even a seemingly simple frame-based description language can pose intractable computational obstacles."

"In this chapter, I review the main methods and techniques of complex systems science. As a first step, I distinguish among the broad patterns which recur across complex systems, the topics complex systems science commonly studies,
the tools employed, and the foundational science of complex systems. The focus of this chapter is overwhelmingly on the third heading, that of tools. These in turn divide, roughly, into tools for analyzing data, tools for constructing and evaluating models, and tools for measuring complexity. I discuss the principles of statistical learning and model selection; time series analysis; cellular automata; agent-based models; the evaluation of complex-systems models;
information theory; and ways of measuring complexity. Throughout, I give only rough outlines of techniques, so that readers, confronted with new problems, will have a sense of which ones might be suitable, and which ones definitely are not."

"This page collects links around papers that try to settle the "P versus NP" question (in either way)." ... the not-equals have it; decided.

"NetLogo is a cross-platform multi-agent programmable modeling environment. NetLogo is a programmable modeling environment for simulating natural and social phenomena. NetLogo is particularly well suited for modeling complex systems developing over time. Modelers can give instructions to hundreds or thousands of "agents" all operating independently. This makes it possible to explore the connection between the micro-level behavior of individuals and the macro-level patterns that emerge from the interaction of many individuals."

"I decided to piece together a program that creates the diagrams automatically for Java classes.  It uses BCEL to grok class files, then it produces a dot file that can be piped into Graphviz. ..I'll release it soon."

nice. analyzing complexity of hadoop's codebase using an architecture visualization tool, structure101.

"Mirowski ..for twenty years ..working through ..forms that economics shares with physics, biology and computer science. ..latest project ..approach to economics ..markets conceived as evolving computational entities (markomata, a wordplay on automat

"resources for exploring the intersections between self-organization in science (complexity theory, cellular automata, animal flocking, molecular self-assembly, etc.) and self-organization in society (online communities, self-managed commons, anarchist po

Universal Selection Theory and the Second Darwinian Revolution

This is the first of a long series of posts giving an informal introduction to computational complexity.

One page explanation and links.