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

Lecture

Von Neumann Extractor: Extensions

In course

COM-622: Topics in information-theoretic cryptography

Information-theoretic methods and their application to secrecy & privacy. Perfect information-theoretic secrecy. Randomness extraction & privacy amplification. Secret key generation from common randomness. Measures of information leakage incl. differential ...

Description

This lecture covers the von Neumann Extractor and its extensions, aiming to derive and analyze an optimal extractor for binary i.i.d. sequences. It introduces the concept of extraction procedures, defining them as mappings with specific properties. The lecture discusses the rate of extraction procedures and provides examples to illustrate the concepts presented.

Instructor

Yanina Yurina Shkel

Official source

Related concepts (5)

Asymptotic analysis

In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior. As an illustration, suppose that we are interested in the properties of a function f (n) as n becomes very large. If f(n) = n2 + 3n, then as n becomes very large, the term 3n becomes insignificant compared to n2. The function f(n) is said to be "asymptotically equivalent to n2, as n → ∞". This is often written symbolically as f (n) ~ n2, which is read as "f(n) is asymptotic to n2".

Asymptotic expansion

In mathematics, an asymptotic expansion, asymptotic series or Poincaré expansion (after Henri Poincaré) is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation to a given function as the argument of the function tends towards a particular, often infinite, point. Investigations by revealed that the divergent part of an asymptotic expansion is latently meaningful, i.e. contains information about the exact value of the expanded function.

Analysis of algorithms

In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the size of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input.

Self-replicating spacecraft

The concept of self-replicating spacecraft, as envisioned by mathematician John von Neumann, has been described by futurists including physicist Michio Kaku and discussed across a wide breadth of hard science fiction novels and stories. Self-replicating probes are sometimes referred to as von Neumann probes. Self-replicating spacecraft would in some ways either mimic or echo the features of living organisms or viruses.

Self-replicating machine