Communication complexity of the secret key agreement in algorithmic information theory

DOI10.4230/LIPICS.MFCS.2020.44MaRDI QIDQ5089211zbMATH OpenFDO

Authors Emirhan Gürpınar, Andrei Romashchenko

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/2004.13411

zbMATH Keywords

mutual informationfinite geometrycommunication complexityKolmogorov complexityexpander mixing lemma

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• An operational characterization of mutual information in algorithmic information theory
• An operational characterization of mutual information in algorithmic information theory
• Secret key agreement by public discussion from common information
• Communication complexity of key agreement on small ranges

Cites work

• A Conditional Information Inequality and Its Combinatorial Applications
• An introduction to Kolmogorov complexity and its applications
• An operational characterization of mutual information in algorithmic information theory
• Common Information and Secret Key Capacity
• Common randomness in information theory and cryptography. I. Secret sharing
• Communication Complexity
• Communication for Generating Correlation: A Unifying Survey
• Conditional complexity and codes
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Expander graphs and their applications
• Finite analogues of Euclidean space
• Kolmogorov Complexity and Algorithmic Randomness
• Mixing properties and the chromatic number of Ramanujan complexes
• Pairs of words with nonmaterializable mutual information
• Secret Key Generation With Limited Interaction
• Secret key agreement by public discussion from common information
• Spectral properties of unitary Cayley graphs of finite commutative rings
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields
• The probabilistic method
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)

Cited in

(5)

• On the Optimality of Secret Key Agreement via Omniscience
• Communication complexity of key agreement on small ranges
• Communication complexity of secure distributed computation in the presence of noise
• Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory
• Comments On “Information-Theoretic Key Agreement of Multiple Terminals—Part I”

This page was built for publication: Communication complexity of the secret key agreement in algorithmic information theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5089211)