BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Marcelo Arena (Pontificia Universidad Católica de Chile) DTSTART:20210909T180000Z DTEND:20210909T190000Z DTSTAMP:20260423T035939Z UID:OLS/57 DESCRIPTION:Title: Des criptive Complexity for Counting Complexity Classes\nby Marcelo Arena (Pontificia Universidad Católica de Chile) as part of Online logic semina r\n\n\nAbstract\nDescriptive Complexity has been very successful in charac terizing complexity classes of decision problems in terms of the propertie s definable in some logics. However\, descriptive complexity for counting complexity classes\, such as FP and #P\, has not been systematically studi ed\, and it is not as developed as its decision counterpart. In this talk\ , we will present a framework based on Weighted Logics to address this iss ue. Specifically\, by focusing on the natural numbers we obtain a logic ca lled Quantitative Second Order Logics (QSO)\, and show how some of its fra gments can be used to capture fundamental counting complexity classes such as FP\, #P and FPSPACE\, among others. Moreover\, we use QSO to define a hierarchy inside #P\, identifying counting complexity classes with good cl osure and approximation properties\, and which admit natural complete prob lems.\n LOCATION:https://researchseminars.org/talk/OLS/57/ END:VEVENT END:VCALENDAR