• Jan Pich
    • (Oxford University)
    • Hardness magnification near state-of-the-art lower bounds
    • Abstract:
    • We continue the development of hardness magnification, a strategy for deriving strong circuit lower bounds by reducing them to a refined analysis of weaker models proposed by Oliveira and Santhanam (2018). Specifically, we 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.
    • 14.12.18   13:30
    • Navid Talebanfard
    • (IM)
    • An exposition of R. Williams' "Strong ETH Breaks with Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation".
    • Abstract:
    • Variants are the Strong Exponential Time Hypothesis have been proposed. In this talk I sketch Williams' result which asserts that Strong ETH fails when we have both non-determinism and randomization. The proof uses arithmetization and polynomial arguments.
    • 07.12.18   13:30

    Michal Koucky, Pavel Pudlak