Complexity of computations and proofs and pseudo-finite structures
Seminar Room 1, Newton Institute
AbstractProblems to establish lower bounds for circuit size or for lengths of propositional proofs can be formulated as problems to construct expansions of pseudo-finite structures. I will explain this relation, give a few examples, and discuss some recent work aimed at proof complexity.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.