University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Hardness magnification near state-of-the-art lower bounds

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

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

  • UserJan Pich, Oxford
  • ClockFriday 10 May 2019, 14:00-15:00
  • HouseFW26.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity