Uniqueness of Enhancements for Triangulated Categories
I am going to talk about triangulated categories in algebra, geometry and physics and about differential-graded (DG) enhancements of triangulated categories. I will discuss such properties of DG enhancements as uniqueness and existing. It can be proved that a uniqueness of DG enhancements exists for a large class of triangulated categories. This class includes all derived categories of quasi-coherent sheaves, bounded derived categories of coherent sheaves and category of perfect complexes on quasi-projective schemes, as well as on a noncommutative varieties.
General Hardness Amplification of Predicates and Puzzles
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 theorems in the cryptographic setting. This proof seems simpler than previous ones, yet immediately generalizes to statements similar in spirit such as the extraction lemma used to obtain pseudo-random generators from one-way functions [Hastad, Impagliazzo, Levin, Luby, SIAM J. on Comp. 1999].
Non-negatively Weighted #CSPs: An Effective Complexity Dichotomy
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 the celebrated dichotomy theorem for unweighted #CSP. Our dichotomy theorem gives a succinct criterion for tractability. If a set F of constraint functions satisfies the criterion, then the #CSP problem defined by F is solvable in polynomial time; if F does not satisfy the criterion, then the problem is #P-hard.