tag:blogger.com,1999:blog-3722233.post1107525003076172241..comments2017-06-24T09:52:46.896-04:00Comments on Computational Complexity: Proving Langs not Regular using Comm ComplexityLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-81917101619895958752017-04-06T23:57:22.515-04:002017-04-06T23:57:22.515-04:00AH-you raise the good point that after a while a c...AH-you raise the good point that after a while a community is so used to certain abbreviations that they (or at least me) assumes they are well known.<br /><br />Langs means Languages. For us a Language is a set of strings. What is a string? A string is a sequence of characters in an alphabet that we all agree on. If the alphabet is {a,b} then<br />aabbbaaa would be a string.<br /><br />Comm means Communication.<br /><br />Are these special in complexity?<br />Alphabet, string, Language are common in all of Computer science, though Language may be something else to people who work in Programming Languages. Langs for Languages is probably not standard, though I suspect most people reading this column knew what I meant (thank YOU for keeping me honest!). Comm for Communication- not sure if thats common.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9693161677885732752017-04-06T20:21:21.802-04:002017-04-06T20:21:21.802-04:00What is "Langs", and what is "Comm&...What is "Langs", and what is "Comm"? Are these special concepts in complexity?Studentnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27957727873684377662017-04-06T06:33:32.239-04:002017-04-06T06:33:32.239-04:00DFA size and deterministic communication complexit...DFA size and deterministic communication complexity of a language in a uniform model of one-way communication are equivalent.<br /><br />The uniform model is that Alice gets a string x and Bob a string y, and the protocol has to decide if xy is in the language.<br /><br />Once you change to non-deterministic or randomized the connection breaks down (lower bounds for automata size remain valid).<br /><br />http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.4448<br /><br />contains some attempts to use this connection for non-deterministic automata.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51964855230861008772017-04-06T02:17:18.467-04:002017-04-06T02:17:18.467-04:00I agree there is ambiguity in what communication c...I agree there is ambiguity in what communication complexity means for uneven splits. I think the complexity of words of size n should be max over all words of size n and all ways to split them. Or it may also make sense to measure complexity with respect to the size of Alice's input only, since this is a one-way model. It seems that since we only care about O(1) complexity, the finer details are not crucial.Sashohttp://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13566986990630422672017-04-05T20:42:19.745-04:002017-04-05T20:42:19.745-04:00I've taught some basics of communication compl...I've taught some basics of communication complexity alongside Myhill-Nerode (and streaming algorithms) for a number of years now in my undergrad automata theory course. (The slides are available online from my webpage.) <br /><br />What Sasho is describing is related to a homework exercise in the same course :) Under the model being described where Alice and Bob get arbitrary splits of a string into halves, and must get O(1) communication for every split, two-way communication should also work (because two way DFAs = DFAs)ryanwhttp://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14738232709820651912017-04-05T18:57:28.575-04:002017-04-05T18:57:28.575-04:00Crossing sequences are a special case of communica...Crossing sequences are a special case of communication complexity.<br />CSProfhttp://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58350611893274495202017-04-05T16:52:33.017-04:002017-04-05T16:52:33.017-04:00Uneven splits- interesting idea but could mean a f...Uneven splits- interesting idea but could mean a few things:<br />Fix n<br />Comm Complexity is max over all splits of x,y<br />min?<br /> GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59336600589669869222017-04-05T14:51:41.100-04:002017-04-05T14:51:41.100-04:00I am not sure this is O(1) under the definition of...I am not sure this is O(1) under the definition of a communication problem I was trying to describe. In the communication problem for language L, Alice receives an string x of arbitrary length, and Bob received another string y also of arbitrary length. Alice sends a single message to Bob, who must use the message and y to decide if xy \in L. I can see how for the language you define the communication complexity is O(1) if Alice and Bob each get half of the word whose membership needs to be decided. But in my definition I allow uneven splits, and I don't think the communication complexity will be O(1) if Alice doesn't get all of x.Sashohttp://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7766042430962758732017-04-05T11:49:16.147-04:002017-04-05T11:49:16.147-04:00Not iff. What if L is { xy : |x|=|y| and x\in HALT...Not iff. What if L is { xy : |x|=|y| and x\in HALT}<br />Then the Comm Comp of L is O(1) but L is not decidable.<br />We need some way to ban these kinds of contrived counterexamples.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60273469074769475742017-04-05T11:47:53.962-04:002017-04-05T11:47:53.962-04:00I believe this is open. Here is phrasing of it, bo...I believe this is open. Here is phrasing of it, both directions<br />1) Is there a nonreg L such that <br />- there is a constant c such that for all w\in L, |w|\ge c,<br />there exists x,y,z w=xyz with |xy|\le c such that<br />xy*z is in L. AND comm comp of { (x,y): |x|=|y|=n and xy\in L} is nonconstnat.<br />2) Is there a non-reg lang L such that comm comp of<br />{ (x,y) : |x|=|y|=n and xy\in L} is O(1) but pumping does prove its not regular. Actually this a a YES but with a silly example that I would want to not allow<br /><br />{ xy : |x|=|y| and x has same number of a's as b's}GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91093142252580746212017-04-05T10:03:17.919-04:002017-04-05T10:03:17.919-04:00@Sasho: Thanks! I could have a look at Kushilevitz...@Sasho: Thanks! I could have a look at Kushilevitz and Nisan's book that is on my shelf... The proof is really close to the classical one since it uses, though in some slightly disguised form, the notion of crossing sequence.B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13963067706062250002017-04-05T09:39:48.909-04:002017-04-05T09:39:48.909-04:00Myhill-Nerode is very much in the spirit of these ...Myhill-Nerode is very much in the spirit of these communication complexity arguments and it may be nice to teach it that way. If I am not missing something, you can restate the theorem as "the deterministic one-way communication complexity of L is O(1) if and only if L is regular". Here the communication problem associated with a language is for Alice and Bob to determine if their concatenated inputs are in L.Sashohttp://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78112135608924837362017-04-05T09:29:02.324-04:002017-04-05T09:29:02.324-04:00@B. It's in Section 12.2 of the Kushilevitz-Ni...@B. It's in Section 12.2 of the Kushilevitz-Nisan book. The main claim is that, given a function f:{0,1}^n \times {0,1}^n \to {0,1}, the time complexity of recognizing the language L_f = {x0^{n}y: f(x,y) = 1} on a single tape TM is at least n*R_0(f), where R_0 is randomized zero-error communication complexity (with public randomness). This gives a quadratic lower bound for recognizing palindromes using a communication lower bound for equality.<br /><br />For the argument, fix a single tape TM that recognizes L_f in time T(n). We will use it to give a zero error protocol with expected complexity O(T(n)/n). Alice and Bob pick an index i uniformly at random from {n+1, …, 2n}. This is the index of one the n zeros in the middle of the input. Then Alice and Bob together simulate the TM basically in the obvious way: whenever the head is to the left of i Alice does the simulation, and when the tape crosses over to the right of i she sends the internal state to Bob, and then he continues the simulation, and the same happens in reverse when the head crosses over from the right of i to the left. Each crossing costs constant communication, and the expected number of times the head crosses over i is at most T(n)/n.<br />Sashohttp://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73731043406729813022017-04-05T03:54:59.513-04:002017-04-05T03:54:59.513-04:00I there a (known) way to rephrase the classical pr...I there a (known) way to rephrase the classical proof that palindromes cannot be recognized in time o(n²) on a 1-tape TM using communication complexity? I am aware that the classical proof has a flavor of communication complexity. My question is: Is it possible to use a lower bound on the deterministic communication complexity of {(x,y):|x|=|y|=n and x=ȳ}, where ȳ is the mirror of y, to derive the lower bound (or some lower bound) on the 1-tape complexity of palindromes? I guess that the deterministic communication complexity of the set I defined is n+1 (same proof as for equality), but I was unable to adapt the proof you present for {xx:x in {0,1}*} not being regular to my case.B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90689574483235730412017-04-05T02:59:40.173-04:002017-04-05T02:59:40.173-04:00Is this technique stronger than the pumping lemma?...Is this technique stronger than the pumping lemma?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58032321085243485742017-04-05T02:28:29.935-04:002017-04-05T02:28:29.935-04:00I recently asked references for a very related tec...I recently asked references for a very related technique here: http://cstheory.stackexchange.com/questions/37136/regular-languages-and-constant-communication-complexity<br /><br />I note there that Hauser has a general technique for 2-player communication complexity when the input is spread in a finite number of blocks between Alice and Bob.<br /><br />A different approach, with multiple players and a fine study of the complexity of the resulting language, is given by:<br /><br />A. Chattopadhyay, A. Krebs, M. Kouckỳ, M. Szegedy, P. Tesson, and D. Thérien, “Languages with bounded multiparty communication complexity,” in Annual Symposium on Theoretical Aspects of Computer Science. Springer, 2007, pp. 500–511.<br /><br />and the citations therein. <br /><br />To add a bit of self-advertising, in https://arxiv.org/abs/1701.02673 we use a simple communication complexity technique to show that a language is in MSO[<] augmented with all monadic numerical predicates. To do so, we adapt the folklore proof of my above CSTheory question.<br /> <br />Cheers!Michaël Cadilhachttp://www.blogger.com/profile/02377285634686958683noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48681237482176703902017-04-05T00:10:49.599-04:002017-04-05T00:10:49.599-04:00Arguably, Regular languages are simpler to underst...Arguably, Regular languages are simpler to understand than Communication complexity, and are thought earlier, that's why these proofs are ot used. Otherwise, later the proof that Palindromes cannot be decided on a single-tape Turing-machine in o(log n) space (in fact not even o(n^2) time) also uses essentially the same idea.domhttp://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68515736520459050092017-04-04T22:58:16.209-04:002017-04-04T22:58:16.209-04:00Thanks. I have added this ref to the post.Thanks. I have added this ref to the post.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22265767919007007432017-04-04T18:53:30.063-04:002017-04-04T18:53:30.063-04:00Turns out our ideas weren't new; they appeared...Turns out our ideas weren't new; they appeared in this paper: J.-C. Birget. Intersection and union of regular languages and state complexity.<br />Inform. Process. Lett. 43 (1992), 185-190.Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.com