Tue, April 9, 2019
Public Access

Category: All

April 2019
Mon Tue Wed Thu Fri Sat Sun
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          
11:00am [11:30am] Rahul Santhanam, University of Oxford
Combinatorics and Theoretical Computer Science seminar. Speaker: Rahul Santhanam. Affiliation: University of Oxford. Date and Time: Tuesday 09 April, 11:30 am - 12:30pm. Venue: Ramanujan Hall, Department of Mathematics. Title: Independence Results in Propositional Proof Complexity. Abstract: Given the lack of progress on complexity lower bounds, it is natural to ask whether they are hard to prove, in some formal sense. I will begin by briefly describing the classical incompleteness results of Godel and Chaitin, and posing the question for whether there are analogues of these results in complexity theory. I will then introduce the finitistic framework of propositional proof complexity, where we are interested in the existence of polynomial size proofs verifiable in polynomial time. I will explain what it means to prove circuit complexity or proof complexity lower bounds in this framework. Finally, I will describe a strong complexity conjecture for which it can be shown unconditionally that there are no feasible propositional proofs, in a certain technical sense.

2:00pm [2:30pm] Shuddhodan, Freie Universitat, Berlin
Geometry and Topology Seminar. Speaker: Shuddhodan. Affiliation: Freie Universitat, Berlin. Date and Time: Tuesday 09 April, 2:30 pm - 3:30 pm. Venue: Ramanujan Hall, Department of Mathematics. Title: Self maps of varieties over finite fields. Abstract: Esnault and Srinivas proved that as in de Rham cohomology over the complex numbers, the value of the entropy of an automorphism of a smooth proper surface over a finite field $\F_q$ is taken in the span of the Neron-Severi group inside of of $\ell$-adic cohomology. In this talk we will discuss some analogous questions in higher dimensions motivated by their results and techniques.