Coalgebraic tools for randomness-conserving protocols

We propose a coalgebraic model for constructing and reasoning about state-based protocols that implement efficient reductions among random processes. We provide basic tools that allow efficient protocols to be constructed in a compositional way and analyzed in terms of the tradeoff between state and...

Full description

Saved in:
Bibliographic Details
Published in:Journal of logical and algebraic methods in programming 2022-02, Vol.125, p.100734, Article 100734
Main Authors: Kozen, Dexter, Soloviev, Matvey
Format: Article
Language:English
Subjects:
Coalgebra
Entropy
Protocol
Randomness
Reduction
Transducer
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose a coalgebraic model for constructing and reasoning about state-based protocols that implement efficient reductions among random processes. We provide basic tools that allow efficient protocols to be constructed in a compositional way and analyzed in terms of the tradeoff between state and loss of entropy. We show how to use these tools to construct various entropy-conserving reductions between processes.
ISSN:2352-2208
DOI:10.1016/j.jlamp.2021.100734