[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

Combinatorics & Theoretical Computer Science Seminar

Albert Atserias
Universitat Politecnica de Catalunya
www.cs.upc.edu/~atserias/

Tuesday, October 13, 2015
Ryerson 251 @ 3:00pm
Title: The Problem of Isomorphism-Invariant Polynomial-Time Computation

Abstract:
An algorithm that takes labelled graphs as inputs is called isomorphism-invariant if its output does not depend on the concrete given labelling of the underlying abstract graph. The problem of characterizing the class of decision problems that can be solved by an isomorphim-invariant algorithm in polynomial time is sometimes called the fundamental problem of descriptive complexity. In this talk I will survey some old and recent results on this problem and some of its consequences for the theory of linear programming extended formulations and the proof complexity of the graph non-isomorphism problem.

Host: Prof. Razborov

(Refreshments will be served prior to the talk I Ry. 255 at 2:30 pm)

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20151008/12023b1f/attachment.htm