BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
BEGIN:VEVENT
CATEGORIES:Colloquia / Seminar / Lecture
DESCRIPTION:Attempts to prove the intractability of the Minimum Circuit Siz
e Problem (MCSP) date as far back as the 1950s and are well-motivated by co
nnections to cryptography\, learning theory\, and average-case complexity.
In this talk\, we will survey some of these connections and discuss recent
progress towards showing MCSP is intractable under worst-case assumptions.
\n\nIn particular\, while Masek showed in the late 1970s that the version o
f MCSP for DNF formulas is NP-hard\, extending this result to the case of d
epth-3 AND/OR formulas was open. We show that the constant depth formula ve
rsion of MCSP is NP-hard (under quasipolynomial-time reductions) for all co
nstant depths. Our approach is based on a novel method to "lift" depth-d fo
rmula lower bounds to depth-(d+1). Intriguingly\, this method also implies
the existence of a function with a 2^{\Omega_d(n^{1/5})} additive gap betwe
en its depth-d and depth-(d+1) formula complexity.\n\nWe also discuss progr
ess in the case of general\, unrestricted circuits. We show that the versio
n of MCSP where the input is a partial function (represented by a string in
{0\,1\,?}*) is not in P under the Exponential Time Hypothesis (ETH).
DTEND:20200929T064500Z
DTSTAMP:20240908T090420Z
DTSTART:20200928T173000Z
LOCATION:Zoom
SEQUENCE:0
SUMMARY:Constant Depth Formula and Partial Function Versions of MCSP are Ha
rd
UID:tag:localist.com\,2008:EventInstance_34501059085671
URL:https://events.seas.harvard.edu/event/rahul_ilango_mit
END:VEVENT
END:VCALENDAR