hi everyone my name is morgan surely and i am pleased to present some results on the number of permanence taken randomized boy and hierarchies in communication complexity this was joint work with tony passing at the university of toronto in the iss and with tom watson at the university of memphis. here's an hour an abyss how our main results involves studying who in her keys in communication complexity.

will be helpful to spend some time on the background happen issuance and motivations first. the find my yeah when nineteen seventy nine and communication complexity asked questions about the following seven two parties allison bob each hold and its strengths which will call x. and y. here and their goal is to pass messages back and forth in order to compute some portion of their strength.

there are allowed on limited computation power the only metric on which they are measured is how many bits they need to communicate before they agree on the answer the basic model of communication but city is the protocol that allison bob use must be deterministic that is given fix input strings communication. in between the two was always exactly the same. studying the power and limitations of this model already leads to some interesting results and other areas appear at a computer science for example in distributed computing and in monotone cornmeal are bounce. it is also interesting to study the model where allison bob have access to a source of randomness and are only required to help of the correct answer most of the time does this help allison bob solve the problem while communicating last this is analogous to the the verses eat the question in classical computation but while. all it is reasonable to conjecture that randomness does not how more than a pollen the male amount entering machines so he may very well equal he it is numb the randomness does help quite a bit in communication and important example of this is the equality commission simply the palace's input equal bobby's.

a simple arguments about the properties of deterministic protocol shows that we need a linear amounts of communication in a deterministic said. best possible protocol is for alice to send her entire inputs ababa and for bombs or why whether or not he has the same income. we can do much better in a randomised setting alice can randomly sample a prime number of wang quadrille mccain and and seven that crime as well as her input modular that crime. if the inputs are equal in bob's input modular the crime will always be the same as alice's. they're not equal and with good probability their inputs modular the primal the difference as well. when in classes of problems in communication complexity by analogy to classical complexity classes problems that are officially for deterministic communication are in a class he with a c.c. superstrings recall that in the worst case problems have linear complexity in the wake of the inputs as alice.

in simply send her entire inputs a bob therefore efficient can mean pollen know me all all problem some when you're complexity which is hollow mail instead by a vision here are we mean holly logarithmic in the way. polly logarithmic fortuitously also starts with a p so the calling the class he makes some amount of sense we define other communication classes by analog as well example we saw earlier shows that be a quality problem is not in he is in between the impact because the protocol we. i've never had a false negatives a quality is in cattle are the two other commonly studied classes are and the m.p. to be empty. in the m.p. model communication and all knowing gruber who can see the inputs an ounce as a witness string and the party's independently the side to accept or reject only seeing the witness string and their input costs of such a protocol is the length of the witness trade. i know that there are some other ways to define on deterministic communication that you might see in the literature but all of these definitions turn out to be a quibble. in p b n p communication parties can exchange bits of information just like in deterministic communication but can also sell functions were charged the end he communication cost of that portion this is similar to the concept of an oracle carry in turn machines. communication oracle's come up quite a bit in the stock so let me go into a bit more detail on them. let's say alice in bob are trying to compute the output of a two party function asked and they want to do so using call a logarithmic communication in the model key to the and p if they're able to do so then apple isn't peter the and p..

as a part of this protocol they're able to compute the output to a different to party function she has holly logarithmic and p. communication what city in the following way. each one writes down and input said g. privately this inputs a g. can depend on their inputs f. and on the communication that has occurred thus far. then they get the output from g. and they can hopefully use this to help them solve asked to cost that this adds to the overall protocol is the and p. cost of g.. communication complexity classes such as these may seem a bit esoteric but it turns out that they can have some interesting consequences. if we take these oracle classes to their logical conclusion we get a class that corresponds to the pollen o'neal hierarchy and this class has deep ties to matrix virginity and static pay the structures.

unfortunately we don't even know how to think about the second level but communication complexity call it a male higher the level of the whole bank. this brings us to a big open problem in communication complexity what is the relationship between the key and p. diddy and me we know that he did the m.p. can solve problems officially that take a linear time in be one example is the set destroying a strong.

if we allow allison bob to solve partial functions that is they have a promise on air and the p.p.p. can do much better than p. diddy and p.m. certain functions so the classes are in comparable in this setting this doesn't say anything about it the verses a to b. and b. or total functions.

it's common in communication complexity to consider both the case for partial functions are allowed and the case were total conscience are required. when solving harsh functions protocols are allowed to break the rules on inputs not in the support so in this case the d.p.p. protocol must be correct with probability bounded away from fifty percent on the inputs in the support i can answer incorrectly or probabilities close to fifty percent otherwise. an example where a difference between the total function setting and a partial function setting has been shown to hold his the verses and p. intersex cullen be a well known communication complexity result shows that these classes are the same her total functions but they can be accidentally separated a partial functions or lab. remember this example as it will come up later. one approach to making progress on the b.p. versus the to the m.p. question that i'd like to highlight is to first solve the keeper says he to be our he were p.b.r. he is defined likely to be empty except that the oracle class its functions that have randomized protocols were one sided air.

but these are equal for total farm gems in b.p. is strickly contain impeded the m.p. as we already know that he to the army is strictly contained in haiti and the.

up until recently many researchers stop that in fact the p.p.p. with equal some people each you her total conscience impeded e.q. the function of his career it must be the equality commission and the cost for doing so is why i'm. this seemed reasonable because every randomized protocol known at the time could be written using a quality or call the company i love it in being as recently the screw this conjecture in fact they show an infinite hierarchy a stronger and stronger sanctions were one sided ran a mess so these functions are and co are. the such that each function can not be solved with oracle access to india the previous functions. our contribution to this area is to study what happens when and instead of changing the strength of your whole which changed the number of times the be or coal is allowed to the call.

specifically we studied the randomized school in higher in communication complexity. let me first the fire and the number deterministic new in hiring. let q.b. a constant class he to the and kikuyu parallel i'm sorry that this is a bit of a mouthful to say contains problems which have a fishing peter the m.p. style protocols report constraint that we are only allowed some have at most a few m.p. oracle calls and that these calls must.

he made non adapt to avoid that is the queries must not depend on the answers to previous queries you can think of this as the queer is being made in parallel this is a natural way to studied the power of adding more and he or all. unfortunately he's rather well motivated classes are hard to reason about without studying a slightly different set of classes that is traditionally called the bullion hierarchy we call it the monitor mystic will inherit the to differentiate it from the randomized lawyer and hierarchy but all the fine on the moment the person. bubble of the hierarchy has classes and p. wind and co and the wind which are global in two and key and co and p. respectively. rick use level has classes and kikuyu and co and the geo protocols amuse classes look like this we have you m.p. problems and we asked whether an odd or even number of them would return treuille on the inputs. for protocols and and teach you the answer is odd he returned true and the answer is here and we were churned fall. cohen p.q. reversed needs. this looks a little weird why should we think of taking the parody of you and the functions in fact there are a number of ways to define the nominee terminus to glue and hierarchy that have been studied in both classical complexity and communication complexity and it turns out these other ways are equivalent to this odd or.

even construction. i'm not going to the finding is always here but if you're interested here a couple of references. we use the parity definition because it happens to be critique easy to think about in communication complexity the other definitions more clearly capsule the idea of grounding the number of calls to an m.p. oracle for unfortunately less clean. in communication complexity the not deterministic billion hierarchy is intertwined with a set of classes he to the and e.q. parallel but we declined earlier and p.q. is strickly contained in piece of the and p.q. parallel which in turn is strickly contained in and teach pupils one.

in fact previous work almost entirely characterize the relationships between classes in the communication not deterministic billion hiring. only one question was left open.

his piece of the m.p. two parallel strictly contained in and peace you post one intersex cohen kikuyu course one. it was known that the containment is true but not whether the classes are different note that if we take a few equals zero this is simply the p. worse and be intersex go and the problem from earlier. if your call for classes are equivalent if we only consider total functions but they're different if partial functions are allowed. one of our results is that the same holds for in constant queue. and easy modification is to exchange and he with our he set of problems with the addition randomized algorithms with no false positives this is the randomized lillian hierarchy the turn machine version of this hierarchy has been studied.

but not the communication complexity version of this hierarchy is a natural way to model more r.p. calls which you'll recall is our goal.

here's some examples of conscience in various levels of the randomized boy in her a. we are already solved it a quality was in co r.p. and so the negation of a quality not equality is an r p. both of these are in the first level of the hierarchy. what we define a function that all call parity a huge nama qualities alice is in bob's in a are each divide it into q blocks x. one through extra few and why wonder why jail. herrity if q non equality returns true if they're an odd number of lives such that x.i.i. is not the whole so why i. this is pretty clearly in our heat you. the billing the gate is to get negated parity a few nona qualities this function returns true if they're an even number of eyes such that x.i.i. is not equal so why i. this negated parody of human on the qualities function isn't co are people here. our main contribution is to relate the randomized lawyer and hire again so the non deterministic louis and hire it.

turns out that these are intertwined in such a way that shows that the randomized doing hierarchy does not collapse that is more r.p. calls help compute more functions. also earlier i mentioned that we resolve an open problem concern in classes in the not determine istiklal inheriting we also showed the same result of the randomized billion hire in together these results completely resolved questions about the separations between classes in both grueling hierarchies. for the rest of the time that i have i'd like to talk a bit about the ideas behind the groups in our paper.

first we proved the hell are you can especially solve problems that and kikuyu hand.

the portion that we used to separate these is the negated parody of you not a quality song can come earlier were called that this function is in co are p.q. by the fact that the negation of the equality function is an r.p.g.. we proved that it isn't in and teach you buy a fairly direct common and turrell argument i won't go into the details but intuitively this will make sense not a quality is an end he so and he queued protocol can return true when an odd number of blocks of different very easily. quality is not in and the so than a gated problem should be typical for andy keogh. this result crews that the randomized billion herrick he is in fear because our p.q. is contained in mph you in so ho our peace deal is not equal to our feet you are in constant kill and therefore hierarchy does not collapse. the resolution of the question of heat to the n.p.t. a parallel versus and peace you post one intersect hell and pete you was one is more complicated to hurt her total functions the equality is fairly easy to show and it is constructive. if you give me efficient and p.q. coastline and co and heat you cost one protocols for function i can give you a piece of the m.p.g. apparel protocol. we were place m.p. with our key here for construction remains the same the separation in a partial function haste is much more involved it involves proving and reread to communication lifting gear and per and teach you and he said the and the hue parallel. here it's a communication lifting is when the hardness of a conscience decision tree complexity is lifted to show the hardness of a related communication have action.

we have a partial function that it's harder for a model of decision trees that is analogous to the to be emptied you parallel and show how bad it gives a related communication partial function as hard or piece of the and you parallel itself.

we also show that the related function is easy for both our p.c. plus one and co are huge was one which gives the desired separation from both the monitor mystic and randomized hire ease. for those of you who are familiar with lifting parents all quickly get a couple of details on ours both of our lifting kirin's use the index gadget with the size of and so the twenty which means the both of them and her a logarithmic penalty in the simulation our mpg lifting pyramid is based on mortgages command. passing in watson with think there are key to the and be used out of the box there with think there are more not preserve a constant she knew him and he he'll we make modifications to ensure that this she remains the same after within takes place. r.p.t. and p.q. parallel lifting pyramid essentially glues together the deterministic lifting heerema horizon mckenzie to our mpg lifting their of this result is a bit more straightforward than the crew correctness for the m.p. q lifting pair of but still require some work to make sure that the deterministic and mpg lifting parents claim. i sleep together. to conclude let me give you some open problems we pretty much completely resolved the structure of both the randomized and none deterministic to inherit his but there are still other work that can be done.

not much is known about relationships between other natural communication classes and classes at high levels of hierarchies. another thing that might be useful is a query to communication lifting gear and her classes in the randomized glowing hierarchy in our paper we only need a listing for classes in the non deterministic billion hierarchy. bullion hierarchy is represent protocols with the constant number of oracle calls what if we still down the number of calls by a super constant amount. finally let me remind you of the big open questions of p.p.p. versus the to the are paying and beekeeper says even the and the thanks for watching have a great day.