![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Jan Pich, Oxford
Friday 10 May 2019, 14:00-15:00
Hardness magnification near state-of-the-art lower bounds
- đ¤ Speaker: Jan Pich, Oxford
- đ Date & Time: Friday 10 May 2019, 14:00 - 15:00
- đ Venue: FW26
Abstract
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.
Series This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.
Included in Lists
- All Talks (aka the CURE list)
- bld31
- Cambridge talks
- Computing and Mathematics
- Department of Computer Science and Technology talks and seminars
- FW26
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- Martin's interesting talks
- School of Technology
- tcw57âs list
- Trust & Technology Initiative - interesting events
- yk373's list
- yk449
Note: Ex-directory lists are not shown.