Kolmogorov-Seminar Courses

Existence of Key Generation Protocol and Kolmogorov Complexity - Iteration 2

Explore the relationship between key-agreement protocols and interactive Kolmogorov complexity, with a generalized statement and concise proof of the difficult implication.

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

Different Complexity Notions in Physical Context - From Pattern Recognition to Quantum Systems

Explore complexity theories in condensed matter physics, examining pattern complexity definitions and Boolean function analysis in quantum magnetic systems through physical and mathematical perspectives.

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

Randomized Complexity of Approximate Matrix Rank in Communication Protocols - Part 2

Delve into advanced matrix rank approximation in communication complexity, exploring computational challenges when Alice and Bob collaborate to determine matrix sum ranks.

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

Littlestone Dimension, Trees and Threshold Dimension

Delve into advanced computational complexity concepts, focusing on Littlestone dimension, its relationship with trees, and threshold dimension in online learning algorithms.

• YouTube
• 1 hour 44 minutes
• 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

Effective Littlestone Dimension - Part 3

Delve into the exploration of bounded effective Littlestone dimension and its implications for computational complexity in this Kolmogorov seminar presentation.

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

Interactive Kolmogorov Complexity and Key Agreement - Simplified Proof

Delve into the relationship between key-agreement protocols and Kolmogorov complexity, exploring a simplified proof of their equivalence in cryptography.

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

Halving Complexity by Oracles?

Explore the intriguing question of whether oracles can halve computational complexity, examining counterexamples using random pairs in affine planes and their implications for Kolmogorov complexity theory.

• YouTube
• 1 hour 52 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

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
• Self-Paced
• 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
• Self-Paced
• 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
• Self-Paced
• Free Video