The Descriptive Complexity of Solutions

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:

1. The problem is in polynomial time—use Gaussian elimination, with some care. See my earlier post on the bits required for solving linear systems.
2. The problem is in . That is a linear system can be solved with polynomial processors in time.
3. The problem is also easily seen to be in , the class of problems that are reducible to the determinant.
4. 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]

Does a Trillion-To-One Make Sense?

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.

Routing Forever on an Expander Graph

Can one route requests forever on an expander graph?

Noga Alon is one of greatest combinatorial experts in the world. He has won many awards and has made countless contributions to almost all aspects of combinatorics and theory.

Today I want to talk about a problem that occurred to me after listening to his talk at our recent theory day. It concerns a neat result that he has on routing on expander graphs.

Is There a Test for Consciousness?

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.

The Curious History of the Schwartz-Zippel Lemma

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.

What Are Proofs For Anyway?

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.

New Streaming Algorithms for Old Problems

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.

Nash Equilibrium for Sparse Games: Part Deux

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.

More on Mathematical Diseases

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.

Rumors and Playing Games

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.