Communication complexity of the secret key agreement in algorithmic information theory

DOI10.4230/LIPICS.MFCS.2020.44MaRDI QIDQ5089211FDOQ5089211

Authors: Emirhan Gürpınar, Andrei Romashchenko 

Publication date: 18 July 2022

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

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

zbMATH Keywords

mutual informationfinite geometrycommunication complexityKolmogorov complexityexpander mixing lemma

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Expander graphs and their applications
• 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
• Communication Complexity
• Kolmogorov Complexity and Algorithmic Randomness
• Mixing properties and the chromatic number of Ramanujan complexes
• Secret key agreement by public discussion from common information
• Common randomness in information theory and cryptography. I. Secret sharing
• Conditional complexity and codes
• Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)
• Finite analogues of Euclidean space
• A Conditional Information Inequality and Its Combinatorial Applications
• An introduction to Kolmogorov complexity and its applications
• Pairs of words with nonmaterializable mutual information
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• Spectral properties of unitary Cayley graphs of finite commutative rings
• Communication for Generating Correlation: A Unifying Survey
• An operational characterization of mutual information in algorithmic information theory
• Common Information and Secret Key Capacity
• Secret Key Generation With Limited Interaction

Cited In (4)

• 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
• 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)