Other seminars

A recently fertile strand of research in Group Theory is developing non-abelian analogues of classical combinatorial results for arithmetic Cayley graphs, describing properties such as growth, expansion, mixing, diameter, etc. We consider these problems for alternating groups, special linear groups over finite fields, and also in the continuous setting of compact Lie groups. The case of normal Cayley graphs (those generated by unions of conjugacy classes) has seen significant progress via character theory (whereby Larsen and Shalev resolved several open problems), but the general case still remains poorly understood. In this paper we generalise the background assumption from being normal to being global (a pseudorandomness condition), replacing character bounds by spectral estimates for convolution operators of global functions, thus obtaining qualitative generalisations of several results on normal Cayley graphs. Furthermore, our theory in the pseudorandom setting can be applied (via density increment arguments) to several results for general sets that are not too sparse, including analogues of Polynomial Freiman-Ruzsa, Bogolyubov's lemma, Roth's theorem, the Waring problem and essentially sharp estimates for the diameter problem of Cayley graphs whose density is at least exponential in -n. Our main tools is a sharp new hypercontractive inequality for global functions on the symmetric group, a hypercontractive result for apecial linear groups, and a sharp hypercontractivity result for compact Lie groups.

 

Based on joint works with Keevash, with Ellis, Kindler, and Minzer, and with Evra and Kindler.

In classical algebra, a commutative ring R, or more generally, a scheme, has two related invariants: the group of units and the Picard group. The first consists of invertible elements in R, while the second consists of invertible modules of R. In higher algebra, one is interested in generalizations of abelian groups and commutative rings, which allow the underlying collection of elements to be a homotopy type rather than a set. Moreover, all the identities required in classical algebra should be replaced by (a hierarchy of) homotopies between the two sides of the identity; for instance, the associativity relation (xy)z = x(yz) is replaced by a chosen homotopy between these two expressions, depending continuously on x,y, and z.

 

Such a homotopical version of the category of abelian groups is the category of spectra, and the corresponding notion of commutative rings is that of commutative ring spectra. Accordingly, one can assign spectra of units and Picard spectra to commutative ring spectra, generalizing the classical units and Picard groups. However, some of the constructions carried out in classical algebra, such as the construction of the line bundle associated with an element of the Picard group of a scheme, require ``strict" variants of these spectra, in which multiplication can be made genuinely commutative (not only up to homotopy). These variants are called the ``strict units'' and ``strict Picard'' spectra. However, despite their theoretical advantages, there are only a few cases in which the strict units and Picard spectra have been determined beyond classical commutative rings.

 

The sphere spectrum is one of the most important examples of a commutative ring spectrum. As the initial commutative ring spectrum, it plays a similar role to the ring of integers in classical algebra. Moreover, its homotopy groups are the stable homotopy groups of spheres, whose computation is the primary motivation for the development of stable homotopy theory.

 

In my talk, I will discuss the notions of spectra, commutative ring spectra, and their strict units and Picard spectra. Then, I will present a recent computation of the strict units and Picard spectra of the sphere spectrum and other related commutative ring spectra.

 

Consider the planar 3 Body Problem with masses $m_0,m_1,m_2>0$. In this paper we address two fundamental questions: the existence of oscillatory motions and chaotic hyperbolic sets. In 1922, Chazy classified the possible final motions of the three bodies, that is, the behaviors the bodies may have when time tends to infinity. One of the possible behaviors are oscillatory motions: solutions of the 3 Body Problem such that the positions of the bodies $q_0, q_1, q_2$ satisfy \[ \liminf_{t\to\pm\infty}\sup_{i,j=0,1,2, i\neq j}\|q_i-q_j\|<+\infty \quad \text{ and }\quad \limsup_{t\to\pm\infty}\sup_{i,j=0,1,2, i\neq j}\|q_i-q_j\|=+\infty. \] Assume that all three masses $m_0,m_1,m_2>0$ are not equal. Then, we prove that such motions exist. We also prove that one can construct solutions of the 3 Body Problem whose forward and backward final motions are of different type. This result relies on constructing invariant sets whose dynamics is conjugated to the (infinite symbols) Bernouilli shift. These sets are hyperbolic for the symplectically reduced planar 3 Body Problem. As a consequence, we obtain the existence of chaotic motions, an infinite number of periodic orbits and positive topological entropy for the 3 Body Problem. This a joint work with M. Guardia, J. Paradela and T. M. Seara

Let X be an irreducible algebraic variety over a non-archimedean field k. Vladimir Berkovich has attached to it an analytic space X^{an} with very good topological properties (it is locally compact and locally arcwise connected), and which contains plenty of "natural" piecewise-linear spaces called skeleta. More precisely, if S is a skeleton, its piecewise-linear structure is natural in the sense that it is "induced by rational functions on X": - if f is a non-zero rational function on X, log |f| is well-defined on S (since the latter consists of Zariski-dense points), and is PL (piecewise linear); - there exist finitely many non-zero rational functions f_1,..f_m on X such that the log lf_i| induce a PL-isomorphism between S and a finite union of convex polytopes in R^m. In this talk, I will present a joint work with Ehud Hrushovski, Francois Loeser and Jinhe He, in which we prove by model-theoretic methods, under the assumption that the ground field k is algebraically closed, a finiteness result for the set of PL functions on a given skeleton S of the form log |f| with f rational and non-zero. More precisely, we show that there exist non-zero rational functions g_1,..., g_r on X such that the functions on S of the form log |f| are exactly those that can be obtained using only the +,-,min and max operations from the log |g_i| and the constant functions with values in log |k^*|.

Classical KAM theory guarantees that most Diophantine unperturbed Lagrangian tori for a non-degenerate integrable Hamiltonian system persist under small perturbation. In this talk I will discuss (in the particular case of natural Hamiltonian systems), how secondary tori (non existing in the integrable limit) arise near simple resonances due to the effect of a generic analytic perturbation and discuss their persistence.

In higher algebra, one studies the homotopical analogue of abelian groups, known as spectra. These objects arise naturally (and facilitate great advances) in various mathematical fields from number theory to differential topology. It is a fundamental fact that in the spectral world there are more "primes", which provide an interpolation between zero and positive characteristics. A key property of the local theory at these intermediate primes is higher semiadditivity, which roughly speaking, provides canonical integrals over homotopically finite topological spaces. In this talk, I will discuss a "higher" analogue of representation and character theory, where characteristic zero vector spaces are replaced by spectra localized at any particular intermediate prime, and finite groups are generalized to a homotopically finite version thereof. In particular, I will present a work in progress on the generalization of the "induced character formula" in terms of the higher semiadditive structure and discuss its relationship with topological Hochschild homology.

By Faltings's Theorem, formerly known as the Mordell Conjecture, a smooth projective curve of genus at least 2 that is defined over a number field K has at most finitely many K-rational points. Votja later gave a second proof. Many authors, including Bombieri, de Diego, Parshin, Remond, Vojta, proved upper bounds for the number of K-rational points. I will discuss joint work with Vesselin Dimitrov and Ziyang Gao where we prove that the number of points on the curve is bounded from above as a function of K, the genus, and the rank of the Mordell-Weil group of the curve's Jacobian. We follow Vojta's approach to the Mordell Conjecture and answer a question of Mazur. I will explain the new feature: an inequality for the Neron-Tate height in a family of abelian varieties. It allows us to bound from above the number of points when the modular height of the curve is sufficiently large. This suffices for Mazur's Question.

This talk will address the following question: In what cases does learning a good hypothesis require more resources than verifying a hypothesis proposed by someone else?** If verification is significantly cheaper than learning, that could have important practical implications for delegation of machine learning tasks in commercial settings, and might also have consequences for verification of scientific publications, and for AI safety. Two results will be discussed: (1) There exists a learning problem where verification requires quadratically less random samples than are required for learning. (2) The broad class of Fourier-sparse functions (which includes decision trees, for example) can be efficiently verified using random samples only, even though it is widely believed to be impossible to efficiently learn this class from random samples alone. 
This is joint work with Shafi Goldwasser (UC Berkeley), Guy Rothblum (WIS), and Amir Yehudayoff (Technion).  

** "Learning" -- as defined in Valiant's Probably Approximately Correct (PAC) framework

We develop differentially private mechanisms that achieve nearly instance-optimal losses, achieving lower loss than all appropriately unbiased mechanisms for any possible instance. We show that our mechanisms, with a modest increase in sample size (logarithmic or constant), are instance-optimal for a large family of functions. In contrast to existing mechanisms, which use the global or local sensitivity of the function being estimated, and so are necessarily instance suboptimal, the key to our construction is to use the inverse of the sensitivity. This allows a simple instance-optimal algorithm, and we develop several representative private mechanisms, including for the median and regression problems.

To describe different levels of stochastic behavior Ergodic Theory introduces a hierarchy of ergodic properties. Among them ergodicity, mixing and the Bernoulli property are most used to study models in science with complicated "turbulent-like" behavior. However, "typical" systems in science are modeled by smooth (differentiable) dynamical systems acting on smooth phase spaces and the classical "smooth realization problem" asks whether any smooth phase space allows a dynamical system with prescribe collection of ergodic (stochastic) properties, in other words whether topology of the phase space may impose obstructions on a system to exhibit certain stochastic behavior. In this connection I also discuss two more important characteristics of stochastic behavior -- the rate of decay of correlations (rate of mixing) and the Central Limit Theorem -- and whether they too can be realized on any smooth phase space.   

This talk concerns the well-studied model of "cake-cutting" for studying questions regarding notions of fair division of resources. We focus on discrete versions rather than using infinite-precision real values, specifically, focusing on the communication complexity. Using general discrete simulations of classical infinite-precision protocols (Robertson-Webb and moving-knife), we roughly partition the various fair-allocation problems into 3 classes: "easy" (constant number of rounds of logarithmic many bits), "medium" (poly-log total communication), and "hard".

Our main technical result concerns two of the "medium" problems (perfect allocation for 2 players and equitable allocation for any number of players) which we prove are not in the "easy" class. Our main open problem is to separate the "hard" from the "medium" classes.

Joint work with Simina Branzei

The "Duty of Care"is a legal obligation requiring one to adhere to a standard of reasonable care while performing acts that could harm others. We propose a formal, mathematical interpretation of the duty of care in the context of "being cautious while driving". The framework enables tackling moral questions in a formal way and is an example of a new research field which we call regulatory science.

Joint work with Shaked Shammah and Amnon Shashua.

  In knot theory and more generally the theory of 3-manifolds various "quantum invariants" like the Witten-Reshetikhin-Turaev or the Kashaev invariant have been much studied in recent years,  in particular because of the famous "volume conjecture" related to the asymptotic growth of the Kashaev invariant.  Rather surprisingly, it transpired a few years ago that these invariants  also have very non-trivial number-theoretical properties, including a kind of weak invariance under the modular group SL(2,Z) ("quantum modular forms") and the experimental discovery of the appearance of certain units in cyclotomic extensions as factors in the asymptotic expansions.  The talk will report on this and specifically on recent joint work with Frank Calegari and Stavros Garoufalidis that constructs such units in a purely algebraic way starting from elements in algebraic K-theory or in the more elementary "Bloch group".  As an unexpected application, this result led to the proof of a well-known conjecture of Nahm on the modularity of certain q-hypergeometric series.

Recent success stories of using machine learning for diagnosing skin cancer, diabetic retinopathy, pneumonia, and breast cancer may give the impression that artificial intelligence (AI) is on the cusp of radically changing all aspects of health care. However, many of the most important problems, such as predicting disease progression, personalizing treatment to the individual, drug discovery, and finding optimal treatment policies, all require a fundamentally different way of thinking. Specifically, these problems require a focus on *causality* rather than simply prediction. Motivated by these challenges, my lab has been developing several new approaches for causal inference from observational data. In this talk, I describe our recent work on the deep Markov model (Krishnan, Shalit, Sontag AAAI '17) and TARNet (Shalit, Johansson, Sontag, ICML '17).

In formal verification, one uses mathematical tools in order to prove that a system satisfies a given specification.
In this talk I consider three limitations of traditional formal verification:
The first is the fact that treating systems as finite-state machines is problematic, as systems become more complex, and thus we must consider infinite-state machines.
The second is that Boolean specifications are not rich enough to specify properties required by today's systems. Thus, we need to go beyond the Boolean setting.
The third concerns certifying the results of verification: while a verifier may answer that a system satisfies its specification, a designer often needs some palpable evidence of correctness.

I will present several works addressing the above limitations, and the mathematical tools involved in overcoming them.

No prior knowledge is assumed. Posterior knowledge is guaranteed.

Today's technological world is increasingly dependent upon the reliability, robustness, quality of service and timeliness of networks including those of power distribution, financial, transportation, communication, biological, and social. For the time-critical functionality in transferring resources and information, a key requirement is the ability to adapt and reconfigure in response to structural and dynamic changes, while avoiding disruption of service and catastrophic failures. We will outline some of the major problems for the development of the necessary theory and tools that will permit the understanding of network dynamics in a multiscale manner.

Many interesting networks consist of a finite but very large number of nodes or agents that interact with each other. The main challenge when dealing with such networks is to understand and regulate the collective behavior. Our goal is to develop mathematical models and optimization tools for treating the Big Data nature of large scale networks while providing the means to understand and regulate the collective behavior and the dynamical interactions (short and long-range) across such networks.

The key mathematical technique will be based upon the use optimal mass transport theory and resulting notions of curvature applied to weighted graphs in order to characterize network robustness. Examples will be given from biology, finance, and transportation.

I will Describe KP hierarchy, its reductions KdV and r-GD, tau functions and wave functions. Witten's conjectured that the tau functions are the generating functions of intersection numbers over the moduli of curves/ r-spin curves (these conjectures are now Kontsevich's theorem and Faber-Shadrin-Zvonkine theorem resp.). Recently the following was conjectured: a. The KdV wave function is a generating function of intersection numbers on moduli of "Riemann surfaces with boundary" (Pandharipande-Solomon-T,Solomon-T,Buryak). b. The r-th GD wave function is the generating function of intersection numbers on moduli of "r-spin Riemann surfaces with boundary" (Buryak-Clader-T). I will describe the conjectures, and sketch the proof of conjecture (a) (Pandharipande-Solomon-T in genus 0, T,Buryak-T for the general case). If there will be time, I'll describe a conjectural generalization by Alexandrov-Buryak-T, and explain why the proof of (b) in high genus seems currently unreachable.

We study the non-vanishing gradient-like vector fields $v$ on smooth compact manifolds $X$ with boundary. We call such fields traversing. With the help of a boundary generic field $v$, we divide the boundary $\d X$ of $X$ into two complementary compact manifolds, $\d^+X(v)$ and $\d^-X(v)$. Then we introduce the causality map $C_v: \d^+X(v) \to \d^-X(v)$, a distant relative of the Poincare return map. Let $\mathcal F(v)$ denote the oriented 1-dimensional foliation on $X$, produced by a traversing $v$-flow.

Our main result, the Holography Theorem, claims that, for boundary generic traversing vector fields $v$, the knowledge of the causality map $C_v$ is allows for a reconstruction of the pair $(X, \mathcal F(v))$, up to a homeomorphism $\Phi: X \to X$ which is the identity on the boundary $\d X$. In other words, for a massive class of ODE's, we show that the topology of their solutions, satisfying a given boundary value problem, is rigid. We call these results ``holographic" since the $(n+1)$-dimensional $X$ and the un-parameterized dynamics of the flow on it are captured by a single correspondence $C_v$ between two $n$-dimensional screens, $\d^+X(v)$ and $\d^-X(v)$.

This holography of traversing flows has numerous applications to the dynamics of general flows. Time permitting, we will discuss some applications of the Holography Theorem to the geodesic flows and the inverse scattering problems on Riemannian manifolds with boundary.

The class P attempts to capture the efficiently solvable computational tasks. It is full of practically relevant problems, with varied and fascinating combinatorial structure. In this talk, I will give an overview of a rapidly growing body of work that seeks a better understanding of the structure within P. Inspired by NP-hardness, the main tool in this approach are combinatorial reductions. Combining these reductions with a small set of plausible conjectures, we obtain tight lower bounds on the time complexity of many of the most important problems in P.

Everyone wants to program with "high-level concepts", rather than meddle with the fine details of the implementation, such as pointers, network packets, and asynchronous callbacks. This is usually achieved by introducing layers of abstraction - but every layer incurs some overhead, and when they accumulate, this overhand becomes significant and sometimes prohibitive. Optimizing the program often requires to break abstractions, which leads to suboptimal design, higher maintenance costs, and subtle hard-to-trace bugs.
I will present two recent projects that attempt to address this difficulty. STNG is an automated lifting compiler that can synthesize high-level graphics code for computing stencils over matrices, from low-level legacy code written in Fortran. Its output is expressed in Halide, a domain-specific language for image processing that can take advantage of modern GPUs. The result is therefore code that is both easier to understand and more efficient than the original code.
Bellmania is a specialized tool for accelerating dynamic-programming algorithms by generating recursive divide-and-conquer implementations of them. Recursive divide-and-conquer is an algorithmic technique that was developed to obtain better memory locality properties. Bellmania includes a high-level language for specifying dynamic programming algorithms and a calculus that facilitates gradual transformation of these specifications into efficient implementations. These transformations formalize the divide-and-conquer technique; a visualization interface helps users to interactively guide the process, while an SMT-based back-end verifies each step and takes care of low-level reasoning required for parallelism.
The lesson is that synthesis techniques are becoming mature enough to play a role in the design and implementation of realistic software systems, by combining the elegance of abstractions with the performance gained by optimizing and tuning the fine details.

Cancer is a highly complex aberrant cellular state where mutations impact a multitude of signalling pathways operating in different cell types. In recent years it has become apparent that in order to understand and fight cancer, it must be viewed as a system, rather than as a set of cellular activities. This mind shift calls for new techniques that will allow us to investigate cancer as a holistic system. In this talk, I will discuss some of the  progress made towards achieving such a system-level understanding using computer modelling of biological  behaviours, also known as Executable Biology. I will concentrate on our recent attempts to better understand cancer through the following examples: 1) drug target optimization for Chronic Myeloid Leukaemia using an innovative platform called BioModelAnalyzer, which allows to prove stabilization of biological systems; 2) dynamic hybrid modelling of Glioblastoma (brain tumour) development; 3) state-based modelling of cancer signalling pathways and their analysis using model-checking; and 4) synthesis of blood stem cell programs from single-cell gene expression data. Looking forward, inspired by David Harel’s Grand Challenge proposed a decade ago, I will propose a smaller grand challenge for computing and biology that could shed new light on our ability to control cell fates during development and disease and potentially change the way we treat cancer in the future.