One-way multiparty communication lower bound for pointer jumping with applications (Q532058): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / review text | |||
The paper studies communication complexity in the ``number on the forehead model''. In other words, we have \(k\) players and \(k\) \(n\)-bit inputs \((x_i)_{i=1}^k\) and the \(i\)-th player knows all inputs except \(x_i\). The goal of the players is to compute a function on their combined inputs. The paper studies a particular variant of this model where each player only speaks once and the order in which the players speak is fixed in advance, thus we can assume that player \(i\) speaks at time \(i\). The main function considered is a \(k\) level pointer jumping (which is essentially a \(k\)-fold composition of functions), where \(x_i\) give the pointers on level \(i\) (description of the \(i\)-th function). The lower bound obtained, which is tight for any constant \(k\) and randomized protocols, is that \(\Omega (n^{1/(k-1)})\) bits must be sent and the bounds remain nontrivial up to \(k=(\log n)^{1/2-\epsilon}\) for any \(\epsilon > 0\). It is not difficult to see that the problem is easy (can be done with communication \(O(\log n)\)) if the players are allowed to speak in any other order. As corollaries lower bounds for related functions follow in similar models. In particular, for any constants \(k\) and \(r\) there is a function that requires \(\Omega (n^{\Omega (1)})\) communication by an \(r\)-round \(k\)-party protocol but can be computed by \(O(\log n)\) communication in \(r'\) rounds when \(r'(k-1) \geq rk\). The function can also be computed by a nondeterministic \(2\)-round protocol with \(O(\log n)\) communication. | |||
Property / review text: The paper studies communication complexity in the ``number on the forehead model''. In other words, we have \(k\) players and \(k\) \(n\)-bit inputs \((x_i)_{i=1}^k\) and the \(i\)-th player knows all inputs except \(x_i\). The goal of the players is to compute a function on their combined inputs. The paper studies a particular variant of this model where each player only speaks once and the order in which the players speak is fixed in advance, thus we can assume that player \(i\) speaks at time \(i\). The main function considered is a \(k\) level pointer jumping (which is essentially a \(k\)-fold composition of functions), where \(x_i\) give the pointers on level \(i\) (description of the \(i\)-th function). The lower bound obtained, which is tight for any constant \(k\) and randomized protocols, is that \(\Omega (n^{1/(k-1)})\) bits must be sent and the bounds remain nontrivial up to \(k=(\log n)^{1/2-\epsilon}\) for any \(\epsilon > 0\). It is not difficult to see that the problem is easy (can be done with communication \(O(\log n)\)) if the players are allowed to speak in any other order. As corollaries lower bounds for related functions follow in similar models. In particular, for any constants \(k\) and \(r\) there is a function that requires \(\Omega (n^{\Omega (1)})\) communication by an \(r\)-round \(k\)-party protocol but can be computed by \(O(\log n)\) communication in \(r'\) rounds when \(r'(k-1) \geq rk\). The function can also be computed by a nondeterministic \(2\)-round protocol with \(O(\log n)\) communication. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68P30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68R99 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5881153 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
communication complexity | |||
Property / zbMATH Keywords: communication complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pointer jumping | |||
Property / zbMATH Keywords: pointer jumping / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
multiparty computation | |||
Property / zbMATH Keywords: multiparty computation / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Johan T. Håstad / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00493-009-2667-z / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2076448565 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The space complexity of approximating the frequency moments / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4910715 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Communication Complexity of Simultaneous Messages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The cost of the missing bit: Communication complexity with help / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Multiparty Communication Complexity and Threshold Circuit Size of AC^0 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Improved depth lower bounds for small distance connectivity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A strong direct product theorem for corruption and the multiparty communication complexity of disjointness / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On ACC / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An information statistics approach to data stream and communication complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The NOF Multiparty Communication Complexity of Composed Functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Communication Complexity and Quasi Randomness / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lower bounds on communication complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some bounds on multiparty communication complexity of pointer jumping / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Improved Separations between Nondeterministic and Randomized Multiparty Communication / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: NOF-Multiparty Information Complexity Bounds for Pointer Jumping / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the power of small-depth threshold circuits / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Communication Complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Disjointness is hard in the multiparty number-on-the-forehead model / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4527022 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rounds in Communication Complexity Revisited / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Communication complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The BNS-Chung criterion for multi-party communication complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3396635 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3549688 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Separating ${AC}^0$ from Depth-2 Majority Circuits / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: One-way multiparty communication lower bound for pointer jumping with applications / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3002796 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 00:28, 4 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | One-way multiparty communication lower bound for pointer jumping with applications |
scientific article |
Statements
One-way multiparty communication lower bound for pointer jumping with applications (English)
0 references
26 April 2011
0 references
The paper studies communication complexity in the ``number on the forehead model''. In other words, we have \(k\) players and \(k\) \(n\)-bit inputs \((x_i)_{i=1}^k\) and the \(i\)-th player knows all inputs except \(x_i\). The goal of the players is to compute a function on their combined inputs. The paper studies a particular variant of this model where each player only speaks once and the order in which the players speak is fixed in advance, thus we can assume that player \(i\) speaks at time \(i\). The main function considered is a \(k\) level pointer jumping (which is essentially a \(k\)-fold composition of functions), where \(x_i\) give the pointers on level \(i\) (description of the \(i\)-th function). The lower bound obtained, which is tight for any constant \(k\) and randomized protocols, is that \(\Omega (n^{1/(k-1)})\) bits must be sent and the bounds remain nontrivial up to \(k=(\log n)^{1/2-\epsilon}\) for any \(\epsilon > 0\). It is not difficult to see that the problem is easy (can be done with communication \(O(\log n)\)) if the players are allowed to speak in any other order. As corollaries lower bounds for related functions follow in similar models. In particular, for any constants \(k\) and \(r\) there is a function that requires \(\Omega (n^{\Omega (1)})\) communication by an \(r\)-round \(k\)-party protocol but can be computed by \(O(\log n)\) communication in \(r'\) rounds when \(r'(k-1) \geq rk\). The function can also be computed by a nondeterministic \(2\)-round protocol with \(O(\log n)\) communication.
0 references
communication complexity
0 references
pointer jumping
0 references
multiparty computation
0 references
0 references
0 references
0 references