Complexity of computations and proofs and pseudo-finite structures
1 hour 4 mins 24 secs,
268.17 MB,
Flash Video
484x272,
29.97 fps,
44100 Hz,
568.54 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Krajicek, J (Charles University, Prague)
Monday 26 March 2012, 09:30-10:30 |
|---|
| Created: | 2012-03-30 10:57 |
|---|---|
| Collection: | Semantics and Syntax: A Legacy of Alan Turing |
| Publisher: | Isaac Newton Institute |
| Copyright: | Krajicek, J |
| Language: | eng (English) |
| 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. |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.84 Mbits/sec | 893.06 MB | View | Download | |
| WebM | 640x360 | 1.14 Mbits/sec | 550.00 MB | View | Download | |
| Flash Video * | 484x272 | 568.54 kbits/sec | 268.17 MB | View | Download | |
| iPod Video | 480x270 | 506.12 kbits/sec | 238.73 MB | View | Download | |
| MP3 | 44100 Hz | 125.02 kbits/sec | 58.83 MB | Listen | Download | |
| Auto | (Allows browser to choose a format it supports) | |||||