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 engage in a matching game with messages of different sizes, aiming to distinguish between them with negligible probability. The lecture explores various conditions and defines the problem, emphasizing the challenge of distinguishing between messages. It provides insights into the indicator function and the implications for most matches. The lecture concludes by highlighting the difficulty of distinguishing between messages, even with small differences, and the negligible probability of success.

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)

Boolean algebra

In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values true and false, usually denoted 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as conjunction (and) denoted as ∧, disjunction (or) denoted as ∨, and the negation (not) denoted as ¬.

Boolean function

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually {true, false}, {0,1} or {-1,1}). Alternative names are switching function, used especially in older computer science literature, and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory. A Boolean function takes the form , where is known as the Boolean domain and is a non-negative integer called the arity of the function.

Boolean expression

In computer science, a Boolean expression is an expression used in programming languages that produces a Boolean value when evaluated. A Boolean value is either true or false. A Boolean expression may be composed of a combination of the Boolean constants true or false, Boolean-typed variables, Boolean-valued operators, and Boolean-valued functions. Boolean expressions correspond to propositional formulas in logic and are a special case of Boolean circuits.

Boolean algebra (structure)

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra (with involution).

Boolean ring

In mathematics, a Boolean ring R is a ring for which x2 = x for all x in R, that is, a ring that consists only of idempotent elements. An example is the ring of integers modulo 2. Every Boolean ring gives rise to a Boolean algebra, with ring multiplication corresponding to conjunction or meet ∧, and ring addition to exclusive disjunction or symmetric difference (not disjunction ∨, which would constitute a semiring). Conversely, every Boolean algebra gives rise to a Boolean ring.

Related lectures (31)

Numbers and Booleans

Introduces numbers and booleans in Python, covering numeric types, arithmetic operations, logical operations, and comparisons.

Boolean Type: Common Errors

Addresses common errors with the boolean type in Java and how to avoid them.

Finite Systems Expressed with Formulas

Explores finite transition systems, propositional logic, truth interpretation, satisfiability, and boolean function representation with circuits.

Theory of Computation: Problems Definition and Counting (Denumerability)

Explores the theory of computation, emphasizing problems definition, counting, and the limits of algorithmic computation.

Boolean Algebra: Python Programming