The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Complexity of computations and proofs and pseudo-finite structures

Krajicek, J (Charles University, Prague)
Monday 26 March 2012, 09:30-10:30

Seminar Room 1, Newton Institute


Problems 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.


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧