𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Recognition problems and communication complexity

✍ Scribed by Gábor Wiener

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
248 KB
Volume
137
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

A special case of combinatorial search, the recognition problem is examined in this article. (H; A; f) is a recognition problem if H is a set, A is a set system on H and f : H → {0; 1} is a function. Someone chooses an arbitrary x ∈ H and instead of determining x itself (which is the case in most of the search problems) we only have to determine the value f(x) for the given function f from as few questions of type "is x ∈ A?" as possible, where A ∈ A. The smallest number of questions needed in the worst case is called the recognition complexity of f over A on H . After surveying some general results, a new class of set systems is introduced and analyzed, generalizing Yao's model of two-party communication complexity.

📜 SIMILAR VOLUMES

Quantum communication and complexity
Quantum communication and complexity
✍ Ronald de Wolf 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 182 KB

In the setting of communication complexity, two distributed parties want to compute a function depending on both their inputs, using as little communication as possible. The required communication can sometimes be signiÿcantly lowered if we allow the parties the use of quantum communication. We surv

The communication complexity of several
The communication complexity of several problems in matrix computation
✍ Jeff I Chu; Georg Schnitger 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 747 KB

The communication complexity of a function f measures the communication resources required for computingf. In the design of VLSI systems, where savings on the chip area and computation time are desired, this complexity dictates an area x time\* lower bound. We investigate the communication complexit

Matrix rank and communication complexity
Matrix rank and communication complexity
✍ Bruno Codenotti; Gianna Del Corso; Giovanni Manzini 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 76 KB

The rank of a matrix seems to play a role in the context of communication complexity, a framework developed to analyze basic communication requirements of computational problems. We present some issues and open problems arising in this area, and put forward a number of research subjects in linear al

The Structure of Well-Covered Graphs and
The Structure of Well-Covered Graphs and the Complexity of Their Recognition Problems
✍ David Tankus; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 449 KB

A graph is well-covered if all its maximal independent sets are of the same cardinality. Deciding whether a given graph is well-covered is known to be NP-hard in general, and solvable in polynomial time, if the input is restricted to certain families of graphs. We present here a simple structural ch

On Data Structures and Asymmetric Commun
On Data Structures and Asymmetric Communication Complexity
✍ Peter Bro Miltersen; Noam Nisan; Shmuel Safra; Avi Wigderson 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 424 KB

In this paper we consider two-party communication complexity, the ``asymmetric case'', when the input sizes of the two players differ significantly. Most of previous work on communication complexity only considers the total number of bits sent, but we study trade-offs between the number of bits the