[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

Combinatorics & Theoretical Computer Science Seminar

Tuesday, May 5, 2015
Ryerson 251@ 3:00 pm
 
Prasad Raghavendra
Berkeley EECS
 
Title: “Combinatorial Optimization Algorithms via Polymorphisms”
 
Abstract: An elegant characterization of the complexity of constraint satisfaction problems has emerged in the form of the the algebraic dichotomy conjecture of [BKJ00]. Roughly speaking, the characterization asserts that a CSP {\Lambda} is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to {\Lambda} to create new ones. In an entirely separate line of work, the unique games conjecture yields a characterization of approximability of Max-CSPs. Surprisingly, this characterization for Max-CSPs can also be reformulated in the language of polymorphisms. 
In this work, we study whether existence of non-trivial polymorphisms implies tractability beyond the realm of constraint satisfaction problems, namely in the value-oracle model. Specifically, given a function f in the value-oracle model along with an appropriate operation that never increases the value of f , we design algorithms to minimize f . In particular, we design a randomized algorithm to minimize a function f that admits a fractional polymorphism which is measure preserving and has a transitive symmetry. 
We also reinterpret known results on MaxCSPs and thereby reformulate the unique games conjecture as a characterization of approximability of max-CSPs in terms of their approximate polymorphisms.

This is joint work with Jonah Issac-Brown Cohen.
 
Host by Prof. Madhur Tulsiani
(Refreshments will be served before the talk in Ry. 255@ 2:30pm)
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150427/b87b8856/attachment.htm