A circuit based model of descriptive complexity
Andrey Kolmogorov was one of the greatest mathematicians of the last century. He created whole new areas of mathematics, he created new directions in existing areas, and he solved long standing open problems.
Today I wish to talk about a problem, that is related to his notion of complexity of a string—Kolmogorov Complexity. The problem I am interested is a natural problem, but would have strong consequences if we could solve it.
Kolmogorov is famous for his model of the complexity of a string as the length of the shortest program that can generate the string. Thus, the string of length
has complexity , while a “random” string
has complexity close to .
One of Kolmogorov’s great results was the partial solution of Hilbert’s Thirteenth problem, which was completed by his great student Vladimir Arnold. The final result was again done by Kolmogorov. He is reported to have said that proving this theorem was one of the most technically challenging proofs of his entire career.
This remarkable result it shows that conventional wisdom can be wrong, since David Hilbert appeared to believe that his Thirteenth problem would go the other way. There is some issue of exactly what Hilbert intended as the statement—so it is unclear if conventional wisdom was or was not overturned.
The final theorem that was proved by Kolmogorov states:
Theorem: For each
, there exists
continuous functions such that every continuous function
is represented as
where the
are continuous functions.
The import of the theorem is that for continuous functions there is no function of many variables. Note, the theorem shows that any function of variables can be expressed using only unary functions and addition. The only multi-variable function needed is addition, which seems surprising.
Let’s turn to talking about the complexity of strings from a slightly different point of view.
A Classic Problem
Let me introduce our complexity notion by looking at the problem of solving a linear system of equations,
where is a
by
integer matrix and
is an integer vector. This is, of course, a classic problem: find an
so that (1) is true, if one exists.
For this classic problem much is known, yet some questions remain open:
- The problem is in polynomial time—use Gaussian elimination, with some care. See my earlier post on the bits required for solving linear systems.
- The problem is in
. That is a linear system can be solved with polynomial processors in
time.
- The problem is also easily seen to be in
, the class of problems that are reducible to the determinant.
- It is not known if the problem lies in lower complexity classes such as
.
How Do We Describe A String?
Instead of Kolmogorov’s general notion of the complexity of a string, we will use a particular notion based on circuits. Suppose that is a circuit and
is a string. Say that
describes
if for all
,
Let us use to denote this. We will use the size of the circuit
to measure how complex the string
is. Denote the size of the smallest circuit
that describes
as
.
This is a natural generalization of the notion of sparse. Clearly, if a string is sparse, then there is a small circuit so that
. More precisely,
Lemma: Suppose
is a string of length
with at most
1’s. Then, there is a circuit
so that
and the size of
is
. Thus,
For general circuits , this notion was addressed by Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger in their paper Power from Random Strings, where they proved it polynomially equivalent to their modification of Leonid Levin’s variation of Kolmogorov’s original idea. See also this recent paper. However, we are interested when
has additional properties, such as being a constant depth circuit of threshold gates.
Describing a Solution
Consider the linear system again,
where is an
by
invertible integer matrix and
is an integer vector. The twist is that now we limit
and
to have
description complexity of at most
.
The key open question is simple: is there a solution to the linear equation so
This does not ask for an algorithm to find the solution , but asks how complex it is to describe a solution.
By Kolmogorov’s original notion, there is one solution that has a particularly short description. It is the unique in the solution space that minimizes the Euclidean distance to
. The description of
can take our size-
circuit describing
and
, but then it appears we need to do iterative calculations to compute
exactly or to a desired precision. The iterations are not so easy to describe—not by a constant-depth circuit. So can we describe this
, or some other solution
, another way?
The issue resembles that of computational depth. We have a very short description, but it is computationally substantial to “unpack,” hence deep. We want a description that is literally less deep to unpack. Where we are being “fair” is we only ask this for equations that are themselves not deep to specify. Those equations come from translating nondeterministic logspace Turing machines and their counting functions into linear algebra.
Describing an Approximate Solution
Consider the same linear system again. Given an can we describe a solution
so that
where
I can weaken this question even further, but let’s leave that for another time.
Open Problems
If one can show that the last question can be answered in the affirmative, with variously restricted circuits describing the solution, then Ken Regan and I believe that we can prove new complexity class separation theorems. More on this in the future.
[fixed some typos]
Do statements about DNA tests make sense?
Nancy Grace is not a theoretician, of course, but was one of the original anchors on Court TV. This channel used to broadcast criminal trials live, and Grace was one of their best commentators—in my opinion.
Today I want to talk about the use of probabilities in trials and in other non-technical areas. I think that there is an interesting theorem that can be proved, but I am unable to exactly formulate it. Perhaps you will be able to help.
read more…
Blum discussed a theory of consciousness recently and this is a follow-up
Manny Blum is one of the great leaders of the theory community. He is a Turing Award winner; was the Ph.D. advisor to some of the top leaders in the field; is the creator of whole parts of theory—from Blum complexity, to algorithms of all kinds, to the theory of pseudo-randomness, to much more; and is one of the true visionaries of the field. There is only one Manny Blum.
Today I would like to talk about his recent presentation before FOCS 2009 on “what is consciousness?” I have no answer, but I have thought about his provocative talk and have a question that I would like to share.
read more…
On the discovery that randomness helps exponentially for identity testing
Jack Schwartz was one of most famous mathematicians who worked in the theory of linear operators, his three volume series with Nelson Dunford is a classic. Yet he found the time, the creative energy, and the problem solving ability to make seminal contributions to many diverse areas of science—not just mathematics or theory—but science in general. He worked on, for example: parallel computers, the design of new programming languages, fundamental questions of computational theory, and many more wonderful problems from a wide range of areas. He is greatly missed by our community as well as all of science.
Today I want to talk about the Schwartz-Zippel Lemma. Or the Schwartz-Zippel-DeMillo-Lipton Lemma. Or the Schwartz Lemma. The whole point is to discuss the curious history of this simple, but very useful result.
read more…
How to make a polygon convex and how not to prove it
Paul Cohen was one of the great logicians of the last century, who won the Fields Medal in 1966 for this brilliant work. He, of course, revolutionized set theory when he proved that the Axiom of Choice and the Continuum Hypothesis were both unprovable in the standard formal system called Zermelo–Fraenkel Set Theory. The theory’s history is a bit complex—but the main creators were Ernst Zermelo and Abraham Fraenkel.
Today I thought, with our Thanksgiving Holiday coming up, I would have a short discussion of “why we prove theorems?” It is related to Cohen, and contains a “tasty” result about polygons that I thought might be a good pre-holiday story.
read more…
A streaming algorithm for the classic Dyck language
Claire Mathieu, previously Claire Kenyon, is an expert in the design and analysis of algorithms, which should be no surprise since she worked as a graduate student with two of the world’s best—Philippe Flajolet and Jeffrey Vitter. Claire has done and continues to do some very pretty work on all aspects of algorithms.
Today I plan to talk about a recent paper of Frédéric Magniez, Claire Mathieu, and Ashwin Nayak on streaming algorithms, and how it relates to work that was in vogue years ago.
read more…
How to find approximate Nash equilibrium for sparse games
Constantinos Daskalakis is one of the experts in modern game theory, especially the structure of Nash Equilibrium for non-zero sum games. He has written a wonderful paper with Christos Papadimitriou On oblivious PTAS’s for nash equilibrium. Also see his nice survey for more information.
Today I want to talk about Costis and Christos’ paper as it relates to sparse games. This is another example of the Iceberg Effect: their paper has a beautiful result on game theory, but I missed another of their results.
A summary of some your ideas on mathematical diseases

John Conway is a world renowned mathematician, who defies a simple description. He has worked on countless games, puzzles, and easy to state, but often hard—if not impossible—to solve problems. These range from his classic game of Life, to his work on Surreal numbers; from his work on polyhedra, to his special notation for huge numbers. At the same time he has made deep contributions to many, if not most areas, of modern mathematics: from group theory, to number theory; from algebra, to geometric theory. There is only one John Horton Conway.
Today I want to talk about some of the mathematical diseases that were raised by those who were kind enough to comment on my previous discussion.
read more…
A rumor from FOCS on approximate Nash Equilibrium is partially true

Paul Spirakis is a senior researcher who has made many important contributions to theory. He has hundreds of publications that cover many areas of theory. What is so impressive about Paul is that he has been able to blend theory and practice in a very fruitful way. This is a pretty unique skill that few have.
Today I want to talk about a new result of his on finding approximate Nash Equilibrium for non-zero sum games.
read more…









