Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 10,000 papers for “Communication complexity”

Communication complexity

Vojtěch Wagner · Digital Repository (National Repository of Grey Literature) · 2012

Title: Communication Complexity Author: Vojtěch Wagner Department: Department of Algebra Supervisor: prof. RNDr. Jan Krajíček, DrSc. Abstract: This work deals with communication complexity, which considers mo- del of two (or more) parties, each holding its own binary input (let's say x and y). Each of players has information only about his own input. Their common goal is to compute value of some function f(x, y) of these inputs. Communicati- on complexity measures amount of information communicated between players in order to compute f(x, y). This work especially concerns two main models - deterministic, in which all decision made by players is deterministic and they compute the right value in all cases and probabilistic model which allows ran- domized fashion and the goal of the players is to compute the right value with high enough probability. We present some basic concepts and methods to lower bound communication complexity of functions, all ilustrated on some examples of basic functions. In the end we present some complex and practically relevant examples, on which presented methods are demonstrated. Keywords: communication complexity, deterministic communication model, ran- domized model, lower bounds on communication complexity. 1

Cited by 0

Communication Complexity

Eyal Kushilevitz, Noam Nisan · Cambridge University Press eBooks · 1996

Many aspects of the internal and external workings of computers can be viewed as a series of communication processes. Communication complexity is the mathematical theory of such communication processes. It is also often used as an abstract model of other aspects of computation. This book surveys this mathematical theory, concentrating on the question of how much communication is necessary for any particular process. The first part of the book is devoted to the simple two-party model introduced by Yao in 1979, which is still the most widely studied model. The second part treats newer models developed to deal with more complicated communication processes. Finally, applications of these models, including computer networks, VLSI circuits, and data structures, are treated in the third part of the book. This is an essential resource for graduate students and researchers in theoretical computer science, circuits, networks and information theory

Cited by 471

Communication complexity

Christos H. Papadimitriou, Michael Sipser · Journal of Computer and System Sciences · 1984

Cited by 89

Communication Complexity

Hauser, George J. · UR Research (University of Rochester)

Ph.D. Thesis, Computer Science Dept., U. Rochester, Gary L. Peterson, thesis advisor; simultaneously published in the Technical Reprt series

Cited by 0

Communication complexity

Ada, Anil · Library and Archives Canada (Government of Canada) · 2014

Communication complexity studies how many bits a certain number of parties need to communicate with each other in order to compute a function whose input is distributed among those parties. Although it is a natural area of investigation based on practical considerations, the main motivation comes from the myriad of applications in theoretical computer science.This thesis has three main parts, studying three different aspects of communication complexity.1. The first part is concerned with the k-party communication complexity of functions F:({0,1}^n)^k -> {0,1} in the 'number on the forehead' (NOF) model. This is a fundamental model with many applications. In this model we study composed functions f of g. These functions include most of the well-known and studied functions in communication complexity literature. A major goal is to understand which combinations of f and g lead to hard communication functions. In particular, due to important circuit applications, it is of great interest to understand how powerful the NOF model becomes when k is log n or more. Motivated by these goals, we show that there is an efficient O(log^3 n) cost simultaneous protocol for sym of g when k > 1+log n, sym is any symmetric function and g is any function. This class of functions includes some functions that were previously conjectured to be hard and our result rules this class out for possible very important circuit complexity applications. We also give Ramsey theoretic applications of our efficient protocol. In the setting of k < log n, we study more closely functions of the form majority of g, mod_m of g, and nor of g, where the latter two are generalizations of the well-known functions Inner Product and Disjointness respectively. We characterize the communication complexity of these functions with respect to the choice of g. As the main application, we answer a question posed by Babai et al. (SIAM Journal on Computing, 33:137--166, 2004) and determine the communication complexity of majority of qcsb, where qcsb is the "quadratic character of the sum of the bits" function. 2. The second part is about Fourier analysis of symmetric boolean functions and its applications in communication complexity and other areas. The spectral norm of a boolean function f:{0,1}^n -> {0,1} is the sum of the absolute values of its Fourier coefficients. This quantity provides useful upper and lower bounds on the complexity of a function in areas such as communication complexity, learning theory and circuit complexity. We give a combinatorial characterization for the spectral norm of symmetric functions. We show that the logarithm of the spectral norm is of the same order of magnitude as r(f)log(n/r(f)) where r(f) = max(r_0,r_1), and r_0 and r_1 are the smallest integers less than n/2 such that f(x) or f(x)parity(x) is constant for all x with x_1 + ... + x_n in [r_0, n-r_1]. We present some applications to the decision tree and communication complexity of symmetric functions. 3. The third part studies privacy in the context of communication complexity: how much information do the players reveal about their input when following a communication protocol? The unattainability of perfect privacy for many functions motivates the study of approximate privacy. Feigenbaum et al. (Proceedings of the 11th Conference on Electronic Commerce, 167--178, 2010) defined notions of worst-case as well as average-case approximate privacy, and presented several interesting upper bounds, and some open problems for further study. In this thesis, we obtain asymptotically tight bounds on the trade-offs between both the worst-case and average-case approximate privacy of protocols and their communication cost for Vickrey Auction, which is the canonical example of a truthful auction. We also prove exponential lower bounds on the approximate privacy of protocols computing the Intersection function, independent of its communication cost. This proves a conjecture of Feigenbaum et al.

Cited by 0

Communication complexity

Sanjeev Arora, Boaz Barak · Computational Complexity · 2009

In this paper we have studied the information exchange needed, when two processors cooperate to compute Boolean-valued functions.–Andrew Yao, 1979

Cited by 0

Traced communication complexity

Eric Goles, Pierre Guillon, Ivan Rapaport B · 2016

We study cellular automata with respect to a new communication complexity prob-lem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicat-ing as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansiveness, entropy and give the asymptotic communication complexity of most elementary cellular automata. Key words: cellular automata, communication complexity

Cited by 0

Pseudodeterministic Communication Complexity

Göös, Mika, Harms, Nathaniel, Riazanov, Artur et al. · ArXiv.org · 2025

We exhibit an $n$-bit partial function with randomized communication complexity $O(\log n)$ but such that any completion of this function into a total one requires randomized communication complexity $n^{Ω(1)}$. In particular, this shows an exponential separation between randomized and \emph{pseudodeterministic} communication protocols. Previously, Gavinsky (2025) showed an analogous separation in the weaker model of parity decision trees. We use lifting techniques to extend his proof idea to communication complexity.

Cited by 0Open access

Communication complexity comparisons.

Keyan Abdul-Aziz Mutlaq (17833696), Vincent Omollo Nyangaresi (17729636), Mohd Adib Omar (17833699) et al. · Figshare · 2024

<div><p>The incorporation of information and communication technologies in the power grids has greatly enhanced efficiency in the management of demand-responses. In addition, smart grids have seen considerable minimization in energy consumption and enhancement in power supply quality. However, the transmission of control and consumption information over open public communication channels renders the transmitted messages vulnerable to numerous security and privacy violations. Although many authentication and key agreement protocols have been developed to counter these issues, the achievement of ideal security and privacy levels at optimal performance still remains an uphill task. In this paper, we leverage on Hamming distance, elliptic curve cryptography, smart cards and biometrics to develop an authentication protocol. It is formally analyzed using the Burrows-Abadi-Needham (BAN) logic, which shows strong mutual authentication and session key negotiation. Its semantic security analysis demonstrates its robustness under all the assumptions of the Dolev-Yao (DY) and Canetti- Krawczyk (CK) threat models. From the performance perspective, it is shown to incur communication, storage and computation complexities compared with other related state of the art protocols.</p></div>

Cited by 0Open access

Communication and Complexity

Wu, Pei · eScholarship (California Digital Library) · 2021

Communication is a universal process by which two or more individuals exchange information. A communication task that we study involves two (or more) parties, each given their own private input, trying to solve a function f or other computational task on their inputs together. For example, distributed data centers routinely check consistency with each other. An important feature of common communication phenomena is that it is interactive. The parties communicate alternatively and adaptively. This feature is absent in the classical information theory which focuses on one-way transmissions. However, the questions studied in the classical information theory remain valid and vital. For example, how do we minimize the communication cost for a certain communication task and how do we handle noise when it is present. From a historical point of view, theoretical computer scientists initiated the study of communication inspired mostly by complexity theory instead of information theory. The latter source of inspiration motivates many other important questions. For example, how much more power a communication protocol gains given resources like randomness, nondeterminism, or quantum entanglement, etc.In this dissertation, we discuss three concrete problems regarding the above questions. In particular, we study the following three problems.(i) What is the maximum noise rate that can be tolerated in interactive communication? Specifically, we study the general noise model of arbitrary substitutions, deletions, and insertions. We settle this problem by giving a coding scheme that tolerates the maximum noise rate. A combinatorial ingredient of our scheme is that of tree code. We prove the existence of a tree code with strong distance properties.(ii) What is the maximum communication complexity of constant-depth and polynomial-size circuits? We obtain strong communication lower bounds, ruling out the possibility of designing efficient generic communication protocols to solve this important class of problems. Our proof centers around the analytical measures threshold degree and sign-rank. The technique we use settles a 50-year-old problem in threshold degree that has applications to other areas of theoretical computer science including circuits complexity and learning theory.(iii) How much power does a communication protocol gain taking advantage of quantum mechanics? We give a near-optimal separation between quantum and classical communication complexity, exhibiting functions that require only O(\\log n) bits of communication for quantum protocols but any classical protocol needs to essentially exchange the entire input. Our approach first studies the analogous problem in the query model, for which we are able to exhibit an optimal separation. These questions are broadly recognized as being central to understanding the phenomenon of quantum speedups.

Cited by 0Open access

Communication complexity comparisons.

Keyan Abdul-Aziz Mutlaq (17833696), Vincent Omollo Nyangaresi (17729636), Mohd Adib Omar (17833699) et al. · Figshare · 2024

<div><p>The incorporation of information and communication technologies in the power grids has greatly enhanced efficiency in the management of demand-responses. In addition, smart grids have seen considerable minimization in energy consumption and enhancement in power supply quality. However, the transmission of control and consumption information over open public communication channels renders the transmitted messages vulnerable to numerous security and privacy violations. Although many authentication and key agreement protocols have been developed to counter these issues, the achievement of ideal security and privacy levels at optimal performance still remains an uphill task. In this paper, we leverage on Hamming distance, elliptic curve cryptography, smart cards and biometrics to develop an authentication protocol. It is formally analyzed using the Burrows-Abadi-Needham (BAN) logic, which shows strong mutual authentication and session key negotiation. Its semantic security analysis demonstrates its robustness under all the assumptions of the Dolev-Yao (DY) and Canetti- Krawczyk (CK) threat models. From the performance perspective, it is shown to incur communication, storage and computation complexities compared with other related state of the art protocols.</p></div>

Cited by 0Open access

Multiparty Communication Complexity

Eyal Kushilevitz, Noam Nisan · Cambridge University Press eBooks · 1996

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.

Cited by 0

Pseudodeterministic Communication Complexity

Göös, Mika, Harms, Nathaniel, Riazanov, Artur et al. · arXiv (Cornell University) · 2025

We exhibit an $n$-bit partial function with randomized communication complexity $O(\log n)$ but such that any completion of this function into a total one requires randomized communication complexity $n^{Ω(1)}$. In particular, this shows an exponential separation between randomized and \emph{pseudodeterministic} communication protocols. Previously, Gavinsky (2025) showed an analogous separation in the weaker model of parity decision trees. We use lifting techniques to extend his proof idea to communication complexity.

Cited by 0Open access