Tue, April 9, 2019
Public Access Category: All |
||||||||||||||||||||
|
- Time:
- 11:30am-12:30pm
- Location:
- Ramanujan Hall, Department of Mathematics
- Description:
- 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.
- Time:
- 2:30pm-3:30pm
- Location:
- Ramanujan Hall, Department of Mathematics
- Description:
- 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.