We describe the Pigeonhole Principle, which is hard for resolution. Pigeonhole principle proof complexity in tree-like resolution is \(2^{\Theta(n \log n)}\), and we briefly describe the upper bound.

We can easily show that \(2^{\Omega(n)}\) is required for tree-like resolution using the Prover-Delayer game, but we can show formally that this game cannot give a tight lower bound.

We show instead that the proof complexity in resolution is \(2^{\Theta(n)}\) and we give both the upper and the lower bound.

If times permits we describe the cutting planes proof system: we show that it p-simulates resolution, and that it refutes Pigeonhole principle efficiently.

Homework

• Section 15.2.1 [Arora, Barak]
• Section 18.5 [Jukna]
• Section 19.1, 19.2 [Jukna]

Codice OPIS: H0W6430W

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.

We briefly discussed the definition of the Cutting Planes proof system.

Codice OPIS: H0W6430W

Homework

• 18.3, 18,4 [Jukna]
• Knuth, the Art of Computer Programming Vol.4B [Page 238/239]

We discuss proofs of unsatisfiability via Decision Trees and Resoluton. We prove that tree-like Resolution efficiently p-simulates Decision trees.

We We describe the Pigeonhole principle and the Ordering Principle formula. The former is hard for resolution, and the latter is hard for tree-like resolution but has a resolution refutation of polynomial size.

Homework

• Section 18.1 [Jukna]

We conclude the discussion on Communication complexity briefly describing a randomized model, and the we show two applications for lower bound of streaming algorithms. Then we introduce the topic of Proof Complexity, and the problem of showing unsaisfiability of CNF formulas.

Homework

• Section 15.1 [Arora, Barak]

We continue with the student presentations.

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 continue the discussion of communication complexity, and the fundamental interpretation of the protocol as partition of a matrix into monochromatic combinatorial rectangles. We see some applications of communication complexity to lower bounds, and we discuss few methods of lower bounding \(C(f)\).

• fooling set method
• tiling method
• rank methods

We will use some material from the book of Rao and Yehudayoff.

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

Homework

• Section 13.2.1, 13.2.2, 13.2.3
• Theorem 1.7, 1.9, 1.18 [Rao, Yehudayoff]
• Exercises 13.1, 13.2, 13.3 (careful), 13.4, 13.5, 13.9, 13.10, 13.16, 13.17, 13.19

Many of these exercises have hints for solutions in the book, and moreover we will see together some of the solutions in class, in particular 13.3, 13.16, 13.19

We concluded with the relations between various complexity measures for boolean functions.

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

We show the connections between certificate and decision tree complexity, then 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, via min-max theorem.

Homework

• Sections 12.3, 12.4.1
• Exercises 12.1, 12.2, 12.3 (ignore \(s(f)\) and \(bs(f)\)), 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 case depth) and see how it is connected to size. We also study certificate complexity and it's connection with decision tree complexity.

Homework

• Sections 12.1, 12.2, Definition 12.13
• Exercises 12.1, 12.2, 12.3 (ignore \(s(f)\) and \(bs(f)\)), 12.5, 12.6, 12.7

Please fill the OPIS form for this course

• instruction: download here.
• OPIS code: H0W6430W

We continue the discussion about interactive proofs. We will discuss:

• Graph Non Isomorphism is in AM (no proof)
• GI is probably non NP-complete
• coNP \(\subseteq\) IP
• TQBF \(\in\) IP

Homework

• Section 8.2.4, Section 8.3, Section 8.4
• Exercise 8.3 (variant: show that AM is in PH)

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
• interactive proof of Graph non-Isomorphism
• power of provers, IP in PSPACE
• public vs private randomness
• Theorem 8.12 with no proof: \(IP[k] \subseteq AM[k+2]\) for any polynomial \(k(n)\).
• Exercise 8.7 with no proof: \(AM[k+1] \subseteq AM[k]\) for any constant \(k\).
• IP, AM, MA classes

Homework

• Section 8.1, 8.2 (Up to Theorem 8.13, with no proof)
• Exercises 8.1, 8.2, 8.6, 8.8

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). Savitch's theorem immediately leaves 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.3, 4.4, 4.5, 4.7, 4.8, 4.9, 4.11

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 (no 4.1.3)
• Exercises 4.1, 4.2, 4.10

Additional resource: wikipedia page on Game Complexity

We continue with randomized computation. We give other examples of randomized algorithm (polynomial identity testing, findind the median).

We define zero-error class ZPP, and then we define the class BPP, which allows two-sided error. We discuss the reduction of the error via repetition, using Chernoff bound. We show that problems in BPP have small boolean circuits, and that BPP is in the polynomial hierarchy.

Requirements:

• Appendix A.2

Homework

• Sections 7.4, Theorem 7.14 and 7.15
• Same as last lecture.

We recap last lecture, plus Theorem 6.19 and Exercises 6.5 and 6.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.

We discuss the amplification of confidence of the algorithm by repetition.

• finding the median
• Randomized primality test

Requirements:

• Appendix A.2

Homework

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

Please fill the OPIS form for this course

• instruction: download here.
• OPIS code: H0W6430W

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 Theorem 3.7. We discuss

Homework

• Sections 3.1, 3.2, 3.3, 3.4, 5.1, 5.2, 5.5
• Exercises 5.1, 5.10, 5.12, 6.5, 6.6 (see Karp-Lipton theorem)

Please fill the OPIS form for this course

• instruction: download here.
• OPIS code: H0W6430W

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
• Theorem 1.29 on Jukna's book

We discuss and define class coNP, and its relation with NP. We also discuss the difference between Decision, Search and Optimization.

We further discuss the complexity class P/poly, define either as the class of languages with polynomial size circuits, or as the class with polynomial running time and polynomial advice. We show that P/poly contains non-computable languages.

Homework

• Section 6.1, 6.2, 6.3

We see easily that there are many others NP-complete, reducing to Independent Set, Clique, Vertex cover or Hamiltonian-Path. Homework

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

We introduce boolean circuits, and we discuss Circuit-SAT. We prove that Circuit-SAT reduces to 3-SAT. We start the proof of Cook-Levin Theorem, using a variant of Theorem 6.6 instead of Lemma 2.11.

Homework

• Sections 2.4, 6.1
• Exercises 2.15, 2.16, 2.17, 2.18, 6.1
• Prove that any boolean circuit of size \(S\) on \(n\)-variables can be converted to the DeMorgan format, so that the new circuit has size at most \(2 S\).
• Prove that any function \(f:\{0,1\}^n \longrightarrow \{0,1\}\) can be computed by a CNF of size \(O(n 2^n)\).
• Prove that any function \(f:\{0,1\}^n \longrightarrow \{0,1\}\) can be computed by a boolean circuit of size \(O(2^n)\).
• Check exercise 6.1 to see that the previous upper bound can be improved.

We see a different definition of NP via non-deterministic Turing Machines, and we prove the equivalence with previous definitions.

We introduce 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 efficiently. This is the question "P vs NP".

We see nevertheless that NP is inside EXP.

Using the notion of polynomial reduction (or Karp reduction) we discuss NP-hardness and NP-completeness: we identify problems that are as hard (or more) than any other problem in NP. We show that SAT reduces to 3-SAT.

We prove Theorem 2.9 to give a canonical (even if not interesting) NP-complete problem. Then we introduce (without proof for now) the Cook-Levin theorem which claims that SAT (or even 3-SAT) is NP-complete.

Homework

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

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. Then we discuss basic results on uncomputability.

Robustness of definitions

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

Universality

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

Uncomputability

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

We define DTIME. We introduce the class P of polynomially decidable languages and we discuss pro and cons on using P as notion of efficiency.

Homework

• Sections 1.1, 1.2, 1.3, 1.4, 1.5, 1.6
• Exercises 1.2, 1.3, 1.5, 1.8, 1.14

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]