BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of California\, Berkeley//UCB Events Calendar//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
DTSTART:19701029T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:19700402T020000
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20170421T194455Z
DTSTART;TZID=America/Los_Angeles:20170504T130000
DTEND;TZID=America/Los_Angeles:20170504T140000
TRANSP:OPAQUE
SUMMARY:Dissertation Talk: Polynomial Proof Systems\, Effective Derivations\, and their Applications in the Sum-of-Squares Hieararchy
UID:108859-ucb-events-calendar@berkeley.edu
ORGANIZER;CN="UC Berkeley Calendar Network":
LOCATION:606 Soda Hall
DESCRIPTION:Benjamin Weitz\, Berkeley EECS\n\nThe Sum-of-Squares (SOS) SDP Hierarchy has recently emerged as a powerful tool for approximation algorithms\, tensor recovery problems\, and more. Because it is relatively new\, we still do not know the answer to even very basic questions about the hierarchy. For example\, we do not even know when the SOS SDP is guaranteed to run correctly in polynomial time! We would also like to know when the SOS SDP performs well\, specifically when achieves the same approximation as any other SDP of a comparable size. \n\nIn this talk we make progress on both of these questions\, giving a sufficient\, checkable criteria for when an SOS SDP will run in polynomial time\, as well as proving that no symmetric SDP performs better than SOS on the Matching and TSP problems. Our results make use of low-degree certificates of ideal membership for the polynomial ideal formed by the constraints. Thus a key step in our proofs is constructing certificates for arbitrary polynomials in the corresponding constraint ideals.
URL:http://events.berkeley.edu/index.php/calendar/sn/pubaff.html?event_ID=108859&view=preview
SEQUENCE:0
CLASS:PUBLIC
CREATED:20170421T194455Z
LAST-MODIFIED:20170421T203133Z
X-MICROSOFT-CDO-BUSYSTATUS:BUSY
X-MICROSOFT-CDO-INSTTYPE:0
X-MICROSOFT-CDO-IMPORTANCE:1
X-MICROSOFT-CDO-OWNERAPPTID:-1
END:VEVENT
END:VCALENDAR