Kolmogorov-Seminar Courses

Upcrossing Inequalities, Ergodic Theorem and Barmpalias-Lewis-Pye - Part 2

Explore advanced mathematical connections between crossing inequalities, Birkhoff ergodic theorem, and Barmpalias-Lewis-Pye results on Martin-Löf random reals.

• YouTube
• 1 hour 26 minutes
• Self-Paced
• Free Video

Learning Sets - Part 2

Explore advanced learning theory for regular and context-free sets, examining maximal cardinality intersections of finite automata with specified state constraints.

• YouTube
• 1 hour 34 minutes
• Self-Paced
• Free Video

Learning Sets - Introductory Talk

Explore how classical computability-based learning concepts apply to set learning in this foundational seminar on computational complexity theory.

• YouTube
• 2 hours 55 minutes
• Self-Paced
• Free Video

Search Problems - Introduction

Explore computational complexity through existential theorems and search problem reductions, covering decision trees and fixed point theorems in this mathematical seminar.

• YouTube
• 2 hours 4 minutes
• Self-Paced
• Free Video

Tutorial on the Threshold Networks VC-Dimension - Continued - in Russian

Изучите нижние границы VC-размерности для класса функций, вычисляемых пороговыми сетями с аффинными вентилями и p параметрами в рамках семинара Колмогорова.

• YouTube
• 1 hour 48 minutes
• Self-Paced
• Free Video

How to Enumerate Combinatorial Objects Fast

Discover efficient enumeration techniques for combinatorial objects using Hamiltonian paths in Boolean cube polyhedra with minimal delay between consecutive objects.

• YouTube
• 1 hour 35 minutes
• Self-Paced
• Free Video

Search Problems - Part 2

Delve into advanced search problem theory and reduction definitions in computational complexity through detailed mathematical analysis and proofs.

• YouTube
• 1 hour 53 minutes
• Self-Paced
• Free Video

Kolmogorov Seminar on Computational and Descriptional Complexity - Part 3

Explore advanced computational and descriptional complexity concepts in this continuation of Fedor Kiselev's comprehensive seminar series from the renowned Kolmogorov-Seminar.

• YouTube
• 1 hour 49 minutes
• Self-Paced
• Free Video

Bishop's Up Crossing Inequality Revisited

Explore Bishop's constructive approach to sequence convergence through crossing inequalities, following Andreev's proof methods for bounded sequences in computational complexity theory.

• YouTube
• 1 hour 57 minutes
• Self-Paced
• Free Video

Neural Networks and VC-Dimension Tutorial

Explore the theoretical foundations of neural networks through VC-dimension analysis, examining upper bounds for predicates computed by Boolean linear combination networks.

• YouTube
• 2 hours 1 minute
• Self-Paced
• Free Video

One-Way Computable Transformations - The Barmalias-Zhang Example

Dive into the mathematical exploration of one-way computable transformations through the Barmalias-Zhang example, examining its significance in computational complexity theory.

• YouTube
• 1 hour 31 minutes
• Self-Paced
• Free Video

Cutting Figures into Equal Parts Using Grid Lines and SAT Solvers - May 27, 2024

Explore computational techniques for solving geometric cutting problems using SAT solvers, with practical applications in grid-based figure partitioning and combinatorial optimization.

• YouTube
• 2 hours 36 minutes
• Self-Paced
• Free Video

Reconstructing Mean of a Sample with Adversary Errors - April 29, 2024

Delve into advanced statistical techniques for reconstructing sample means affected by adversarial errors using semidefinite programming and sum-of-squares methodology in vector-valued distributions.

• YouTube
• 2 hours 2 minutes
• Self-Paced
• Free Video

Computing Majority of N Using Majority-K Circuits with Logarithmic Depth

Delve into probabilistic constructions and computational complexity, exploring Valiant's theorem on majority functions using Maj-k circuits and their depth analysis.

• YouTube
• 1 hour 50 minutes
• Self-Paced
• Free Video

Полудуплексная Коммуникационная Сложность: Разные Виды Adversary

Dive into the intricacies of half-duplex communication complexity, exploring different adversary types and their impact on complexity measures through concrete examples and theoretical analysis.

• YouTube
• 1 hour 24 minutes
• Self-Paced
• Free Video