We conclude the course showing that it is possible to study the width of resolution proofs in order to give size lower bounds, via an important size-degree relation. In particular this applies to

• Tseitin formulas

Homework

• Section 18.6, 18.7 [Jukna]

We discuss, via exercises, the equivalence between Decision Trees and Tree-Like Resolutions. We describe the following formulas that are often used examples in proof complexity.

• Ordering Principle
• Pigeonhole principle

We present a Prover-Delayer game on CNFs that provides a good framework to give lower bounds to tree-like resolution refutations. We use it to prove that Tree-Like Resolution cannot prove the ordering principle efficiently, while standard resolution has short proofs of it.

Nevertheless resolution is not all powerful. We give an exponential lower bound to the length of resolution proofs of the pigeonhole principle.

Homework

• Section 15.2.1 [Arora, Barak]
• Section 18.3, 18,4, 18.5 [Jukna]

We introduce the topic of Proof Complexity. We introduce proofs of unsatisfiability for CNF formulas. In particular we discuss Decision Trees and Resoluton. We prove that tree-like Resolution efficiently p-simulates Decision tree.

is equivalent to Decision Trees, and we show a lower bound for Tree-Like Resolution via a Prover-Delayer game.

Homework

• Section 15.1 [Arora, Barak]
• Section 18.1 [Jukna]

Lecture will be in room 1.01 of building D

We introduce randomized protocols and we discuss a Minimax theorem for them. We will use some material from the book of Rao and Yehudayoff.

Homework

• Chapter 3 [Rao, Yehudayoff]

We continue the discussion of communication complexity. We see some applications of communication complexity to lower bounds, and we discuss the rank method to lower bound \(C(f)\). We will use some material from the book of Rao and Yehudayoff.

• Theorem 1.9: \(C(f) = O({(\log \chi(f))}^2)\)
• Theorem 1.7: balancing deterministic protocols

Homework

• Section 13.2.3
• Theorem 1.7, 1.9 [Rao, Yehudayoff]
• Exercises 13.3, 13.9, 13.19

We introduce the model of communication complexity, in particular the deterministic one. We give some examples of applications, and then we describe some techniques to prove lower bounds in this model.

Homework

• Section 13.1, 13.2.1, 13.2.2
• Exercises 13.1, 13.5, 13.9, 13.10

We continue the discussion of decision tree complexity considering randomized trees. We see how they relate with standard trees and how to lower bound them. Then we connect the decision tree complexity to sensitivity, block sensitivity and degree, three parameters of boolean functions. We briefly see how these measures are useful to study parallel computation.

Homework

• Chapter 12
• Exercises 12.1, 12.2, 12.3, 12.4, 12.5, 12.6, 12.7

We discuss a simple and yet fundamental model of computation: decision trees. We define the most important complexity measure over it (worst depth depth), and we put it in connection with another measure of complexity of boolean functions: certificate complexity.

Homework

• Chapter 12
• Exercises 12.1, 12.2, 12.3, 12.4, 12.5, 12.6, 12.7

We discuss some unconditional lower bounds for circuits. We show that there are hard functions, even though we do not know how they look like. Then we show a hierarchy theorem for circuits. After that we show the minimum number of OR and AND gates in a circuit for Parity on \(n\) bits is exactly \(3n-3\).

Homework

• Section 6.5, 6.6
• Theorem 1.29 on Jukna's book

While there are many results proved under the assumption that P is different from NP, there are interesting results that require stronger (but still believable) assumption. We will either prove, sketch the proof or just claim the following results

• \(\mathrm{NP} \subseteq \mathrm{P}/\mathrm{poly}\) implies \(\mathrm{PH} = \Sigma^p_{2} \) [Theorem 6.19]
• if GI is NP-complete, then \(\Sigma^p_{2} = \Pi^p_{2}\) [Theorem 8.18]
• \(\mathrm{BPP} \subseteq \Sigma^p_{2} \cap \Pi^p_{2} \) [Theorem 7.15]

Homework

• Section 6.4, 6.5, 6.6, 7.5, 8.2.4
• Exercises 6.5, 6.6

Note that this lecture will be delivered online because the teacher is sick. Please enter in the zoom session here.

We define the class of problems with polynomial circuits, and we relate with BPP. Then we introduce the Polynomial Hierarchy and sketch some illuminating equivalences between definitions. In particular, depending on time Homework

• Section 5.1, 5.2, 6.1, 6.2
• Exercises 5.1, 6.3

The students will present proofs of NP-completeness for various problems. Each presentation should introduce the problem and explain why it is NP-complete, showing a reduction.

We conclude the discussion about interactive proofs. In particular we see the proof that IP = PSPACE.

• protocol for Graph Non Isomorphism
• coNP \(\in\) IP
• IP = PSPACE

Homework

• Section 8.3
• Exercises 8.8

We conclude the discussion about random computation

• two definitions of ZPP
• ZPP = RP \(\cap\) coRP
• Polynomial identity test in coRP

We study the power of interaction: instead of asking to an all-powerful prover for a single answer (e.g. a witness), we consider an interactive dialog between the prover and the verifier.

• randomness in interaction is necessary
• public vs private randomness
• IP, AM, MA classes
• coNP \(\in\) IP
• IP = PSPACE

Homework

• Section 8.1, 8.2
• Exercises 8.1, 8.2, 8.6

We introduce the use of randomization in computation. We present some examples of randomized processes and computations that seem to be more efficient (either in theory or in practice) than deterministic ones. We define the classes RP, coRP, BPP, and ZPP. We show that problems in BPP have small boolean circuits.

Requirements:

• Appendix A.2

Homework

• Sections 7.1, 7.2 (no 7.2.4), 7.3, 7.4, 7.5 (no 7.5.3)
• Exercises 7.1, 7.4, 7.5, 7.6

We discuss a PSPACE complete problem and its relation with two-players competitive games. We give the proof of Savitch's Theorem (Theorem 4.14). The results immediately leave us wondering if the squaring the space is necessary to get rid of non-determinism. We discuss NL complexity class, and the theory of NL-completeness which revolves around logspace reductions. We show Theorem 4.18 and Theorem 4.20.

Homework

• Sections 4.2, 4.3
• Exercises 4.4, 4.5, 4.6, 4.7, 4.8, 4.9, 4.11

We finish the proof of Theorem 3.7, then we introduce the study of Space Complexity. This is the study of how much memory is needed to decide a language. A core concept is the configuration graph of a (non)-deterministic computation. We introduce the complexity classes related to space, and the class PSPACE. Homework

• Sections 4.1
• Exercises 4.1, 4.2, 4.10

Additional resource: wikipedia page on Game Complexity

We prove some real lower bounds on general Turing machines, using the Time Hierarchy Theorems. We state Ladner's Theorem. Then we discuss the topic of machines with Oracle and the limits of diagonalization. We proved Theorem 3.1, sketched the proof of Theorem 3.2, stated Theorem 3.3 and started the proof of Theorem 3.7.

Homework

• Sections 3.1, 3.2, 3.3, 3.4

We discuss and define classes as coNP, EXP, NEXP: their definitions and their relations. We discuss more about the implications of P=NP and of P different from NP. How do we overcome worst case hardness?

Homework

• Sections 2.6, 2.7
• Exercises 2.23, 2.24, 2.25, 2.26, 2.27, 2.29, 2.30, 2.31, 2.34.

Now the we know that 3-SAT is NP-complete, we see easily that there are many others NP-complete like Independent Set, or Clique, or Hamiltonian Path/Cycle. We can prove that via Karp reductions to 3-SAT.

We discuss the difference between Decision and Search.

Homework

• Sections 2.4, 2.5
• Exercises 2.14, 2.15, 2.16, 2.17, 2.18, 2.21.

Using the notion of polynomial reduction we discuss the notions of NP-hardness and NP-completeness: : we identify problems that are as hard (or more) than any other problem in NP.

We see a different ways to define NP: via a non-deterministic Turing Machine.

We discuss Cook-Levin theorem which shows that SAT (or even 3-SAT) is an NP-complete problems. Via the notion of reduction we see that many other problems are indeed NP-complete.

Homework

• Sections 2.2, 2.3 (without section 2.3.4), 6.1
• Exercises 2.6, 2.7, 2.8, 2.9, 2.10, 2.11, 2.12

We discuss the class NP, the class of decision problems that have short certificates/witness of the yes instances. This class models what we usually think as puzzles. There is one or more solutions that are easy to verify but maybe hard to find. Indeed for many decision problems in NP we do not know how to decide them We see different ways to define NP: via (1) a verifier (2) a non-deterministic Turing Machine.

We introduce (without proof for now) the Cook-Levin theorem which shows that SAT (or even 3-SAT) is an NP-complete problems. Via the notion of reduction we see that many other problems are indeed NP-complete.

Homework

• Sections 2.1, 2.2
• Exercises 2.1, 2.2, 2.4

We discuss basic results on uncomputability and then introduce the class P of polynomially decidable languages. We discuss pro and cons on using P as notion of efficiency.

Uncomputability

• Function UC
• Halting problem
• Gödel Theorem (proof idea)

Homework

• Sections 1.5, 1.6.
• Exercises 1.8, 1.14.

We recap the definition of Turing machines and discuss basic properties. We see an example on how to check a palindrome binary string in linear time.

Robustness of definitions

• number of tapes
• random acess memory (think about Exercise 1.9)
• size of the alphabeth
• obliviousness
• variants on tape structure

Universality

• Encoding a machine as a string
• Universal Turing machine: statement of Theorem 1.9
• Machine with timer

Homework

• Sections 1.1, 1.2, 1.3, 1.4.
• Exercises 1.2, 1.3, 1.5.

Introduction of the course, and of the topic of computationa complexity. We discussed generically what it means to prove a lower bound, i.e., to show that it is impossible to compute some function within a certain amount of resources.

An impossibility result is a mathematical statement about a computational model. We can focus on powerful computational model and only prove weak and conditional lower bounds, and we can consider concrete and restricted models where we can prove tight one.

We saw the example of two loer bounds:

• Parity on \(n\) variables requires CNF formulas of size \(\Theta(n 2^n)\)
• (Sketch) Equality of two strings of \(n\) bits requires \(n\) bits of communication.

Homework:

• read Introduction and Chapter 0 of textbook [AB]