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:20181009T171344Z
DTSTART;TZID=America/Los_Angeles:20181119T160000
DTEND;TZID=America/Los_Angeles:20181119T170000
TRANSP:OPAQUE
SUMMARY:The Limits of Proof
UID:120718-ucb-events-calendar@berkeley.edu
ORGANIZER;CN="UC Berkeley Calendar Network":
LOCATION:Banatao Auditorium Sutardja Dai Hall
DESCRIPTION:Paul Beame\, University of Washington\n\nIn the early part of the 20th century\, Gödel\, Turing\, and Tarski showed that no consistent system of reasoning can contain proofs of important properties of the natural numbers or of computations. In these cases\, the difficulty stems from the need to reason about infinities of numbers or time that don't show up in our everyday world. In contrast\, proofs of properties in a bounded size world always exist.\n\nThe field of proof complexity studies the power of the many ways to express such proofs. These ways involve logic\, algebra\, combinatorial optimization\, graph theory\, and computations.\n\nFor many natural properties and methods of reasoning from these diverse fields\, one can show that\, though proofs exist\, their sizes must be astronomical – even proofs about small worlds would require more symbols to write down than there are particles in the universe.\n\nI will survey highlights and research directions in proof complexity and how these have implications for the P versus NP question and beyond.\n\nLight refreshments will be served before the lecture at 3:30 p.m.
URL:http://events.berkeley.edu/index.php/calendar/sn/pubaff.html?event_ID=120718&view=preview
SEQUENCE:0
CLASS:PUBLIC
CREATED:20181009T171344Z
LAST-MODIFIED:20181009T171902Z
X-MICROSOFT-CDO-BUSYSTATUS:BUSY
X-MICROSOFT-CDO-INSTTYPE:0
X-MICROSOFT-CDO-IMPORTANCE:1
X-MICROSOFT-CDO-OWNERAPPTID:-1
END:VEVENT
END:VCALENDAR