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

Lecture

Linear Algebra: Efficiency and Complexity

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 concepts of constraints, active constraints, and tight constraints in linear algebra, focusing on efficiency and complexity analysis. It also discusses the relationship between geometry and mathematics, exploring the idea of translating geometric problems into mathematical formulations. The instructor explains the importance of convexity and feasibility in constraint optimization problems, providing examples to illustrate these concepts. Additionally, the lecture delves into the notion of worst-case complexity statements and upper bound phenomena in algorithm analysis, highlighting the differences between various algorithms in terms of efficiency and completion probabilities.

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

Ontological neighbourhood

Theoretical computer science

Theory of computation: Computational complexity theory

Related concepts (32)

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used.

Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.

Color

Color (American English) or colour (Commonwealth English) is the visual perception based on the electromagnetic spectrum. Though color is not an inherent property of matter, color perception is related to an object's light absorption, reflection, emission spectra and interference. For most humans, color are perceived in the visible light spectrum with three types of cone cells (trichromacy). Other animals may have a different number of cone cell types or have eyes sensitive to different wavelength, such as bees that can distinguish ultraviolet, and thus have a different color sensitivity range.

Color theory

In the visual arts, color theory is the body of practical guidance for color mixing and the visual effects of a specific color combination. Color terminology based on the color wheel and its geometry separates colors into primary color, secondary color, and tertiary color. The understanding of color theory dates to antiquity. Aristotle (d. 322 BCE) and Claudius Ptolemy (d. 168 CE) already discussed which and how colors can be produced by mixing other colors. The influence of light on color was investigated and revealed further by al-Kindi (d.

Related lectures (29)

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.

Primal-dual Optimization: Extra-Gradient Method

Explores the Extra-Gradient method for Primal-dual optimization, covering nonconvex-concave problems, convergence rates, and practical performance.

Improved Algorithm: Three-Color Parity Games

Introduces an improved algorithm for three-color parity games, focusing on progress measures, acceleration, and practical speed-up.

Complexity & Induction: Algorithms & Proofs

Covers worst-case complexity, algorithms, and proofs including mathematical induction and recursion.

Coin Rendering: Part 1 MOOC: Information, Computation, Communication: Introduction to computational thinking