Kolmogorov-Seminar Courses

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
• On-Demand
• Free Video

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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• 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