Iddo Tzameret - Teaching


At Royal Holloway, University of London, I currently teach modules related to knowledge representation and logic in the broad sense. These include the introductive Databases course for undergraduates (2nd year); and an elective advanced course about Semantic Web technologies, which incorporates data representation, the web, markup languages, Ontologies and first order logic (i.e., Description Logic).

At Tsinghua University I used to teach the main theory of computation course. This was a challenging and long (15 weeks) course, incorporating automata theory, Turing machines, computability (recursion) theory (undecidability, Godel's theorem), first order logic and complexity theory (hierarchy theorems; basic complexity classes, reductions, etc.) Additionally, I taught specialized advanced graduate courses on theory of computation and propositional proof complexity.


Databases (undergrad, 2nd year; term 1)

Semantic Web (grad/undergrad; term 1)


Databases (undergrad, 2nd year; term 1)

Semantic Web (grad/undergrad; term 1)

Spring 2014-2015

• No teaching this year

Spring 2013-2014

Theory of Computation (undergrad, 2nd year)

Spring 2012-2013

Theory of Computation (undergrad, 2nd year)

Spring 2011-2012

Theory of Computation (undergrad, 2nd year)

Fall 2011-2012

Computational and Proof Complexity (graduate, advanced TCS 1) (joint with Periklis Papakonstantinou)

  1. NEWEST: Assignment 3 -- not so easy. Due Mon. 7, November, 23:59pm.
    Correction! In Problem 3, you can assume that m>5.199n (and not just m>5.19n, as written). [Thanks to Huacheng Yu.]


  3. Assignment 2.

  4. Update 19 Oct 2011--this is the corrected version of the "correction" for Problem 4 in Exercise 2 (the i and j were erroneously flipped before): This problem would be considered only as a BONUS, because of the confusion.
    Exercise 2: Problem 4, as originally stated was trivially correct (i.e., true by definition). It should have been instead:
    A positive resolution refutation of the PHP(n,n-1) is a sequence of clauses (C1,...,Cm) with only positive literals such that Cm is the empty clause, and every clause Ci is either a Pigeon Axiom or was derived from previous lines Cj,Ck, for j,k < i, via the rule:
    From (A or Rj or Pj) and (B or Sj or Pj) one can derive (A or B or Pj),
    for Rj, Pj and Sj disjoint sets of variables xij, where j is the same and the i's are distinct.
    E.g., Ri={x_(1,2),x_(2,2)}, Pi={x_(5,2),x_(4,2)}, Si={x_(7,2)}.
    Then the aim of the problem is to show that a positive resolution refutation of the PHP(n,n-1) can be transformed with only a polynomial increase in size to a (standard) resolution refutation of PHP(n,n-1).

    Thanks for Huacheng Yu and Zhe Zhang for the corrections.

  5. Sources for the course: (The first item can be found at the iTCS library. The other items can be found easily on the web.)
    (1) Stasys Jukna, Extremal Combinatorics With Applications in Computer Science, 2001, Springer-Verlag, Section 4.8.
    (2) Eli Ben-sasson and Avi Wigderson, Short Proofs are Narrow - Resolution made Simple (2000), JACM.
    (3) P. Beame and T. Pitassi, Propositional proof complexity: Past, present, and future, Current trends in theoretical computer science: Entering the 21st century (G. Paul, G. Rozenberg, and A. Salomaa, editors), World Scientific Publishing, 2001, pp. 42--70.
    (4) Nathan Segerlind, The Complexity of Propositional Proofs, Bull. Symbolic Logic Volume 13, Issue 4 (2007), 417-481.
    (5) Pavel Pudlak, Lower bounds for resolution and cutting planes proofs and monotone computations, The Journal of Symbolic Logic, vol. 62 (1997), no. 3, pp. 981-998.

Fall 2010-2011

      • Algebraic complexity reading group