English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Consider the computations at a node in a message passing algorithm. Assume that the node has incoming and outgoing messages <inline-formula> <tex-math notation="LaTeX">$\mathbf {x} = (x_{1}, x_{2}, \ldots, x_{n})$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\mathbf {y} = (y_{1}, y_{2}, \ldots, y_{n})$ </tex-math></inline-formula>, respectively. In this paper, we investigate a class of structures that can be adopted by the node for computing <inline-formula> <tex-math notation="LaTeX">$\mathbf {y}$ </tex-math></inline-formula> from <inline-formula> <tex-math notation="LaTeX">$\mathbf {x}$ </tex-math></inline-formula>, where each <inline-formula> <tex-math notation="LaTeX">$y_{j}, j = 1, 2, \ldots, n$ </tex-math></inline-formula> is computed via a binary tree with leaves <inline-formula> <tex-math notation="LaTeX">$\mathbf {x}$ </tex-math></inline-formula> excluding <inline-formula> <tex-math notation="LaTeX">$x_{j}$ </tex-math></inline-formula>. We make three main contributions regarding this class of structures. First, we prove that the minimum complexity of such a structure is <inline-formula> <tex-math notation="LaTeX">$3n - 6$ </tex-math></inline-formula>, and if a structure has such complexity, its minimum latency is <inline-formula> <tex-math notation="LaTeX">$\delta + \lceil \log (n-2^{\delta }) \rceil $ </tex-math></inline-formula> with <inline-formula> <tex-math notation="LaTeX">$\delta = \lfloor \log (n/2) \rfloor $ </tex-math></inline-formula>, where the logarithm always takes base two. Second, we prove that the minimum latency of such a structure is <inline-formula> <tex-math notation="LaTeX">$\lceil \log (n-1) \rceil $ </tex-math></inline-formula>, and if a structure has such latency, its minimum complexity is <inline-formula> <tex-math notation="LaTeX">$n \log (n-1)$ </tex-math></inline-formula> when <inline-formula> <tex-math notation="LaTeX">$n-1$ </tex-math></inline-formula> is a power of two. Third, given <inline-formula> <tex-math notation="LaTeX">$(n, \tau)$ </tex-math></inline-formula> with <inline-formula> <tex-math notation="LaTeX">$\tau \geq \lceil \log (n-1) \rceil $ </tex-math></inline-formula>, we propose a construction for a structure which we conjecture to have the minimum complexity among structures with latencies at most <inline-formula> <tex-math notation="LaTeX">$\tau $ </tex-math></inline-formula>. Our construction method runs in <inline-formula> <tex-math notation="LaTeX">$O(n^{3} \log ^{2}(n))$ </tex-math></inline-formula> time, and the obtained structure has complexity at most (generally much smaller than) <inline-formula> <tex-math notation="LaTeX">$n \lceil \log (n) \rceil - 2$ </tex-math></inline-formula>.

A Class of Optimal Structures for Node Computations in Message Passing Algorithms