UNION OF BULGARIAN MATHEMATICIANS
INSTITUTE OF MATHEMATICS AND INFORMATICS, BULGARIAN ACADEMY OF SCIENCES
NATIONAL MATHEMATICS COLLOQUIUM
The next meeting of the National Mathematics Colloquium will be held on July 14, 2021 (Wednesday) at 4:15 p.m. in the Conference Room of IMI-BAS and online in Zoom.
A talk on:
How hard is it to prove computational hardness?
From Computational Complexity Theory to Algebraic Combinatorics and back
will be delivered by
Prof. Greta Panova, University of Southern California, USA.
Abstract: How hard is it to solve a given problem? How hard is it to prove that a problem is hard to solve? The answer to such questions can be given by Computational Complexity Theory whose flagship problem, the P vs NP problem, tries to separate the two major computational complexity classes. The algebraic version is the VP vs VNP problem, and is tackled by Geometric Complexity Theory (GCT). Using the tools from Algebraic Combinatorics, we showed that distinguishing VP from VNP via GCT is itself a harder problem than expected by disproving one of the milestone conjectures of GCT.
In this talk I will introduce the main concepts and ideas behind these theories and explain the connections with algebra and combinatorics. We will also discuss the opposite direction, application of computational complexity theory in combinatorial problems.
Zoom Meeting https://us02web.zoom.us/j/85767399108?pwd=TGR3YkR6d1NCYWtoSVM4QjIvcVN4UT09
Meeting ID: 857 6739 9108
Passcode: 044702
Everybody is invited.
Head of the Colloquium: Acad. P. Popivanov