tag:blogger.com,1999:blog-3722233.post6550933808686728606..comments2021-09-24T04:38:40.736-05:00Comments on Computational Complexity: Kolmogorov Complexity and CausationLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-85226892539975031682018-06-19T14:47:57.031-05:002018-06-19T14:47:57.031-05:00still it can happen that a noisy signal has much h...still it can happen that a noisy signal has much higher complexity wrt no-noise propotype than vice versa...<br />alexander.shenhttps://www.blogger.com/profile/11475502380398851852noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73814393133547423212018-06-11T10:29:03.166-05:002018-06-11T10:29:03.166-05:00Kolmogorov complexity is slightly asymmetric (caus...Kolmogorov complexity is slightly asymmetric (caused by the incomputability of Kolmogorov complexity). If there are several rounds of information exchange, this asymmetry can accumulate and become linear in the number of rounds. <br /><br />Imagine 2 devices run a computation. At regular time intervals each device sends a bit to the other. We are given a list of communicated pairs of bits: (x1, y1), (x2, y2), ... We are asked to determine whether xi is a reply to yi or vice versa, thus the bits are either communicated in the order x1 -> y1 -> x2 -> y2 -> ... or y1 -> x1 -> y2 -x2 -> ... In this case the sum of online Kolmogorov complexities corresponding to the machines can differ by almost a factor 2, while the complexities grow linearly. See: http://drops.dagstuhl.de/opus/volltexte/2014/4452/<br />Unknownhttps://www.blogger.com/profile/00628530174326565098noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70950427849195373272018-05-29T08:08:18.287-05:002018-05-29T08:08:18.287-05:00Assumptions are key to causal inference. Under cer...Assumptions are key to causal inference. Under certain assumptions, one can decide the causal direction using Kolmogorov complexity. In the two variable case, instead of the Kolmogorov complexity of a random variable (exchangeably a string), Peters & Schölkopf, 2010 postulate that Kolmogorov complexity of distributions of those variables may have an answer. The paper titled "Causal inference using algorithmic Markov condition" by Peters & Schölkopf takes an interesting outlook on the problem of causal inference using Kolmogorov complexity. <br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37670531560444513452018-05-24T15:49:25.479-05:002018-05-24T15:49:25.479-05:00I think that you've (slightly) misunderstood t...I think that you've (slightly) misunderstood the question. In my interpretation our input is S={(x1,y1),..,(xt,yt)}, where all the xi's and yi's are distinct, and we want a (shortest) program P for which P(xi)=yi for every i, and a (shortest) program Q for which Q(yi)=xi for every i. The question is whether P or Q is shorter. Of course, your argument shows that this is undecidable already for t=1.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5793850227852413662018-05-24T14:58:10.159-05:002018-05-24T14:58:10.159-05:00The paper "Information-geometric approach to ...The paper "Information-geometric approach to inferring causal direction" (https://dl.acm.org/citation.cfm?id=2170008) contains a nice formalization of this idea.Arnabhttp://drona.csa.iisc.ac.in/~arnabb/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-92050872283739407882018-05-24T11:15:31.901-05:002018-05-24T11:15:31.901-05:00https://arxiv.org/abs/1702.06776https://arxiv.org/abs/1702.06776Anonymousnoreply@blogger.com