BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20251026T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20250330T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.29378.field_data.0@www.glad.uniroma1.it
DTSTAMP:20260403T200333Z
CREATED:20250620T080913Z
DESCRIPTION:AbstractFor decades\, fundamental questions in complexity theor
 y have remained wide open. A classic counting argument by Shannon shows th
 at most Boolean functions on n bits require circuits of size 2^n/n\, yet w
 e lack even superlinear circuit size lower bounds for any explicit functio
 n in NP. This raises two natural questions: (i) can we make these counting
  arguments constructive\, and (ii) why have we struggled so much to find a
 n explicit hard function?In this talk\, we rigorously examine two algorith
 mic and metamathematical notions of constructivity in complexity theory\, 
 and how they are related to circuit lower bounds and barrier results. We w
 ill demonstrate that(i) New constructive proofs of known nonconstructive l
 ower bounds imply strong\, breakthrough lower bounds.(ii) Some nonconstruc
 tive proofs of lower bounds cannot be made constructive.We show how these 
 ideas can be used to make unconditional progress on an old question in pro
 of complexity and bounded arithmetic.
DTSTART;TZID=Europe/Paris:20250701T110000
DTEND;TZID=Europe/Paris:20250701T110000
LAST-MODIFIED:20250621T094146Z
LOCATION:DIAG - Room  B203
SUMMARY:Talk: 'Constructive Criticisms of Complexity: Unifying Proofs and A
 lgorithms' - Stefan Grosser - Stefan Grosser (Mc Gill University)
URL;TYPE=URI:http://www.glad.uniroma1.it/node/29378
END:VEVENT
END:VCALENDAR