Thursday, May 24, 2018

Kolmogorov Complexity and Causation

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.

Sunday, May 20, 2018

COMPUTER PROOF vs computer proof- Quadratic VDW theorem

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.


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.

Thursday, May 17, 2018

The Complexity of the Firm

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.

Monday, May 14, 2018

What does it mean for a student to guess an answer?

On my final in Aut Theory I wanted to ask a TRUE/FALSE/UNKNOWN TO SCIENCE
question but did not want them to guess. Hence I had +4 for a right answer, -3 for a wrong answer.
Here is the question:

For each of the following say if its TRUE, FALSE, or UNKNOWN TO SCIENCE. No Proof Required BUT you get +4 for every right answer and -3 for every wrong answer and 0 for an answer left blank. So

                DO NOT GUESS!!!!!!!!!!!!!!!!!!!!!!!!!!!

a) If A is regular and F is a finite set then A UNION F is regular.

b) If A is in P and F is a finite set then A UNION F is in P.

c) If A is in NP and F is a finite set then A UNION F is in NP.

d) If A is decidable and F is a finite set then A UNION F is decidable.

e) If A is undecidable and F is a finite set then A UNION F is undecidable

Note that they are all TRUE. A student who (as many did) answered T-T-T-T-F had the following conversation with me:

BILL: You guessed! I told you DO NOT GUESS!!!!!!!!!!!!

STUDENT: No. I REASONED that you would not make them all T, so by this reasoning the last one had to be F. I now see that my reasoning is wrong--- you would make them all T, but it was not guessing, it was reasoning.

                I claim the student was guessing, he claims he was not. What do you think?

Having said that, the following IS a rational strategy:

If I don't know the answer but it has nothing to with P vs NP then it has to be T or F. In this case guess since exp val is positive.  If the answer has to do with P vs NP then do not guess.

This also raises a question- if they honestly thought (say) e was F I want to just give them 0,  whereas if they are guessing or using reasoning about `Bill wouldn't ...' I want to give them -3. But alas, we cannot read their minds or souls.

Friday, May 11, 2018

Richard Feynman (1918-1988)

When I took cryptography from Manuel Blum, he handed out copies of the chapter "Safecracker Meets Safecracker" from Richard Feynman's book Surely You're Joking Mr. Feynman. Feynman, the Nobel Prize winning physicist who was born a hundred years ago today, wrote this book not about physics but just a series of stories from different times in his life. This chapter described how Feynman learned how to open locked safes in Los Alamos during the Manhattan Project.

We all have interesting stories to tell but Feynman finds a way to keep things compelling in a way most scientists could not--even if he sometimes comes off being a bit of a jerk, hence the title. This book inspired me to tell my own stories which occasionally show up in this blog.

His most important stories form The Feynman Lectures on Physics (free to read online), an amazing explanation of deep physical concepts.

Richard Feynman's biggest contribution to theoretical computer science comes from a 1981 keynote address.
What kind of computer are we going to use to simulate physics? The full description of quantum mechanics for a large system cannot be simulated with a normal computer. And therefore, the problem is, how can we simulate the quantum mechanics? Can you do it with a new kind of computer—a quantum computer?
which begat a proof-of-concept paper by David Deutsch and Richard Jozsa which begat Daniel Simon's exponential separation which begat Peter Shor's factoring algorithm which begat billions of research dollars and considerable expectations, real and imagined, for Feynman's vision.

Wednesday, May 09, 2018

Second of N posts on G4G13. Maybe

(Don't forget to vote for SIGACT posistions:here  9th workshop on Flexible network design, May 22-25 at College Park, here.)

My first poston G4G13 is arguably here. To see why its debatable, see that post.


In a Foxtrot cartoon (see here) Foxtrot has a glass which looks like it is half-full (or half-empty)
and asks people if its half-full or half empty. But the jokes on them!
The class is slightly angled so its actually 5/12 full (or 7/12 empty)
Given the area of the top and bottom What is the angle?
Generalize to other dimensions.

HEX PRIMES by Spandan Bandyopadhyay

Here is an alternative definition of primes that
lends itself to a generalization.

A number x is PRIME if when there is a rectangle with
integer sides and area x, one of the sides is 1.

Lets generalize this!

A number x is TRIPRIME if when there is a triangle with
integer sides of area x, one of the sides is 1.

Rather than use these prefixes we will go with

A number x is n-PRIME if when there is a convex n-gon with
integer sides and area x, one of the sides is 1.

HEXPRIMES are of course 6-primes.

The problem with 5-minute talks (maybe it should have been 6 minutes)
is that the concept is intersting but I didn't get to hear much
about them. And I could not find a paper on line. Note that this
conference has many non-academics for whome PAPERS are not the
basic currency so things are more informal. This is GOOD in that
its more of a free-for-all, but bad for follow up.
ALL of G4G12's are on You-Tube, so when that happens for G4G13,
I can follow up on this.

One thing I did manage to write down- 7 is the first HEX-composite.

Thursday, May 03, 2018

Broader Impacts Redefined

The ACM Future of Computing Academy suggests that "peer reviewers should require that papers and proposals rigorously consider all reasonable broader impacts, both positive and negative." Here is the broader impacts section of a future imagined grant proposal.

My latest cryptocurrency paper will allow people to sell all sorts of paraphernalia, illegal, immoral and fattening, while avoiding paying taxes. Dr. Evil and his minions can move money around the world anonymously to more easily implement their dastardly plans. With this new work bitcoin will increase in value, causing far more mining setups that will deplete the energy resources of the world.

Since I already own bitcoin, I will get filthy rich, increasing the gap between the one-percenters and the middle-class. I'll buy a fancy car and reprogram the auto-pilot to run over people who get in my way. And all those pesky bicyclists clogging the roads. That would be a positive impact.

For the rest of humanity my new quantum gravitation algorithm will put all those people out of work. But their misery will be short lived because if anyone tries to run the algorithm, it may cause a small black hole that devours the earth.

My proposed generic oracle separation would seem to have no impact whatsoever. But what happens if an alien race threatens to destroy the planet unless we find such a separation. I will have saved the earth, a very positive broader impact. Of course a different alien race could visit the earth and deem it mostly harmless until they discover my oracle, realized we have advanced too far and then blow us up before we become a threat.

In other broader impacts, I will train graduate student to be just like me. Whether this is a positive or negative impact I leave to the reviewers.