Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Boolean Hidden Matching Problem

Description

This lecture covers the Boolean Hidden Matching Problem, where Alice and Bob aim to find a matching of size n without revealing their inputs. The slides discuss message matching, total communication, and applications to lower bounds.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Mikhail Kapralov

Official source

Related concepts (32)

Hardware random number generator

In computing, a hardware random number generator (HRNG), true random number generator (TRNG) or non-deterministic random bit generator (NRBG) is a device that generates random numbers from a physical process capable of producing entropy (in other words, the device always has access to a physical entropy source), rather than by means of an algorithm. Such devices are often based on microscopic phenomena that generate low-level, statistically random "noise" signals, such as thermal noise, the photoelectric effect, involving a beam splitter, and other quantum phenomena.

Models of communication

Models of communication are simplified representations of the process of communication. Most models try to describe both verbal and non-verbal communication and often understand it as an exchange of messages. Their function is to give a compact overview of the complex process of communication. This helps researchers formulate hypotheses, apply communication-related concepts to real-world cases, and test predictions. Despite their usefulness, many models are criticized based on the claim that they are too simple because they leave out essential aspects.

Randomness

In common usage, randomness is the apparent or actual lack of definite pattern or predictability in information. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual random events are, by definition, unpredictable, but if the probability distribution is known, the frequency of different outcomes over repeated events (or "trials") is predictable. For example, when throwing two dice, the outcome of any particular roll is unpredictable, but a sum of 7 will tend to occur twice as often as 4.

Communication

Communication is usually defined as the transmission of information. The term can also refer to the message itself, or the field of inquiry studying these transmissions, also known as communication studies. The precise definition of communication is disputed. Controversial issues are whether unintentional or failed transmissions are included and whether communication does not just transmit meaning but also create it. Models of communication aim to provide a simplified overview of its main components and their interaction.

Communication protocol

A communication protocol is a system of rules that allows two or more entities of a communications system to transmit information via any variation of a physical quantity. The protocol defines the rules, syntax, semantics, and synchronization of communication and possible error recovery methods. Protocols may be implemented by hardware, software, or a combination of both. Communicating systems use well-defined formats for exchanging various messages.

Related lectures (36)

Communication Amid Uncertainty

Explores challenges in human communication, context importance, compression problems, uncertain functionality, and proof verification.

Data Storage and Transmission Protocols

Explores data structure, storage, network protocols, communication rules, and message encapsulation in transmission systems.

Untitled

Probability and Statistics

Introduces probability, statistics, distributions, inference, likelihood, and combinatorics for studying random events and network modeling.

Filtering and Sampling of Signals