The following pointer chasing problem plays a central role in the study of bounded round communication complexity. There are two players A and B. There are two sets of vertices V/sub A/ and V/sub B/ of size n each. Player A is given a function f/sub A/: VA/spl rarr/VB and player B is given a function f/sub B/: VB/spl rarr/VA. In the problem g/sub k/ the players have to determine the vertex reached by applying f/sub A/ and f/sub B/ alternately, k times starting with a fixed vertex v/sub 0//spl isin/V/sub A/. That is, in g/sub 1/, they must determine f/sub A/(v/sub 0/), in g/sub 2/ they must determine f/sub B/(f/sub A/(v/sub 0/)), in g/sub 3/ they must determine f/sub A/(f/sub B/(f/sub A/(v/sub 0/))), and so on.

We study the k-round two-party communication complexity of the pointer chasing problem for fixed k. Damm, Jukna and Sgall [2] showed an upper bound of O(n log(k\\Gamma 1) n) for this problem. We prove a matching lower bound; this improves the lower bound of \\Omega (n) shown by Nisan and Wigderson [11], and yields a corresponding improvement in the hierarchy results derived in [11, 7] for bounded-depth monotone circuits. We consider the bit version of this problem, and show upper and lower bounds. This implies that there is an abrupt jump in complexity, from linear to superlinear, when the number of rounds is reduced to k=2 or less. We also consider the s-paths version (originally studied by Klauck [7]) and show an upper bound. The lower bounds are based on arguments using entropy. One of the main contributions of this work is a transfer lemma for distributions with high entropy; this should be of independent interest.

We prove that read-once branching programs computing integer multiplication require size $2^{\Omega(\sqrt{n})}$. This is the first nontrivial lower bound for multiplication on branching programs that are not oblivious. By the appropriate problem reductions, we obtain the same lower bound for other arithmetic functions.

Article Free Access Share on A lower bound for integer multiplication with read-once branching programs Author: Stephen Ponzio MIT Laboratory for Computer Science MIT Laboratory for Computer ScienceView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995Pages 130–139https://doi.org/10.1145/225058.225098Published:29 May 1995Publication History 22citation329DownloadsMetricsTotal Citations22Total Downloads329Last 12 Months11Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The authors consider a system of distributed processors that communicate by passing messages and that have inexact information about time. Specifically, a processor knows that a single message is delayed by at most time d and the time between any two of its consecutive steps is at least e/sub 1/ and at most e/sub 2/; it has no other way of estimating elapsed time. The author extends this model by making a realistic assumption about how the delay of messages is affected by the rate at which they are sent. He defines a model of message links with bounded capacity, which are guaranteed to deliver messages at only a given rate. If a processor sends messages at a greater rate, they may incur greater delay. The effect of this bounded capacity on the time necessary to detect processor failures, is quantified. The author considers a system of two processors connected by a bidirectional message link of a given (integral) capacity.>