Let A_1,...,A_n be events in a probability space. The
approximate inclusion-exclusion problem, due to Linial and
Nisan (1990), is to estimate Pr[A_1 OR ... OR A_n] given
Pr[AND_{i\in S}A_i] for all |S|<=k. Kahn et al. (1996) solve
this problem optimally for each k. We study the following more
general question: ... more >>>

An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by ... more >>>

We present a greatly simplified proof of the length-space
trade-off result for resolution in Hertel and Pitassi (2007), and
also prove a couple of other theorems in the same vein. We point
out two important ingredients needed for our proofs to work, and
discuss possible conclusions to be drawn regarding ... more >>>