BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T212001Z
UID:Seminar-ACTO-981@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20210210T140000
DTEND:20210210T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Ninad Rajgopal: Hardness Magnification and the Locality Barrier\n\nHardness magnification reduces major complexity separations (such as EXP is not in NC1  or NP is not in P/Poly) to proving lower bounds for some natural problem Q (like the Minimum Circuit Size Problem - MCSP) against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19, CJW20] have established results of this form. In the most intriguing cases, the required lower bound is known for problems that appear to be significantly easier than Q, while Q itself is susceptible to lower bounds but these are not yet sufficient for magnification.\n\n\n\nIn this work, we investigate the prospects of proving new lower bounds using this approach. In particular, we consider the following essential questions associated with the hardness magnification program: Can we adapt known lower bound techniques to establish the desired lower bound for Q?\n\n\n\nHardness magnification might sidestep the Razborov-Rudich natural proofs barrier [RR97], but we identify a source of difficulty when trying to adapt existing lower bound techniques to prove strong lower bounds via magnification. This is captured by a locality barrier: existing magnification theorems unconditionally show that the problems Q considered above admit highly efficient circuits extended with small fan-in oracle gates, while lower bound techniques against weak circuit models quite often easily extend to circuits containing such oracles. This explains why direct adaptations of certain lower bounds are unlikely to yield strong complexity separations via hardness magnification.\n\n\n\nThis talk will be based on joint work with Lijie Chen, Shuichi Hirahara, Igor C.Oliveira, Jan Pich and Rahul Santhanam,\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=981
LOCATION:Online MT CSACTOO365Team
END:VEVENT
END:VCALENDAR