### 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

#### Abstract

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.

#### Video

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

## Comments

Start the discussion!