Lecture

Von Neumann Extractor: Optimal Binary Extraction Procedure

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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, aiming to provide and analyze an asymptotically optimal extractor for binary strings. It explains the extraction procedure, proving uniformity, rate computation, and the recursion relation for the extraction rates. The lecture concludes with Propositions regarding the convergence of the extraction rates and the fixed point of the extraction operator.

Instructor

Yanina Yurina Shkel

Teaching & PhD PhD Students Serhat Emre Coban, Anuj Kumar Yadav, Cemre Çadir Courses Advanced probability and applications COM-417 In this course, various aspects of probability theory are considered. The first part covers the main theorems in the field (law of large numbers, central limit theorem), while the second part focuses on the theory of martingales and concentration inequalities. Signal processing COM-202 Signal processing theory and applications: discrete and cont

Official source

Related concepts (32)

Uniform convergence

In the mathematical field of analysis, uniform convergence is a mode of convergence of functions stronger than pointwise convergence. A sequence of functions converges uniformly to a limiting function on a set as the function domain if, given any arbitrarily small positive number , a number can be found such that each of the functions differs from by no more than at every point in .

Recursion (computer science)

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science. The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement.

Uniform

A uniform is a variety of costume worn by members of an organization while participating in that organization's activity. Modern uniforms are most often worn by armed forces and paramilitary organizations such as police, emergency services, security guards, in some workplaces and schools and by inmates in prisons. In some countries, some other officials also wear uniforms in their duties; such is the case of the Commissioned Corps of the United States Public Health Service or the French prefects.

Recursion

Recursion occurs when the definition of a concept or process depends on a simpler version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references can occur.

Course-of-values recursion

In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function f by course-of-values recursion, the value of f(n) is computed from the sequence . The fact that such definitions can be converted into definitions using a simpler form of recursion is often used to prove that functions defined by course-of-values recursion are primitive recursive.

Related lectures (53)

1e Particle motion in given electromagnetic fields: the drifts

Function Approximations

Covers continuous functions with compact support, density, and approximation, focusing on the heat equation.

Characteristic Functions: Definition and Properties

Covers characteristic functions for random variables and their properties, including independence and convergence.

Dirichlet Series

Explores Dirichlet series convergence properties and absolute convergence conditions, with examples and applications.

Convergence of Numerical Sequences