Lectures related to Interactive Proofs: The Power of Interaction

The Power of Interaction: Zero-Knowledge Construction

Explores zero-knowledge construction, setup models, and the power of interaction in cryptographic protocols, including Sigma Protocol and NP Zero-Knowledge Proofs.

Cryptanalysis: Public-Key & The Power of Interaction

Explores cryptanalysis in public-key systems and the power of interaction in interactive proofs, covering CO-NP, NP classes, P vs. NP, and more.

Graphical Models: Representing Probabilistic Distributions

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Complex Systems: Critical Phenomena

Explores critical phenomena in complex systems, including stochastic objects, percolation, and combinatorial optimization.

Complexity & Induction: Algorithms & Proofs

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

Elements of Computational Complexity

Introduces computational complexity, decision problems, quantum complexity, and probabilistic algorithms, including NP-hard and NP-complete problems.

Elements of computational complexity

Covers classical and quantum computational complexity concepts and implications.

Graph Coloring: Theory and Applications

Covers the theory and applications of graph coloring, focusing on disassortative stochastic block models and planted coloring.

Information Measures: Entropy and Information Theory

Explains how entropy measures uncertainty in a system based on possible outcomes.

Sparsest Cut: Bourgain's Theorem

Explores Bourgain's theorem on sparsest cut in graphs, emphasizing semimetrics and cut optimization.

Sparsest Cut: ARV Theorem

Covers the proof of the Bourgain's ARV Theorem, focusing on the finite set of points in a semi-metric space and the application of the ARV algorithm to find the sparsest cut in a graph.

Stein Algorithm: Polynomial Identity Testing

Explores the Stein algorithm for polynomial identity testing and the minimization of a cut problem.

Cryptanalysis: The Power of Interaction

Explores the power of interaction in cryptographic primitives and conventional cryptanalysis techniques.

Promise Constraint Satisfaction and Width

Covers Promise Constraint Satisfaction Problems complexity, width, graph coloring, polymorphisms, and algorithms.

Theory of Computation: Decidability and Complexity

Delves into the theory of computation, covering decidability, complexity, P vs. NP, and reductions.

Theory of Computation: NP Problems Examples

Examines NP problems, graph coloring, path optimization, and computational complexity distinctions in P and NP classes.

Complexity of Algorithms: Big-O Notation

Explores algorithm complexity, big-O notation, induction, recursion, and analysis of running times, covering NP problems and complexity classes.

Topology of Riemann Surfaces

Covers the topology of Riemann surfaces, focusing on orientation and orientability.

Challenges in Bit-Precise Reasoning

Covers challenges in bit-precise reasoning, including SMT-COMP results, AIG, bit-blasting, Tseitin transformation, and complexity classes.

Complexity Classes: P and NP

Explores complexity classes P and NP, highlighting solvable and verifiable problems, including NP-complete challenges.