Calendar
- 04March 4, 2020
Non-random behaviour in sums of modular symbols
1 Oxford Street, Cambridge, MA 02138 USAWe give explicit expressions for the Fourier coefficients of Eisenstein series twisted by Dirichlet characters and modular symbols on $\Gamma_0(N)$ in the case where $N$ is prime and equal to the conductor
of the Dirichlet character. We obtain these expressions by computing the spectral decomposition of automorphic functions closely related to these Eisenstein series. As an application, we then evaluate certain sums of modular symbols in a way which parallels past work of Goldfeld, O’Sullivan, Petridis, and Risager. In one case we find less cancellation in this sum than would be predicted by the common phenomenon of “square root cancellation”, while in another case we find more cancellation.**CANCELED** Informal Geometry & Dynamics Seminar: Pseudo-Anosov mapping classes with large dilatation
I’ll talk about some subclasses of pseudo-Anosov mapping classes whose dilatations are bounded away from 1.Well-ordering principles in Proof theory and Reverse Mathematics
There are several familiar theories of reverse mathematics that can be characterized by well-ordering principles of the form(*) “if X is well ordered then f(X) is well ordered”,where f is a standard proof theoretic function from ordinals to ordinals (such f’s are always dilators). Some of these equivalences have been obtained by recursion-theoretic and combinatorial methods. They (and many more) can also be shown by proof-theoretic methods, employing search trees and cut elimination theorems in infinitary logic with ordinal bounds. One could perhaps generalize and say that every cut elimination theorem in ordinal-theoretic proof theory encapsulates a theorem of this type.One aim of the talk is to present a general methodology underlying these results that enables one to construct omega-models of particular theories from (*).As (*) is of complexity $\Pi^1_2$ such a principle cannot characterize stronger comprehensions at the level of $\Pi^1_1$-comprehension. This requires a higher order version of (*) that employs ideas from ordinal representation systems with collapsing functions used in impredicative proof theory. The simplest one is the Bachmann construction. Relativizing the latter construction to any dilator f and asserting that this always yields a well-ordering turns out to be equivalent to $\Pi^1_1$-comprehension. This result has been conjectured more than 10 years ago, but its proof has only been worked out by Anton Freund in recent yearsCMSA Colloquium: Derandomizing Algorithms via Spectral Graph Theory
20 Garden Street, Cambridge, MA 02138Randomization is a powerful tool for algorithms; it is often easier to design efficient algorithms if we allow the algorithms to “toss coins” and output a correct answer with high probability. However, a longstanding conjecture in theoretical computer science is that every randomized algorithm can be efficiently “derandomized” — converted into a deterministic algorithm (which always outputs the correct answer) with only a polynomial increase in running time and only a constant-factor increase in space (i.e. memory usage).In this talk, I will describe an approach to proving the space (as opposed to time) version of this conjecture via spectral graph theory. Specifically, I will explain how randomized space-bounded algorithms are described by random walks on directed graphs, and techniques in algorithmic spectral graph theory (e.g. solving Laplacian systems) have yielded deterministic space-efficient algorithms for approximating the behavior of such random walks on undirected graphs and Eulerian directed graphs (where every vertex has the same in-degree as out-degree). If these algorithms can be extended to general directed graphs, then the aforementioned conjecture about derandomizing space-efficient algorithms will be resolved.
Joint works with Jack Murtagh, Omer Reingold, Aaron Sidford, AmirMadhi Ahmadinejad, Jon Kelner, and John Peebles.