COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Cambridge Algorithms talks > The complexity of finite-valued CSPs

## The complexity of finite-valued CSPsAdd to your list(s) Download to your calendar using vCal - Stanislav Zivny (University of Oxford)
- Monday 09 June 2014, 10:00-11:00
- Computer Laboratory, Room FW26.
If you have a question about this talk, please contact Dr Thomas Sauerwald. Let L be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. We are interested in the problem of minimising a function given explicitly as a sum of functions from L. We establish a dichotomy theorem with respect to exact solvability for all finite-valued languages defined on domains of arbitrary finite size. We present a simple algebraic condition that characterises the tractable cases. Moreover, we show that a single algorithm based on linear programming solves all tractable cases. Furthermore, we show that there is a single reason for intractability; namely, a very specific reduction from Max-Cut. (based on work published at FOCS ’12 and STOC ’13, joint work with J.Thapper) This talk is part of the Cambridge Algorithms talks series. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Cambridge Algorithms talks
- Cambridge talks
- Computer Laboratory talks
- Computer Laboratory, Room FW26
- Interested Talks
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
Note that ex-directory lists are not shown. |
## Other listsBrain and Consciousness CTSRD - CRASH-worthy Trusted Systems R&D Sir Andrew Motion Visits Cambridge in War Poets Event Peptide Mini-Symposium Computer Laboratory Computer Architecture Group Meeting One Day Meeting - 5th Annual Symposium of the Cambridge Computational Biology Institute## Other talksMeasuring Designing: Design Cognitiometrics, Physiometrics & Neurometrics Ethics for the working mathematician, seminar 11: Winning with mathematics The Object of My Affection: stories of love from the Fitzwilliam collection Adaptation in log-concave density estimation Exploring the Galaxy's alpha-element abundances and globular cluster populations with hydrodynamic simulations Panel comparisons: Challenor, Ginsbourger, Nobile, Teckentrup and Beck |