### Monday, September 28th, 2015

We explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\Omega(1)}. The best previous extractor, by Bourgain, required each source to have min-entropy .499n.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta>0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylog(n)-wise independently, and the remaining q=n^{1-\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q=n^{1/2 - \delta}.

Our explicit two-source extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.

### Tuesday, September 29th, 2015

No abstract available.

I will briefly describe a couple of widely open research directions in Cryptography that are closely related to fine-grained Complexity. First, we will demonstrate the importance of exact hardness bounds through the notion of “proof of work.” Then we will wonder how Cryptographic hardness can be formed.

### Wednesday, September 30th, 2015

### Thursday, October 1st, 2015

In this talk, I will report moderately exponential time satisfiability algorithms for (i) SYM*AND circuits with a slightly superpolynomial number of gates, (ii) THR*THR circuits with a subquadratic number of gates and (iii) XOR*AND*XOR*AND*XOR circuits with a nearly exponential number of gates. The first algorithm is based on backtracking and dynamic programming. The second and third algorithms are based on the polynomial method in Boolean circuit complexity.

The random restriction approach was originally used to prove formula size lower bounds, where it was shown that formulas shrink on average under random restrictions. In several recent works, this result was improved to a concentrated version where formulas shrink with high probability. This concentrated shrinkage property leads to nontrivial algorithms for Formula-SAT, MAX-SAT, etc. In this talk, we will survey techniques in showing concentrated shrinkage, and its applications in designing efficient algorithms.