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

Lecture

Forkas Lemma: Theorem of the Alternatives

In course

MATH-261: Discrete optimization

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems. ...

Description

This lecture covers the Forkas Lemma and the Theorem of the Alternatives, focusing on solving systems of linear equations and the existence of solutions. Topics include vectors, certificates, and the implications of different scenarios.

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

Instructors (2)

Rom Pinchasi

Friedrich Eisenbrand

Friedrich Eisenbrand's main research interests lie in the field of discrete optimization, in particular in algorithms and complexity, integer programming, geometry of numbers, and applied optimization. He is best known for his work on efficient algorithms for integer programming in fixed dimension and the theory of cutting planes, which are an important tool to solve large scale industrial optimization problems in practice. Before joining EPFL in March 2008, Friedrich Eisenbrand was a full professor of mathematics at the University of Paderborn. Friedrich received the Heinz Maier-Leibnitz award of the German Research Foundation (DFG) in 2004 and the Otto Hahn medal of the Max Planck Society in 2001.

Official source

Related concepts (27)

Public key certificate

In cryptography, a public key certificate, also known as a digital certificate or identity certificate, is an electronic document used to prove the validity of a public key. The certificate includes information about the key, information about the identity of its owner (called the subject), and the digital signature of an entity that has verified the certificate's contents (called the issuer). If the signature is valid, and the software examining the certificate trusts the issuer, then it can use that key to communicate securely with the certificate's subject.

Root certificate

In cryptography and computer security, a root certificate is a public key certificate that identifies a root certificate authority (CA). Root certificates are self-signed (and it is possible for a certificate to have multiple trust paths, say if the certificate was issued by a root that was cross-signed) and form the basis of an X.509-based public key infrastructure (PKI). Either it has matched Authority Key Identifier with Subject Key Identifier, in some cases there is no Authority Key identifier, then Issuer string should match with Subject string ().

Euclidean vector

In mathematics, physics, and engineering, a Euclidean vector or simply a vector (sometimes called a geometric vector or spatial vector) is a geometric object that has magnitude (or length) and direction. Vectors can be added to other vectors according to vector algebra. A Euclidean vector is frequently represented by a directed line segment, or graphically as an arrow connecting an initial point A with a terminal point B, and denoted by . A vector is what is needed to "carry" the point A to the point B; the Latin word vector means "carrier".

Extended Validation Certificate

An Extended Validation Certificate (EV) is a certificate conforming to X.509 that proves the legal entity of the owner and is signed by a certificate authority key that can issue EV certificates. EV certificates can be used in the same manner as any other X.509 certificates, including securing web communications with HTTPS and signing software and documents. Unlike domain-validated certificates and organization-validation certificates, EV certificates can be issued only by a subset of certificate authorities (CAs) and require verification of the requesting entity's legal identity before certificate issuance.

Linear equation

In mathematics, a linear equation is an equation that may be put in the form where are the variables (or unknowns), and are the coefficients, which are often real numbers. The coefficients may be considered as parameters of the equation, and may be arbitrary expressions, provided they do not contain any of the variables. To yield a meaningful equation, the coefficients are required to not all be zero. Alternatively, a linear equation can be obtained by equating to zero a linear polynomial over some field, from which the coefficients are taken.

Related lectures (39)

Elements of Lie Groups and Algebras

Explores the transformation of vectors and tensors in quantum physics, emphasizing Lie groups and algebras.

Vector Transformation and Tense

Explores the transformation of vectors and tensors, including rotations and representations in quantum physics.

Untitled

Indicial Notation and Vectors

Explores indicial notation, vectors, and the transformation law in the context of mass flux density.

Linear Independence and Basis