Видео

In this tutorial we discuss Public-Coin interactive proof systems, aka Arthur-Merlin. We prove the Goldwasser-Sisper theorem, showing that every language that has a private coin protocol, also has a public coin protocol.

In this tutorial we discuss polynomial reductions. Using polynomial reductions we show four languages that are NP-hard.

In this tutorial we discuss randomize computation, in particular the classes ZPP and RL

In this tutorial we define P and NP. We show that the two definitions of NP are equivalent

In this tutorial we discuss Formulas, and the relationship between optimal formula depth for a function to its optimal size.

In this tutorial we discuss non-deterministic Turing machines.

In this tutorial we discuss the alternative definition of the polynomial hierarchy, and prove that it is indeed equivalent to the first definition that we saw.

In this tutorial we discuss Rice's theorem. In addition we present a new technique of proving the decidability of languages called "Configuration Counting."

A video for those who left the lecture and tutorial about reductions still quite confused. Hopefully this will help a bit!

In this tutorial we discuss Turing Machines with an Oracle, relativizing arguments and show that the P vs. NP question cannot be resolved by such an argument.

This tutorial was dedicated to Computational Reductions. We defined and analyzed properties of reductions, and solved three exercises.

In this tutorial we discussed Hierarchy theorems, complexity of function composition, and proved that 2-SAT is NL-complete

The operation of the Turing machine we constructed in Tutorial 1 for the function f(x) = x 1.

In this tutorial we discuss the decidability of languages, and the important difference between accepting a language and deciding a language. We present the main computability classes which we will discuss in the first part of the course - R, RE, coRE.

Theory of Computability - Tutorial 2

Theory of Computability - Tutorial 1

Past exam tutorial Crypto Spring 2024

Tutorial 11 - Interactive Oracle Proofs

Tutorial 2 - Perfect Completeness

Tutorial 8 - LDE Local Correcting

Tutorial 12 - Streaming Interactive Proofs

Tutorial 4 - IP = PSPACE

Tutorial 10 - Collision Resistant Hash Functions

Tutorial 3 - Crypto for ZKP 101

Tutorial 1 - Arthur-Merlin Games

Tutorial 7 - Low-Degree Extensions

Tutorial 9 - Circuit Complexity

Tutorial 3.5 - Crypto for ZKP 101 cont.

Tutorial 5 - Error-Correction Codes