Iddo Tzameret  Teaching
Summary
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.
20162017
•
Databases (undergrad, 2nd year; term 1)
•
Semantic Web (grad/undergrad; term 1)
20152016
•
Databases (undergrad, 2nd year; term 1)
•
Semantic Web (grad/undergrad; term 1)
Spring 20142015
•
No teaching this year
Spring 20132014
Spring 20122013
Spring 20112012
Fall 20112012
•
Computational and Proof Complexity (graduate, advanced TCS 1) (joint with Periklis Papakonstantinou)

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

NEW: CLASS SCRIBES!!

Assignment 2.

Update 19 Oct 2011this 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,n1) 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,n1) can be transformed with only a polynomial increase in size to a (standard) resolution refutation of PHP(n,n1).
Thanks for Huacheng Yu and Zhe Zhang for the corrections.
 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, SpringerVerlag, Section 4.8.
(2) Eli Bensasson 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. 4270.
(4) Nathan Segerlind, The Complexity of Propositional Proofs, Bull. Symbolic Logic Volume 13, Issue 4 (2007), 417481.
(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. 981998.
Fall 20102011