## The SZR model of the zombie apocalypse

You’ve watched all the movies.  You’ve read all the books.  You’ve even practiced tactial skirmishes with lifesize zombie targets.  But now, all of a sudden, you are thinking, “I didn’t know there would be math!”

Actually, if you’re a regular reader of this blog, I imagine you are thinking, “I didn’t know there would be zombies.”  For those who want a math-free overview of Munz et al.‘s “When Zombies Attack: Mathematical Modelling of an Outbreak of Zombie Infection,” please see this piece by Wired.  For the rest of you, I promise Greek letters and differential equations after the jump.

Acknowledgement: I would like to thank blame this post on Dave Clarke, who brought the Munz et al. paper to my attention in an answer he gave to a question I asked about the computational theory of simulation of diseases.

## New blog: Theoretical Computer Science

Quantum computing expert Joe Fitzsimons and I have just agreed to be co-editors of the brand-new blog Theoretical Computer Science, the community blog of the TCS question and answer site cstheory.stackexchange.com.  The first post of the new blog is here.  The blog is hosted under the StackExchange network, and the graphic designer for StackExchange is expected to produce a blog theme in a few weeks.  Until then, the site will look sketchy, and we are still getting things up and running.  For example, the blog cannot process LaTeX yet, which limits our ability to publish technical posts.  I imagine we can get that resolved soon.

Our initial objective is to put out one to two posts per week: one post that is more “meaty,” by a contributor (i.e., not Joe or me!) that discusses a topic in some depth; and one post that is a review of activity on cstheory this week.  (Examples: these are the unanswered questions of the week; these are the editors’ choice of the most interesting answers to questions this week.)  We currently have commitments from four people to contribute to the blog, and we are actively looking for more participation.  Please email Joe or me, or add your name to the blog contributor  signup sheet, if you would like to be involved.  We would like to host expository material in all areas of theoretical computer science, and also more specialized discussions, that would primarily interest experienced researchers.

Edit: Math is now rendering; we appear ready to go.

## “Editor’s Selection”

My post from yesterday on the Church-Turing Thesis now bears a green-and-white checkbox icon labeled “Editor’s Selection.”  This is because yesterday afternoon, an editor of ResearchBlogging.org selected it (and two other posts, by different bloggers) as “interesting and notable ResearchBlogging.org posts in the physical sciences, chemistry, engineering, computer science, geosciences and mathematics” for this week.

I have no idea what the “acceptance rate percentage” is for this, but I figured I should explain what the icon was doing there.  I wrote one previous post about ResearchBlogging.org, when I first joined.

## A mathematical proof of the Church-Turing Thesis?

The Church-Turing Thesis lies at the junction between computer science, mathematics, physics and philosophy.  The Thesis essentially states that everything computable in the “real world” is exactly what is computable within our accepted mathematical abstractions of computation, such as Turing machines.  This is a strong statement, and, of course, if one had tried to say the same thing about natural laws and Newtonian physics, one would have a respectable thesis that turned out to be false.  (There is even a theoretical research area, hypercomputation, that attempts to show how “super-Turing” computers could be built in real life by taking advantage on non-Newtonian physics.)

When I learned the Church-Turing Thesis in school, I was told that it was a thesis, not a theorem, precisely because it was not formally provable.  The notion of “computable” was intuitive, not mathematically precise, so it was impossible to say whether a particular mathematical abstraction was the ULTIMATELY CORRECT one.  Nevertheless, in 2008, two respected researchers — Nachum Dershowitz of Tel Aviv University, and Yuri Gurevich of Microsoft Research —  did indeed publish a proof of the Church-Turing Thesis in the Bulletin of Symbolic Logic.  How is this possible?  They constructed an axiomatization of computation based on abstract state machines, a theoretical notion developed by Gurevich that Microsoft has used to perform practical software tests, and then proved that the Church-Turing Thesis held for that axiomatization of computation.  In other words, they managed to formalize the notoriously unformalizable “computation in the real world.”

This impressed me quite a bit — so much so, that when a user named Avinash asked on the theoretical computer science question and answer site, “What would it mean to disprove Church-Turing Thesis?” I answered that the Thesis had been proved for all practical purposes.  Not my finest hour, as we will see.  Fortunately, Avinash, in a feat of crowdsourcing genius, accepted my answer as correct, in order to encourage discussion.  Since then, some of the top theorists in the world have contributed their opinion of the Dershowitz/Gurevich paper, and their philosophy about the thesis overall.  I will cover some of the main points in the rest of this blog entry. Continue reading

## STOC 2011: Infinitary Ramsey Theory yields a complexity dichotomy theorem for CSPs over graphs

In this post, I will discuss Schaefer’s Theorem for Graphs by Bodirsky and Pinsker, which Michael Pinsker presented at STOC 2011.  I love the main proof technique of this paper: start with a finite object, blow it up to an infinite object, use techniques from infinitary Ramsey Theory to show that the infinite object must possess regularities, use those regularities to get complexity bounds in P and NP.

Schaefer’s Theorem

The standard version of Schaefer’s Theorem is a statement about the complexity of finding satisfying assignments for a set of Boolean relations.  It is a dichotomy theorem: either the set of relations falls under one of six cases, in which case it is solvable in $\mathsf{P}$; or it doesn’t, in which case finding satisfying assignments is $\mathsf{NP}$-complete.  As an “obvious” example, if the set of relations is not always false, but is always true if all its variables are set to TRUE, then finding a solution is (clearly) polynomial-time computable.  As a less obvious example, a set of relations that is equivalent to a conjunction of binary clauses can be solved in polynomial time.

In a sense, then, one can consider Schaefer’s Theorem to be a “ramification” of SAT-type phenomena: it explains more precisely when $\mathsf{NP}$-completeness will arise.  The intent of the paper by Bodirsky and Pinsker is to obtain a similar ramification in the setting where relations are defined over the universe of graphs, instead of being arbitrary Boolean relations.  Sure enough, they uncover a similar dichotomy — either sets of relations are tractably solvable, or they are $\mathsf{NP}$-complete.

## DNA circuit that computes square root; silicon transistors go 3D

1. On the theory side, Olexandr Isayev, a chemist at Case Western, blogs about a new paper by Erik Winfree and Lulu Qian, in which they design DNA circuitry capable of computing a square root.
2. On the practical industry side, Joerg Heber, Senior Editor at Nature Materials, blogs about Intel’s new chips that place transistors using a 3D framework, taking advantage of previously unused vertical space, so the distance between transistors is currently 22 nm, and is projected to be only 10 nm by 2015.  Wow.

## Review: Handbook of Nature-Inspired and Innovative Computing

I recently completed a review for SIGACT News of the Handbook of Nature-Inspired and Innovative Computing, edited by Albert Zomaya.  The full review is here.  Below is the introduction to the review.  I enjoyed reading the book.

The ambitious goal of the Handbook of Nature-Inspired and Innovative Computing is to “to be a Virtual Get Together of several researchers that one could invite to attend a conference on ‘futurism’ dealing with the theme of Computing in the 21st Century.” The Handbook contains 22 chapters, written in a “workshop style,” meaning that little to no background is required from the reader except for basic knowledge of computer science, and the chapter authors provide an overview of a particular research area. The material is divided into three sections: Models (i.e., theory), Enabling Technologies (i.e., hardware), and Application Domains (i.e., recent, novel applications of computer science). Most of the chapters present either theoretical models (fuzzy logic, quantum computing, swarm intelligence) or report on trends in non-von-Neumann-model hardware (morphware, optical VLSI, neural models in silicon). Overall, I found this volume to be a fascinating, and gentle, introduction to a wide range of nonstandard research areas of computer science.