Kolmogorov-Seminar Courses

Games on Graphs - Memory Requirements and Strategy Analysis

Explore the theoretical foundations of graph-based games, focusing on strategic approaches, memory requirements, and applications in parity and mean-payoff scenarios.

• YouTube
• 1 hour 36 minutes
• On-Demand
• Free Video

Kraft-Barmpalias-Lewis-Pye Lemma - October 24, 2022

Delve into the layered version of Kraft's lemma, exploring its mathematical foundations and applications in computational complexity theory through expert analysis.

• YouTube
• 1 hour 19 minutes
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• Free Video

Vapnik-Chervonenkis Theorem and Statistical Learning Theory

Dive into the fundamental Vapnik-Chervonenkis theorem, exploring how VC-dimension relates to machine learning generalization and error rates in hypothesis spaces.

• YouTube
• 2 hours 35 minutes
• On-Demand
• Free Video

Combinatorial Rectangles, Kolmogorov Complexity and Experts' Aggregation - March 4, 2024

Delve into communication protocols, exploring their relationship with Kolmogorov complexity, combinatorial rectangles, and the fascinating world of experts' opinion aggregation.

• YouTube
• 2 hours 4 minutes
• On-Demand
• Free Video

Rectangles, Complexity and Games in Communication Theory - December 4, 2023

Delve into communication complexity theory through rectangles, exploring inequality principles, combinatorial strategies, and their applications in computational game theory.

• YouTube
• 1 hour 58 minutes
• On-Demand
• Free Video

Improving Solovay's Theorem - Part 2

Delve into advanced computational complexity theory through an examination of Solovay's theorem improvements, focusing on mathematical proofs and theoretical foundations.

• YouTube
• 1 hour 41 minutes
• On-Demand
• Free Video

Improving Solovay's Theorem in Computational Complexity - Part 1

Delve into computational complexity theory and explore improvements to Solovay's theorem through advanced mathematical analysis and theoretical frameworks.

• YouTube
• 1 hour 36 minutes
• On-Demand
• Free Video

Algebraic Tools for Graph Matchings - November 13, 2023

Delve into advanced algebraic techniques for analyzing perfect matchings in graphs, exploring determinant-based algorithms and derandomization methods for both bipartite and non-bipartite cases.

• YouTube
• 2 hours 16 minutes
• On-Demand
• Free Video

Lempel-Ziv Algorithm: Complexity Analysis and Automaton Conversion

Delve into the Lempel-Ziv algorithm's complexity analysis, exploring its relationship with superadditive functions and automaton conversion principles in computational theory.

• YouTube
• 1 hour 52 minutes
• On-Demand
• Free Video

Automatic Complexity and Block-Entropy Coding - Preparations for Lempel-Ziv Analysis

Explore the mathematical foundations of string complexity through three equivalent measures: block entropy, finite-state transduction, and superadditive functions, leading to Lempel-Ziv compression analysis.

• YouTube
• 1 hour 54 minutes
• On-Demand
• Free Video