In this talk, I will give new proofs for the hardness
amplification of fficiently samplable predicates and of weakly
verifiable puzzles. More oncretely, in the first part of the talk,
I will give a new proof of Yao's XOR-Lemma as well as
related...
We prove a complexity dichotomy theorem for all non-negatively
weighted counting Constraint Satisfaction Problems (#CSP). This
caps a long series of important results on counting problems
including unweighted and weighted graph homomorphisms and...
