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

Homework

• Section 19.1, 19.2 [Jukna]

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.

Homework

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

We describe the Ordering Principle formula, which is hard for tree-like resolution but has a resolution refutation of polynomial size.

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 show both statements.

Homework

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

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 trees, andd we show a lower bound for Tree-Like Resolution via a Prover-Delayer game.

Homework

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

We conclude the discussion of deterministic communication complexity, showing

• connections between communication matrix and its rank
• Theorem 1.7 [Rao and Yehudayoff]: balancing deterministic protocols

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

Homework

• Theorem 1.7 [Rao and Yehudayoff]: balancing deterministic protocols
• Chapter 3 [Rao and Yehudayoff]: sections
  • "Some protocols" (equality, greater than)
  • "Randomized Communication complexity"
  • "Error reductions"
• Theorem 3.5 [Rao and Yehudayoff]: Public to Private coins
• Section 13.2.3 [Boaz and Barak]

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

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, 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 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 the Certificate complexity and its connection with Decision tree complexity.

Homework

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

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 discuss a simple and yet fundamental model of computation: decision trees. We define the most important complexity measure over it (worst depth depth).

Homework

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

We conclude the discussion about interactive proofs. We will prove:

• Graph Non Isomorphism is in IP
• coNP \(\subseteq\) IP
• TQBF \(\in\) IP

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

Homework

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

The lecture is going to be cancelled because the lecturer is sick

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.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.

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).

Homework

• Sections 4.1 (no 4.1.3), 4.2
• Exercises 4.1, 4.2, 4.10

Additional resource: wikipedia page on Game Complexity

We continue with randomized computation. We give another example of randomized algorithm (findind the median) which is simpler than the corresponding deterministic version.

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.

Requirements:

• Appendix A.2

Homework

• Same as last lecture.

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, and ZPP.

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

• Randomized primality test
• Polynomial Identity Test

Requirements:

• Appendix A.2

Homework

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

We further discuss the complexity class P/poly, define both as the class of languages with polynomial size circuits. We show that P/poly contains non-computable languages.

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.1, 6.3, 6.5
• Theorem 1.29 on Jukna's book

We conclude the proof that 3-SAT is NP-complete, we see easily that there are many others NP-complete like Independent Set, or Clique, or Vertex cover.

We discuss and define class coNP, and its relation with NP.

We discuss the difference between Decision, Search and Optimization.

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 prove Theorem 2.9 to give a canonical (even if not interesting) NP-complete problem.

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.3 (without section 2.3.4), 6.1
• Exercises 2.15, 2.16, 2.17, 2.18
• 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 the previous definition.

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 and that 3-SAT reduces to INDSET.

We introduce (without proof for now) the Cook-Levin theorem which claims that SAT (or even 3-SAT) is an NP-complete problems.

Homework

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

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.

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. To do (2) we define NTIME.

Homework

• Sections 1.6, 2.1.
• Exercises 1.8, 1.14, 2.1, 2.2.

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 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

Uncomputability

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

Homework

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

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]