Kolmogorov Complexity and Causation
24 May 2018 | 3:18 pm


I got an interesting email question.
Suppose I give you a set of points S of the form (x,y). He suggested ideally they would be pairs of a real numbers. Supposing there is a causal relationship between x and y of some kind, we want to know know if it is more likely that the x value causes the y value or the y value causes the x value. One plausible way to decide what the answer should be is by answering the question is the length of the shortest program which maps the x values to their y values shorter than the length of the shortest program which maps the y values to their x values.
So, my intuition says that this is clearly undecidable. I'm actually having a hard time thinking of a proof, so do you happen to know of one or if this problem might actually be decidable?
On a related note, since I'm already writing you about this question, do you happen to know about the complexity of any related questions which involve circuit size instead of program length? 
Let's use notation from Kolmogorov complexity, letting C(x|y) be the size of the smallest program that takes y as input and outputs x. Now suppose it is decidable to determine whether C(x|y) > C(y|x). Then find an x of length n such that for all y of length n/3, C(x|y)>C(y|x). Such x exist: For any random x, C(x|y)>= 2n/3 and C(y|x) <= n/3.

Now I claim C(x)>=n/4 for the x you found. If not we have C(x|y)<=C(x)<n/4 but for some y, C(y|x)>=n/3 since there aren't enough shorter programs to cover all the y's.

Since there is no computable procedure to find x such that C(x)>=n/4, there can't be decidable procedure to determine whether C(x|y) > C(y|x).

But does this question relate to causality. Pick a random x from strings of length n and y at random from strings of length n/3. We have C(x|y) >  C(y|x) even though there is no causality.

Instead you could look at the information of y in x, how many bit of x does y help describe, defined by I(y|x) = C(x)-C(x|y). This measure correlation since I(y|x)=0 iff x and y are independent but symmetry of information gives I(y|x)=I(x|y) so no hope for causation.

In short, Kolmogorov complexity won't give you much on causation--you can't avoid the controlled experiments.

For your last question, there is a notion of Kolmogorov complexity that roughly corresponds to circuit size, KT(x|y) defined as the sum of the program size and running time minimized over all programs p that take y as an input and output x. I'm guessing it's hard to determine if KT(x|y) < KT(y|x) and you could probably show it under some assumption like secure psuedorandom generators. Also symmetry of information isn't believed to hold for KT complexity so maybe there is something there. Interesting questions.

COMPUTER PROOF vs computer proof- Quadratic VDW theorem
21 May 2018 | 2:44 am

Quad VDW Theorem: For all c there exists W=W(c) such that for all c-colorings of {1,...,W} there exists a,d such that a and a+d2 are the same color.

What is known about W(c)?

The first proof of Quad VDW was nonconstructive.

The second proof was constructive but used VDW's theorem and gave terrible bounds, even for W(2).

EASY: Show W(2)=5

ON A HS MATH COMP: Show that for all 3-colorings of {1,...,2003} there exists two numbers a square apart that are the same color.

One can get a bound less than 100.

With a lot more detailed work one can get W(3)=29.

None of above was done with a computer.

SO- what about W(4)?  There are three proofs that W(4) exists:

a) Prove the QUAD VDW theorem. This gives terrible bounds.

b) I had some students use SAT solvers and they obtained W(4)=58. I am sure they are right and I am glad to know it (especially since it confirms the general mantra that the bounds from proofs in Ramsey theory tend to be much bigger than the reality) but its somehow unsatisfying. I want a HS proof. I wanted to put it on the MD Math Comp for 2017 but wiser people prevailed.

c) I gave the problem to a Grad Student Zach Price and he came up with a HS proof-- sort of.  Look at the following graph: here.  It shows that in any 4-coloring of N which does not have two numbers a square apart the same color:

COL(x) = COL(x+290085289)

from this one can obtain

W(4) ≤ 2900852892  (which is MUCH better than the bound from the proof of Quad VDW) and hence a proof of QVDW that does not need a program, except that to FIND this gadget used a program.  I doubt a HS student could do this on an exam.

Is Zach's proof the HS proof I am looking for?

PRO- once you see it its easy to verify and does not need a program.

CON- coming up with it needed a program.

More to the point: which proof do you like better:

1) The SAT Solver proof.  Not a proof you can see or feel, but gives exact bounds.

or

2) Zach's gadget proof. Much worse bound but you can see and feel the proof, and verify it after you know the gadget.

I prefer Zach's proof.



The Complexity of the Firm
17 May 2018 | 12:37 pm

In 1937, a year after Turing had his seminal paper, Ronald Coase published a paper The Nature of the Firm to give a framework to why we have companies and how large they become. In a perfect market economy we shouldn't need a firm at all, everyone is just an independent contractor and market pricing will drive efficient use of labor. Coase notes there are costs to creating contracts and one can gain efficiencies by avoiding these contracts by having both parties inside the same organization.

Much of those costs come from complexity, it is impossible to create a contract to cover all possible outcomes and thus contracts are incomplete leading to loopholes and lawsuits.

In the other direction, having the central organization of a firm has its own costs, from inefficiencies from not using markets to balance supply and demand, to the complexity of the organization processes themselves. In Coase's model, a firm grows to a size that balances the organization and contract costs at the margin.

So what happens to the sizes of firms when we reduce complexity, as happens with modern computing, from better communication, optimization and data analytics. We see relatively new companies like Google and Amazon getting larger. We also see a number of startups and small companies with very few workers, sometimes just one.

Computing drops both the cost of central organization and the cost of contracts so the size of a firm depends on circumstance. One can have a tech startup with a small number of workers since they can write apps that run on other people's platforms (like web browsers and on phones) and have the processing done on the cloud where they can scale or not scale as needed. Meanwhile a large company can more easily coordinate and connect using modern technology making it cost efficient to expand.

As we enter a new age of machine learning and automation, how will that affect the very nature of companies in the future? How about universities, a special kind of firm in itself? How can we harness the tools and ideas from computational complexity to help understand these and other societal changes.


More News from this Feed See Full Web Site