BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Rahul Ilango (MIT) DTSTART:20200527T170000Z DTEND:20200527T180000Z DTSTAMP:20260423T021018Z UID:TCSPlus/5 DESCRIPTION:Title: Is it (NP) hard to distinguish order from chaos?\nby Rahul Ilango (MIT ) as part of TCS+\n\n\nAbstract\n"The Minimum Circuit Size Problem (MCSP) roughly asks what the ""complexity"" of a given string is. Informally\, on e can think of this as determining the degree of ""computational order"" a string has.\n\nIn the past several years\, there has been a resurgence of interest in MCSP. A series of exciting results have begun unraveling what looks to be a fascinating story. This story already reveals deep connecti ons between MCSP and a growing list of fields\, including cryptography\, l earning theory\, structural complexity theory\, average-case complexity\, and circuit complexity. As an example\, Santhanam recently proved a condit ional equivalence between the complexity of MCSP and the existence of one- way functions.\n\nThis talk is split into two parts. The first part is a b road introduction to MCSP\, answering the following questions: What is thi s problem? Why is it interesting? What do we know so far\, and where might the story go next? The second part discusses recent joint work with Bruno Loff and Igor Oliveira showing that the ""multi-output version"" of MCSP is NP-hard. "\n\nThe Minimum Circuit Size Problem (MCSP) roughly asks what the "complexity" of a given string is. Informally\, one can think of this as determining the degree of "computational order" a string has.\n\nIn th e past several years\, there has been a resurgence of interest in MCSP. A series of exciting results have begun unraveling what looks to be a fascin ating story. This story already reveals deep connections between MCSP and a growing list of fields\, including cryptography\, learning theory\, stru ctural complexity theory\, average-case complexity\, and circuit complexit y. As an example\, Santhanam recently proved a conditional equivalence bet ween the complexity of MCSP and the existence of one-way functions.\n\nThi s talk is split into two parts. The first part is a broad introduction to MCSP\, answering the following questions: What is this problem? Why is it interesting? What do we know so far\, and where might the story go next? T he second part discusses recent joint work with Bruno Loff and Igor Olivei ra showing that the "multi-output version" of MCSP is NP-hard.\n LOCATION:https://researchseminars.org/talk/TCSPlus/5/ END:VEVENT END:VCALENDAR