Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
On Communication Complexity of Fixed Point Computation
View through CrossRef
Brouwer’s fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point. Roughgarden and Weinstein (FOCS 2016) initiated the study of fixed point computation in the two-player communication model, where each player gets a function from
[0,1]^n
to
[0,1]^n
, and their goal is to find an approximate fixed point of the
composition
of the two functions. They left it as an open question to show a lower bound of
2^{\Omega (n)}
for the (randomized) communication complexity of this problem, in the range of parameters which make it a total search problem. We answer this question affirmatively.
Additionally, we introduce two natural fixed point problems in the two-player communication model.
Each player is given a function from
[0,1]^n
to
[0,1]^{n/2}
, and their goal is to find an approximate fixed point of the
concatenation
of the functions.
Each player is given a function from
[0,1]^n
to
[0,1]^{n}
, and their goal is to find an approximate fixed point of the
mean
of the functions.
We show a randomized communication complexity lower bound of
2^{\Omega (n)}
for these problems (for some constant approximation factor).
Finally, we initiate the study of finding a panchromatic simplex in a Sperner-coloring of a triangulation (guaranteed by Sperner’s lemma) in the two-player communication model: A triangulation
T
of the
d
-simplex is publicly known and one player is given a set
S_A\subset T
and a coloring function from
S_A
to
\lbrace 0,\ldots ,d/2\rbrace
, and the other player is given a set
S_B\subset T
and a coloring function from
S_B
to
\lbrace d/2+1,\ldots ,d\rbrace
, such that
S_A\dot{\cup }S_B=T
, and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of
|T|^{\Omega (1)}
for the aforementioned problem as well (when
d
is large). On the positive side, we show that if
d\le 4
then there is a deterministic protocol for the Sperner problem with
O((\log |T|)^2)
bits of communication.
Association for Computing Machinery (ACM)
Title: On Communication Complexity of Fixed Point Computation
Description:
Brouwer’s fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point.
Roughgarden and Weinstein (FOCS 2016) initiated the study of fixed point computation in the two-player communication model, where each player gets a function from
[0,1]^n
to
[0,1]^n
, and their goal is to find an approximate fixed point of the
composition
of the two functions.
They left it as an open question to show a lower bound of
2^{\Omega (n)}
for the (randomized) communication complexity of this problem, in the range of parameters which make it a total search problem.
We answer this question affirmatively.
Additionally, we introduce two natural fixed point problems in the two-player communication model.
Each player is given a function from
[0,1]^n
to
[0,1]^{n/2}
, and their goal is to find an approximate fixed point of the
concatenation
of the functions.
Each player is given a function from
[0,1]^n
to
[0,1]^{n}
, and their goal is to find an approximate fixed point of the
mean
of the functions.
We show a randomized communication complexity lower bound of
2^{\Omega (n)}
for these problems (for some constant approximation factor).
Finally, we initiate the study of finding a panchromatic simplex in a Sperner-coloring of a triangulation (guaranteed by Sperner’s lemma) in the two-player communication model: A triangulation
T
of the
d
-simplex is publicly known and one player is given a set
S_A\subset T
and a coloring function from
S_A
to
\lbrace 0,\ldots ,d/2\rbrace
, and the other player is given a set
S_B\subset T
and a coloring function from
S_B
to
\lbrace d/2+1,\ldots ,d\rbrace
, such that
S_A\dot{\cup }S_B=T
, and their goal is to find a panchromatic simplex.
We show a randomized communication complexity lower bound of
|T|^{\Omega (1)}
for the aforementioned problem as well (when
d
is large).
On the positive side, we show that if
d\le 4
then there is a deterministic protocol for the Sperner problem with
O((\log |T|)^2)
bits of communication.
Related Results
Complexity Theory
Complexity Theory
The workshop
Complexity Theory
was organised by Joachim von zur Gathen (Bonn), Oded Goldreich (Rehovot), Claus-Peter Schnorr (Frankfurt), and Madhu Sudan ...
Linguistic Complexity
Linguistic Complexity
Linguistic complexity (or: language complexity, complexity in language) is a multifaceted and multidimensional research area that has been booming since the early 2000s. The curren...
Communication Management
Communication Management
The question of what comprises communication management has caused numerous discussions among communication scholars representing different theoretical and disciplinary angles. Com...
Information Technology and the Complexity Cycle
Information Technology and the Complexity Cycle
Aim/Purpose: In this paper we propose a framework identifying many of the unintended consequences of information technology and posit that the increased complexity brought about by...
Assessment of Construction Project Complexity
Assessment of Construction Project Complexity
Objective:Project complexity is a crucial factor in project management that presents auxiliary obstacles to reaching project objectives (cost, time, safety, and quality). This stud...
An effective communication topology for performance optimization: a case study of the finite-volume wave modeling (FVWAM)
An effective communication topology for performance optimization: a case study of the finite-volume wave modeling (FVWAM)
Abstract. High-resolution models are essential for simulating small-scale processes and topographical features, which play a crucial role in understanding meteorological and oceani...
Environmental Communication
Environmental Communication
The study of environmental communication, as a subfield of the study of communication, is a relatively recent endeavor. Roughly speaking, the field of environmental communication i...
An Effective Communication Topology for Performance Optimization: A Case Study of the Finite Volume WAve Modeling (FVWAM)
An Effective Communication Topology for Performance Optimization: A Case Study of the Finite Volume WAve Modeling (FVWAM)
Abstract. High-resolution models are essential for simulating small-scale processes and topographical features, which play a crucial role in understanding meteorological and oceani...