Indistinguishability in Counting Logics and the Complexity of Semi-Algebraic Proofs

Add to your list(s) Download to your calendar using vCal

• Atserias, A (Universitat Politcnica de Catalunya)
• Tuesday 27 March 2012, 09:00-10:00
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Semantics and Syntax: A Legacy of Alan Turing

The recent connection between the concept of indistinguishability by the properties expressible in a certain formal language and a relaxation of structural isomorphism through linear programming brings the areas of descriptive complexity and propositional proof complexity a little bit closer together. In this talk I will overview this connection making emphasis on the questions it has answered, but also on the many new exciting questions that it raises.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.