Monthly Archives: June 2011

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.

Continue reading


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

A Twitterish post on two blog entries about nanoscale hardware:

  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.

Distributed Computing at STOC 2011 – part two

In this post, I will discuss Distributed Verification and Hardness of Distributed Approximation, by Das Sarma and seven other authors.  I enjoyed this paper for a couple reasons: first, it highlights a major difference between “traditional” computing and distributed computing; and, second, it puts forth a research program that seems to have a lot of promise.  In a nutshell, the authors present a way to translate lower bounds in communication complexity into lower bounds in distributed verification and distributed approximation, so a straightforward technique is able to answer multiple open questions at one fell swoop. Continue reading

Distributed computing at STOC 2011 – part one

In this blog entry and the next one, I will discuss two distibuted computing papers at STOC 2011: Tight Bounds for Parallel Randomized Load Balancing by Lenzen and Wattenhoffer (this entry), and Distributed Verification and Hardness of Distributed Approximation by Das Sarma et al (next entry).  There have been at least two tracks on distributed systems at STOC, so these papers are representative, not exhaustive by any means.  I am going to start, though, with a personal note about something sad, so if you’d like to jump directly to the science, please skip the subhead below, and go directly to the next one.

Michelle Le

Michelle Le is a nursing student at Samuel Merritt College, who disappeared when leaving the hospital after rounds eleven days ago.  A good friend of mine is in the same class as Le.  Monday night, the police changed the status of the case from disppearance to homicide.  (This has been in the local California news for days; one recent link is here.)  The family is asking the public to hold out hope, despite police pronouncements that the effort is now one of recovery.  Suffice it to say that I was on a long phone call Monday night, did not sleep much or well,and  I skipped the morning session of STOC Tuesday to be with my friend.  (This was the session where the award-winning papers were presented, so hopefully someone who attended can blog about them.)  According to my friend, Michelle Le is beautiful and hilarious, and is the only student in the nursing program who is also working twenty hours a week.  (Most students are not employed, to be able to keep up with the accelerated reading load.)  So Michelle is driven and dedicated as well.  I hope she returns home very soon.

Continue reading

Turing lecture 2011

UPDATE: Video of the Turing Lecture now available here.

I am at STOC 2011, which is part of FCRC, the federation of CS conferences that meets jointly every five years.  This is far and away the biggest CS conference I have attended, and, even for STOC alone, the schedule is formidable.  The first talk was this morning at 8:30, and the (first-ever) poster session ends at 10:30 tonight.  And there are two parallel sessions.  In the past, I have mostly tried to attend every talk possible at a conference, and I am going to try something a bit different this time.  I plan to attend about half the available talks each day, and spend the rest of the time meeting people and writing blog entries about the talks I just attended.  Hopefully, I will learn more that way — and maybe people who didn’t attend will enjoy the “news reports.”

But, to begin at the beginning, the highlight of the entire federation of conferences took place last night, when Les Valiant, the 2010 Turing Award winner, gave the 2011 Turing Lecture to hundreds of computer scientists.  This talk was professionally videotaped, and I will try to remember to update this post when a link is available, but in the meantime, here are my impressions.

(Aside: Lance Fortnow and Richard Lipton have already blogged on Valiant’s winning the Turing Award.  See also this recent post by Lance that briefly mentions Valiant’s Turing Lecture.)

Valiant’s main thesis is that probabilistic machine learning is the way to address a fundamental open problem of evolutionary theory: How could organisms as complex as exist on Earth have developed after only 13.75 billion years?  If we model an extremely simple life form as a circuit, where each node in the circuit is a protein, we achieve an apparent contradiction from this seemingly quite reasonable model.  The contradiction: a complex life form alive today has perhaps 3 million genes.  There is no currently known subexponential way to build circuits for  complex functions, and yet life forms today are certainly able to solve complex functions.  Hence, it might reasonably require 2^{3,000,000} time steps to construct a complex life form, and, even if a “time step” is very small, the quantity still dominates the “mere” 13.75 billion-year age of the universe.

So Valiant’s point was that evolutionary theory is, at present, completely unable to give any rate of convergence arguments for Darwinian processes.  He took lengths to emphasize that he believes the evidence for evolution is overwhelming; he hopes to ramify biological understanding with theoretical computer science, not to point to the need for an intelligent designer.  Indeed, Valiant said the problem is the exact opposite of a “great mind” finding a “simple universe,” where, e.g., Newton or Galileo states a simple underlying concept such as the law of gravitation.  Instead, our tiny life form/circuit has no chance whatever of achieving understanding of a world that is prohibitively complex.  All it can hope to do is to get a little bit better than it was the day, or the generation, before.

The Lecture was high level, and intended for a broad audience.  Valiant gave a related talk in 2006 (slides, video),which contains more technical details.  That talk has a bug/feature that a biologist in the audience thought the approach was bogus and took the speaker to task for it, at length.  Valiant eventually just decided to stop talking.  There were no such problems at the Lecture last night, of course — though the videotapers kept putting Valiant’s image on the screen instead of the two technical slides!  So I will refer you to the slides from 2006 for technical details, instead of trying to reconstruct any Lecture specifics.

The gist: Valiant proposes that organisms learn about their environments by means of PAC learning (probably approximately correct learning, a notion Valiant defined in 1984).  PAC learning requires a “goal,” a function one is trying to learn, and it is often said that Darwinian evolution does not have a goal.  Valiant resolves this by proposing an “ideal function,” a function that has the answer to everything: given any set of circumstances as input, the ideal function outputs action X, the ideal action to take in the given situation.  Then under an evolutionary setting, circuits which better approximate the ideal function are favored to continue their line, while circuits with inferior approximations are likely to die off.  The math works out, if the ideal function and approximating functions are real-valued, and circuits can learn complex functions in subexponential amounts of time.  Hence, this provides a reasonable way to attack the problem of the rate of convergence of evolutionary processes.

As a final note, Chazelle, in his Natural Algorithms paper, provided the first-ever rates of convergence for longstanding control theory models of bird flocking, so it is allied to Valiant’s own approach.  Valiant went a step further than just saying that CS applied to other disciplines would be a good tool to obtain rates of convergence.  He noted that the parity function is not PAC-learnable, and said: People might object that the parity function does not appear in nature, but that is exactly the point; it does not appear in nature because it is not evolvable.