Hardness magnification near state-of-the-art lower bounds

Add to your list(s) Download to your calendar using vCal

• Jan Pich, Oxford
• Friday 10 May 2019, 14:00-15:00
• FW26.

If you have a question about this talk, please contact Victor Gomes.

Hardness magnification is a strategy for deriving strong circuit lower bounds by reducing them to a refined analysis of weaker models proposed by Oliveira and Santhanam (2018). I will present several improvements of their initial results. For example, we will consider a gap version of the meta-computational problem MCSP , which asks to distinguish truth-tables of Boolean functions of small circuit complexity from truth-tables of a slightly larger complexity, and establish that a small improvement over the state-of-the-art lower bounds in a variety of computational models for the gap version of MCSP would imply explicit super-polynomial lower bounds. This talk is based on a joint work with Igor C. Oliveira and Rahul Santhanam and on an ongoing work with Igor C. Oliveira, Ninad Rajgopal and Rahul Santhanam.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• FW26
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.