Worst-case interactive communication. II. Two messages are not optimal

Alon Orlitsky

Type: Article

Publication Date: 1991-07-01

Citations: 54

DOI: https://doi.org/10.1109/18.86993

View

Locations

IEEE Transactions on Information Theory - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Pliable Index Coding via Conflict-Free Colorings of Hypergraphs	2024	Prasad Krishnan Rogers Mathew Subrahmanyam Kalyanasundaram
+	Limited broadcast domination: upper bounds and complexity	2017	Carmen Hernando Mercè Mora Ignacio M. Pelayo José Cáceres María Luz Puertas
+ PDF Chat	None	2012	Alexander A. Sherstov
+	On the Capacity of Computation Broadcast	2019	Hua Sun Syed A. Jafar
+	The communication complexity of the inevitable intersection problem	2016	Dmitry Gavinsky
+	The communication complexity of the inevitable intersection problem	2016	Dmytro Gavinsky
+	Contributions to Structural Communication Complexity	2009	Henning Wunderlich
+	Combinatoriek: meer dan trucjes	2014	Mark Timmer Neeltje Cornelia Verhoef
+	Análise Combinatória e Proposta Curricular Paulista: um estudo dos problemas de contagem.	2011	Carlos Eduardo de Campos
+	SIGACT news complexity theory column 63	2009	Lane A. Hemaspaandra
+ PDF Chat	Multiparty Interactive Coding Over Networks of Intersecting Broadcast Links	2021	Manuj Mukherjee Ran Gelles
+ PDF Chat	Rounds vs. Communication Tradeoffs for Maximal Independent Sets	2024	Sepehr Assadi Gillat Kol Zhijun Zhang
+	Erratum to: Structural Information and Communication Complexity	2017	Thomas Moscibroda Adele A. Rescigno
+	Time bound	2001	Jetse Sprey
+	A tradeoff between information and communication in broadcast protocols	2006	Baruch Awerbuch Oded Goldreich David Peleg Ronen Vainish
+ PDF Chat	A note on multiparty communication complexity and the Hales–Jewett theorem	2018	Adi Shraibman
+	On Pliable Index Coding	2019	Shanuja Sasi B. Sundar Rajan
+	Bounding the Optimal Length of Pliable Index Coding via a Hypergraph-based Approach	2022	Tulasi Sowjanya B. Visvesh Subramanian Prasad Krishnan
+	An Upper Bound for a Communication Game Related to Time-Space Tradeoffs	2013	Pavel Pudlák Jiřį́ Sgall
+	Estrategias de resolución de un problema combinatorio en estudiantes de noveno grado de básica secundaria	2011	Luis Alejandro Bustos Felipe Fernández

Cited by (18)

Action	Title	Year	Authors
+	A First Course in Information Theory	2002	Raymond W. Yeung
+	Bibliography	2005
+	Effective protocols for low-distance file synchronization	2011	Aleksandr Chuklin
+ PDF Chat	Infinite-message distributed source coding for two-terminal interactive computing	2009	Nan Ma Prakash Ishwar
+ PDF Chat	Enhancing Sensor Network Lifetime Using Interactive Communication	2007	Samar Agnihotri Pavan Nuggehalli Ramesh R. Rao
+ PDF Chat	The Communication Complexity of Functions with Large Outputs	2023	Lila Fontes Sophie Laplante Mathieu Laurière Alexandre Nolin
+	Round elimination in exact communication complexity	2018	Jop Briët Harry Buhrman Debbie Leung Teresa Piovesan Florian Speelman
+	On the Interactive Communication Cost of the Distributed Nearest Lattice Point Problem	2018	Vinay A. Vaishampayan Maiara F. Bollauf
+ PDF Chat	Interactive Nearest Lattice Point Search in a Distributed Setting: Two Dimensions	2022	Vinay A. Vaishampayan Maiara F. Bollauf
+ PDF Chat	File Updates Under Random/Arbitrary Insertions and Deletions	2017	Qiwen Wang Sidharth Jaggi Muriel Médard Viveck R. Cadambe Moshe Schwartz
+	On Cooperation in Multi-Terminal Computation and Rate Distortion	2013	Milad Sefidgaran Aslan Tchamkerten
+ PDF Chat	The Infinite-Message Limit of Two-Terminal Interactive Source Coding	2013	Nan Ma Prakash Ishwar
+ PDF Chat	Round complexity in the local transformations of quantum and classical states	2017	Eric Chitambar Min-Hsiu Hsieh
+ PDF Chat	Round Complexity of Common Randomness Generation: The Amortized Setting	2019	Noah Golowich Madhu Sudan
+	Energy Conscious Interactive Communication for Sensor Networks	2007	Samar Agnihotri Pavan Nuggehalli
+	Distributed Function Computation Over a Rooted Directed Tree	2013	Milad Sefidgaran Aslan Tchamkerten
+ PDF Chat	Distributed Function Computation Over a Rooted Directed Tree	2016	Milad Sefidgaran Aslan Tchamkerten
+	On Computing a Function of Correlated Sources	2011	Milad Sefidgaran Aslan Tchamkerten

Citing (0)

Action	Title	Year	Authors