Mathematics, Physics & Computer Science Seminar Series

November 23, 2022 from 4:30 PM at Governor's Palace, Moravské náměstí 1a, Baroque Hall

Menachem Magidor

Taming the Monster of Independence

Abstract:

Mathematicians feel that every genuine mathematical problem has a solution. Gödel's incompleteness theorem is a major challenge to this feeling, because it claims that every rich enough mathematical theory contains a statement that can not be proved or disproved by this theory. Namely: the problem is independent of present theory. The result of the last half a century showed that many problems in many subfields of Mathematics are independent of the usual axiom system mostly used by mathematicians: ZFC. The most famous one is the Continuum Hypothesis, CH. Discovering that a problem you spent a lot of time and effort with, is independent, is very frustrating for the working mathematician. This is the source of the expression ” the monster of independence” . Can the ” ugly monster of independence” be tamed? Can we still find ways of settling problems that seem to be independent? In the talk we shall explore several approaches to this challenge.


Menachem Magidor is an Israeli mathematician who specializes in mathematical logic, in particular, set theory at the Hebrew University's Einstein Institute of Mathematics. He served as President of the Hebrew University of Jerusalem, was President of the Association for Symbolic Logic from 1996 to 1998, and is currently the President of the Division for Logic, Methodology and Philosophy of Science and Technology of the International Union for History and Philosophy of Science (DLMPST/IUHPS; 2016-2019). In 2016 he was elected an honorary foreign member of the American Academy of Arts and Sciences. In 2018 he received the Solomon Bublick Award.

Mathematics, Physics & Computer Science Seminar Series

December 7, 2022 from 4:30 PM at Governor's Palace, Moravské náměstí 1a, Baroque Hall

Hans Munthe-Kaas

Computational Mathematics between Dynamics, Geometry and Algebra

Abstract:

Simulation of dynamical systems evolving in time is a central subject of numerical analysis. Traditionally, the main goals in designing a numerical integrator were high accuracy, numerical stability and computational efficiency.

In the last decades it has, however, become increasingly clear that not all errors are equally bad. For example in the simulation of a conservative mechanical system it may be crucial to preserve the Hamiltonian structure of the equations, or to preserve conserved quantities such as energy, angular momenta and other first integrals. In robotics and control, there may be geometric constraints which are important to obey exactly.

The lesson learnt is that the most important goal should be to ‘make errors in the right way’, rather than just minimising the error over a single time step. For long time simulations, the quality of the error is more important than its magnitude in each step. This gave birth to the research field Geometric Numerical Integration, or structure preserving discretisation of differential equations.

The analysis of geometric integration algorithms has evolved into a rich area of research in the borderland between computational dynamics, differential geometry and combinatorial algebra, where the interplay between these three fields is enriching all of them.

In this talk we will survey recent results in these areas, and illustrate by computational examples. The talk is aimed at scientists with a general background in computational engineering problems.

HANS ZANNA MUNTHE - KAAS is professor of mathematics at the University of Bergen and leader of the new Lie-Størmer Center in Tromsø. In the last four years he has been the leader of the Abelprize committee. He is editor-in-chief of the journal “Foundations of Computational Mathematics” and President of the Norwegian Mathematical Society.

The second regular Department Assembly of this year will take place on Wednesday, 2 November, at 4 pm, in M1.

The programme will involve my report on the department budgeting and evaluation, discussion, and the item "other".

Mathematics, Physics & Computer Science Seminar Series

October 26, 2022 from 4:30 PM at Governor's Palace, Moravské náměstí 1a, Baroque Hall

Irit Dinur

Expanders in higher dimensions

Abstract:

Expander graphs have been studied in many areas of mathematics and in computer science with versatile applications, including coding theory, networking, computational complexity and geometry.

High-dimensional expanders are a generalization that has been studied in recent years and their promise is beginning to bear fruit. In the talk, I will survey some powerful local to global properties of high-dimensional expanders, and describe several interesting applications, ranging from convergence of random walks to construction of locally testable codes that prove the c3 conjecture (namely, codes with constant rate, constant distance, and constant locality).

==================================
The PCP theorem

The PCP theorem says that any mathematical proof can be written in a special "PCP" format such that it can be verified, with arbitrarily high probability, by sampling only a few symbols in the proof. Hence the name, Probabilistically Checkable Proofs (PCPs). Alternatively and equivalently, any system of multivariate polynomial equations can be efficiently converted into another, so that if no input satisfies all equations in the former, no input satisfies even a tiny fraction of the equations in the later. Moreover, each of the new equations will involve only 3 variables.

This theorem is the key to understanding the difficulty of approximation and optimization problems; and also amazingly finds uses in modern cloud computing protocols. We will explain the context and meaning of the theorem, and outline a proof that relies on expander graphs, which are a central combinatorial object in numerous computer science and mathematical areas.

Irit Dinur is interested in theoretical computer science, and especially in error-correcting codes and probabilistically checkable proofs, both of which capture a certain “robustness” in computation. Currently, she is interested in connecting these to so-called high-dimensional expansion​—an analogue of expander graphs that draws on group theory, topology, and combinatorics.