Скачать или смотреть Lower bounds for subgraph isomorphism – Benjamin Rossman – ICM2018

Mathematical Aspects of Computer Science
Invited Lecture 14.3
Lower bounds for subgraph isomorphism
Benjamin Rossman

Abstract: We consider the problem of determining whether an Erdős–Rényi random graph contains a subgraph isomorphic to a fixed pattern, such as a clique or cycle of constant size. The computational complexity of this problem is tied to fundamental open questions including P vs. NP and NC¹ vs. L. We give an overview of unconditional average-case lower bounds for this problem (and its colored variant) in a few important restricted classes of Boolean circuits.

ICM 2018 – International Congress of Mathematicians ©
www.icm2018.org  
 
Os direitos sobre todo o material deste canal pertencem ao Instituto de Matemática Pura e Aplicada, sendo vedada a utilização total ou parcial do conteúdo sem autorização prévia e por escrito do referido titular, salvo nas hipóteses previstas na legislação vigente.

The rights over all the material in this channel belong to the Instituto de Matemática Pura e Aplicada, and it is forbidden to use all or part of it without prior written authorization from the above mentioned holder, except in the cases prescribed in the current legislation.