You are here

Other seminars

ThursdayNov 23, 202312:00
Special Guest SeminarRoom 155
Speaker:Or ShalomTitle:Inverse theorems in ergodic theory and additive combinatoricsAbstract:opens in new windowin html    pdfopens in new window

The Gowers uniformity k-norm on a finite abelian group measures the averages of complex functions on such groups over k-dimensional arithmetic cubes. The inverse question about these norms asks if a large norm implies correlation with a function of an algebraic origin. The analogue of the Gowers uniformity norms for measure-preserving abelian actions are the Host-Kra-Gowers seminorms which are intimately connected to the Host-Kra-Ziegler factors of such systems. The corresponding inverse question in the dynamical setting asks for a description of such factors in terms of systems of an algebraic origin. In this talk, we survey recent results about the inverse question in the dynamical and combinatorial settings, and in particular how an answer in the former setting can imply one in the latter. This talk is based on joint works with Asgar Jamneshan and Terence Tao.

ThursdayNov 16, 202311:00
Special Guest SeminarRoom 1
Speaker:Noam LifshitzTitle:Hypercontractivity in simple groupsAbstract:opens in new windowin html    pdfopens in new window

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.

MondayAug 07, 202314:00
Special Guest LectureRoom 155
Speaker:Egor ShelukhinTitle:Remark on non-contractible closed geodesicsAbstract:opens in new windowin html    pdfopens in new window

Proving that there are infinitely many closed geodesics on Riemannian manifolds is a long-term theme in differential geometry. While the main case of interest has been that of simply-connected manifolds, the case of infinite fundamental groups or even that of infinitely many free homotopy classes of loops is also open in general, owing to unsolved problems in group theory. We present a simple criterion in terms of the action of the fundamental group on higher homotopy groups for there to be infinitely many closed geodesics for a C^4-generic Riemannian metric, or for an arbitrary Riemannian metric if in addition there are infinitely many homotopy classes of loops. This talk is based on joint work with Jun Zhang.

WednesdayFeb 22, 202316:00
Special Guest LectureRoom 155
Speaker:Shachar CarmeliTitle:Strict units and Picard spectraAbstract:opens in new windowin html    pdfopens in new window

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.


SundayFeb 19, 202316:00
Special Guest SeminarRoom 1
Speaker:Ivan PenkovTitle:Unspelled corollaries from standard theorems about the field of complex numbersAbstract:opens in new windowin html    pdfopens in new window

I will recall Steinitz's characterisation of the field of complex numbers and Artin-Schreier's theorem.
These classical facts have some "unexpected" consequences like a nice embedding of the field of non-standard numbers into the field of complex numbers. Also I will discuss the embeddings of the field of real numbers into the field of complex numbers.

The talk is aimed at a wide audience including undergraduate students.

MondayFeb 06, 202309:15
Geometry and Topology Seminar & Mathematical Analysis and Applications SeminarRoom 155
Speaker:Pau MartinTitle:Hyperbolic dynamics and oscillatory motions in the 3 Body ProblemAbstract:opens in new windowin html    pdfopens in new window

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

TuesdayDec 20, 202211:00
Special Guest SeminarRoom 1
Speaker:Dimitri KanevskyTitle:Non-associative Moufang loops of point classes on cubic surfacesAbstract:opens in new windowin html    pdfopens in new window
In this talk, I will construct an example of a non-associative Moufang loop of point classes on a cubic surface over a local field and describe a class of cubic surfaces over number fields for which I conjecture that Moufang loops associated with them are non-associative. The question about the existence of non-associative loops of point classes on cubic surfaces was stated in Yuri I. Manin's book "Cubic Forms" about fifty years ago. All required concepts will be recalled.
TuesdayNov 29, 202211:00
Special Guest SeminarLecture Hall
Speaker:Professor Antoine Ducros Title:Rational functions and piecewise-linear maps in non-archimedean geometryAbstract:opens in new windowin html    pdfopens in new windowLecture Hall room 1
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^*|.
TuesdayNov 22, 202211:00
Special Guest SeminarLecture Hall
Speaker:Itay Glazer Title:Word maps and word measures: probability and geometry Abstract:opens in new windowin html    pdfopens in new window

Every word w(x_1,...,x_r) in a free group, such as the commutator word w=xyx^(-1)y^(-1), induces a word map w:G^r-->G on every group G. For g in G, it is natural to ask whether the equation w(x_1,...,x_r)=g has a solution in G^r, and to estimate the "size" of this solution set, in a suitable sense. When G is finite, or more generally a compact group, this becomes a probabilistic problem of analyzing the distribution of w(x_1,...,x_r), for Haar-random elements  x_1,...,x_r  in G. When G is an algebraic group, such as SLn(C), one can study the geometry of the polynomial map w:SLn(C)^r-->SLn(C), using algebraic methods. 
Such problems have been studied in the last few decades, in various settings such as finite simple groups, compact p-adic groups, compact Lie groups, and simple algebraic groups. Analogous problems have been studied for Lie algebra word maps as well. In this talk, I will mention some of these results, and explain the tight connections between the probabilistic and algebraic approaches. 

Based on joint works with Yotam Hendel, Raf Cluckers and Nir Avni.

MondayNov 21, 202213:00
Special Guest SeminarRoom 1
Speaker:Prof. Luigi ChierchiaTitle:Birth and persistence of secondary tori in nearly-integrable Hamiltonian systemsAbstract:opens in new windowin html    pdfopens in new window
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.
WednesdayJun 15, 202210:00
Special Guest LectureRoom 1
Speaker:George LusztigTitle:On the exceptional group E_8Abstract:opens in new windowin html    pdfopens in new window
I will introduce the exceptional group E_8.The only prerequisites are the notion of vector space and that of a group.
TuesdayDec 21, 202116:00
Special Guest SeminarRoom 1
Speaker:Lior YanovskiTitle:Higher semiadditive representation and character theory.Abstract:opens in new windowin html    pdfopens in new window
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.
WednesdayDec 15, 202111:15
Special Guest SeminarRoom 1
Speaker:Amir SagivTitle:Floquet Hamiltonians and topological insulators Abstract:opens in new windowin html    pdfopens in new window
Floquet topological insulators (FTIs) are an emerging category of materials whose properties are transformed by time-periodic forcing, with a wide range of applications to electronics, laser science, and more. Traditionally, the theory of FTIs is based on discrete, approximated models. Can FTIs be understood from their first-principles continuum models, i.e., from a driven Schrodinger equation? First, we rigorously show that the propagation of physically relevant wave-packets are governed by a Dirac equation. This dynamical-systems approach allows us to study both the bulk and edge insulation of FTIs. In particular, we show that in the continuous Dirac model, localized edge-modes decay due to a resonance phenomenon.
MondayOct 25, 202116:00
Geometry and Topology Seminar & Mathematical Analysis and Applications Seminar
Speaker:Philipp HabeggerTitle:Uniformity for the Number of Rational Points on a CurveAbstract:opens in new windowin html    pdfopens in new windowZoom Meeting:
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.
WednesdayJan 29, 202013:00
Computer Science SeminarRoom 1
Speaker:Yuval DaganTitle:Interaction is necessary for distributed learning with privacy or communication constraintsAbstract:opens in new windowin html    pdfopens in new windowSPECIAL FOUNDATIONS OF COMPUTER SCIENCE SEMINAR

Local differential privacy (LDP) is a model where users send privatized data to an untrusted central server whose goal it to solve some data analysis task. In the non-interactive version of this model the protocol consists of a single round in which a server sends requests to all users then receives their responses. This version is deployed in industry due to its practical advantages and has attracted significant research interest. Our main result is an exponential lower bound on the number of samples necessary to solve the standard task of learning a large-margin linear separator in the non-interactive LDP model. Via a standard reduction this lower bound implies an exponential lower bound for stochastic convex optimization and specifically, for learning linear models with a convex, Lipschitz and smooth loss. These results answer the questions posed in \citep{SmithTU17,DanielyF18}. Our lower bound relies on a new technique for constructing pairs of distributions with nearly matching moments but whose supports can be nearly separated by a large margin hyperplane. These lower bounds also hold in the model where communication from each user is limited and follow from a lower bound on learning using non-adaptive \emph{statistical queries}.




SundayJan 19, 202013:30
Computer Science SeminarRoom 155
Speaker:Jonathan ShaferTitle:Learning vs. VerifyingAbstract:opens in new windowin html    pdfopens in new windowspecial foundations of computer science seminar

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

MondayJan 13, 202011:15
Computer Science SeminarRoom 155
Speaker:Lijie Chen Title:Strong Average-Case Circuit Lower Bounds from Non-trivial DerandomizationAbstract:opens in new windowin html    pdfopens in new windowSPECIAL THEORY SEMINAR

We prove that for all constants a, NQP = NTIME[n^polylog(n)] cannot be (1/2 + 2^(-log^a n) )-approximated by 2^(log^a n)-size ACC^0 of THR circuits (ACC^0 circuits with a bottom layer of threshold gates). Previously, it was even open whether E^NP can be (1/2+1/sqrt(n))-approximated by AC^0[2] circuits.
More generally, we establish a connection showing that, for a typical circuit class C, non-trivial nondeterministic CAPP algorithms imply strong (1/2 + 1/n^{omega(1)}) average-case lower bounds for nondeterministic time classes against C circuits. The existence of such (deterministic) algorithms is much weaker than the widely believed conjecture PromiseBPP = PromiseP.

Our new results build on a line of recent works, including [Murray and Williams, STOC 2018], [Chen and Williams, CCC 2019], and [Chen, FOCS 2019]. In particular, it strengthens the corresponding (1/2 + 1/polylog(n))-inapproximability average-case lower bounds in [Chen, FOCS 2019]. The two important technical ingredients are techniques from Cryptography in NC^0 [Applebaum et al., SICOMP 2006], and Probabilistic Checkable Proofs of Proximity with NC^1-computable proofs.  

SundayDec 22, 201913:30
Computer Science SeminarRoom 155
Speaker:Hilal AsiTitle:Nearly Instance-Optimal Mechanisms in Differential PrivacyAbstract:opens in new windowin html    pdfopens in new windowSPECIAL FOUNDATIONS OF COMPUTER SCIENCE SEMINAR

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.

MondayDec 09, 201911:15
Computer Science SeminarRoom 155
Speaker:Karthik C.STitle:Clustering: How hard is it to classify data? Abstract:opens in new windowin html    pdfopens in new windowSPECIAL FOUNDATIONS OF COMPUTER SCIENCE SEMINAR

Two popular objectives optimized in clustering algorithms are k-means and k-median. The k-means (resp. k-median) problem in the L_p-metric is specified by n points as input and the goal is to classify the input point-set into k clusters such that the k-means (resp. k-median) objective is minimized. The best-known inapproximability factor in literature for these NP-hard problems in L_p-metrics were well-below 1.01. In this talk, we take a significant step to improve the hardness of approximating these problems in various L_p-metrics.

TuesdayNov 19, 201911:15
Special Guest LectureRoom 1
Speaker:Professor Yakov Pesin Title:Smooth models of systems with complicated stochastic behaviorsAbstract:opens in new windowin html    pdfopens in new window

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.   

ThursdayDec 13, 201811:30
Computer Science Seminar
Speaker: Sampath KannanTitle: Fairness in Algorithmic Decision MakingAbstract:opens in new windowin html    pdfopens in new windowWOLFSON AUDITORIUM

In this talk we survey some formulations of fairness requirements for decision making under uncertainty. We then discuss results from 3 recent papers:

  1. Treating individuals fairly is not in conflict with long-term scientific learning goals if the population is sufficiently diverse.
  2. When there is a pipeline of decisions, end-to-end fairness is impossible to achieve even in a very simple model.
  3. Exploiting the knowledge acquired by others can unfairly advantage the free rider.

These papers are joint work with a number of co-authors:

Christopher Jung, Neil Lutz, Jamie Morgenstern, Aaron Roth, Bo Waggoner, Steven Wu, and Juba Ziani

ThursdayNov 29, 201811:30
Computer Science Seminar
Speaker: Noam NisanTitle:The Communication Complexity of Cake CuttingAbstract:opens in new windowin html    pdfopens in new windowWOLFSON AUDITORIUM

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

ThursdayNov 22, 201811:30
Computer Science Seminar
Speaker:Amos FiatTitle:C-single crossing Interdependent valuationsAbstract:opens in new windowin html    pdfopens in new windowWOLFSON AUDITORIUM

We consider the goal of social welfare maximization where a single item is to be assigned to one of to n potential agents with interdependent values.

That is, each agent has her own private signal, and the valuation of each agent is a known function of all n private signals. This captures settings such as valuations for artwork, oil drilling rights, broadcast rights, and many more. In the interdependent value setting, all previous work has assumed a so-called single-crossing condition. Single-crossing means that the impact of agent i’s private signal, s_i, on her own valuation is greater than the impact of s_ii on the valuation of any other agent. It is known that without the single-crossing condition an efficient outcome cannot be obtained. We study welfare maximization for interdependent valuations through the lens of approximation.

We show that, in general, without the single-crossing condition, one cannot hope to approximate the optimal social welfare any better than the approximation given by assigning the item to a random bidder. Consequently, we introduce a relaxed version of single-crossing, c-single-crossing, parameterized by c ≥ 1, which means that the impact of s_i on the valuation of agent i is at least 1/c times the impact of s_i on the valuation of any other agent (c = 1 is single-crossing). Using this parameterized notion, we obtain a host of positive results. We also consider interdependent settings when valuations are concave and give improved results.

Joint work with Alon Eden, Michal Feldman, and Kira Goldner.

ThursdayNov 08, 201811:30
Computer Science Seminar
Speaker: Shai Shalev-ShwartzTitle:Formalizing the “Duty of Care” for self-driving carsAbstract:opens in new windowin html    pdfopens in new windowWOLFSON AUDITORIUM

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.

ThursdayNov 01, 201811:30
Computer Science Seminar
Speaker:Adi ShamirTitle:Machine Learning in Security: Applications and ImplicationsAbstract:opens in new windowin html    pdfopens in new windowWolfson Auditorium

In this talk I will survey the way machine learning research is affecting the field of security, and the way security research Is affecting the field of machine learning. After giving several examples of each type, I will discuss some of the latest developments In adversarial machine learning research, which are used by hackers to defeat security mechanisms based on regular machine learning techniques

ThursdayJun 14, 201816:00
Special Guest LectureRoom 1
Speaker:Don ZagierTitle:Units, K-theory, and knotsAbstract:opens in new windowin html    pdfopens in new windowPLEASE NOTE THE CHANGE IN TIME

  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.

ThursdayMar 22, 201812:30
Special Guest SeminarRoom 108
Speaker:Mark BorodovskyTitle:Genome Decoding: Learning and Following Sequence PatternsAbstract:opens in new windowin html    pdfopens in new window

Genome-wide forces of mutation and selection create local and global sequence patterns that carry information on functional role of genomic DNA. I will describe algorithmic approaches to genome analysis that decode sequence patterns and identify features of structural gene organization and gene expression (e.g. leaderless transcription). The algorithms make unsupervised inference of the structure of underlying graphical model and its parameters. 
The subsequently developed software tools were, among other applications, used at NCBI (Bethesda, MD) to annotate and re-annotate 2,500+ fungal genomes and 130,000+ prokaryotic genomes. Yet another algorithm was employed by DOE JGI (Walnut Creek, CA) to annotate the largest collection of metagenomes. 

Speaker s short Bio
Mark Borodovsky, PhD, a Regents' Professor at the Joint Georgia Tech and Emory University Department of Biomedical Engineering and the School of Computational Science and Engineering. Since 1990 when he arrived to Atlanta from Moscow, Dr Borodovsky had also joint faculty appointments at the School of Biology and the School of Mathematics. Dr. Borodovsky is a Founder of the Georgia Tech Bioinformatics graduate program.

TuesdayFeb 20, 201810:00
Special Guest SeminarRoom 1
Speaker:Prof. David SontagTitle:AI for Health Needs CausalityAbstract:opens in new windowin html    pdfopens in new window

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).

TuesdayFeb 20, 201810:00
Special Guest SeminarRoom 1
Speaker:Prof. David SontagTitle:AI for Health Needs CausalityAbstract:opens in new windowin html    pdfopens in new window

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).

ThursdayJan 18, 201811:00
Special Guest SeminarRoom 290C
Speaker:Shaull Almagor Title:Automated Verification of Infinite-State Systems with Certifiable AlgorithmsAbstract:opens in new windowin html    pdfopens in new window

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.

TuesdayDec 26, 201712:30
Distinguished Lecture SeriesRoom 1
Speaker:Walter StraussTitle:Steady Water WavesAbstract:opens in new windowin html    pdfopens in new window
The mathematical study of water waves became possible after the derivation of the basic mathematical equations of fluids by Euler in 1752. Later, water waves, with a free boundary at the air interface, played a central role in the work of Poisson, Cauchy, Stokes, Levi-Civita and many others. It has seen greatly renewed interest among mathematicians in recent years. I will consider classical 2D traveling water waves with vorticity. By means of local and global bifurcation theory using topological degree, one can prove that there exist many such waves. They are exact smooth solutions of the Euler equations with the physical boundary conditions. Some of the waves are quite tall and steep and some are overhanging. There are periodic ones and solitary ones. I will also exhibit some numerical computations of such waves. Many fundamental problems remain open.
TuesdayDec 26, 201711:15
Distinguished Lecture SeriesRoom 1
Speaker:Allen TannenbaumTitle:Optimal Mass Transport and the Robustness of Complex NetworksAbstract:opens in new windowin html    pdfopens in new window

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.

WednesdayNov 22, 201716:15
Special Guest LectureRoom 290C
Speaker:Dalia TerhesiuTitle:The pressure function for infinite equilibrium Abstract:opens in new windowin html    pdfopens in new window

 Assume that $(X,f)$ is a dynamical system and $\phi$ is a real non negative potential such that the corresponding $f$-invariant measure $\mu_\phi$ measure is infinite.  Under assumptions of good inducing schemes, we give conditions under which the pressure of $f$ for a perturbed potential $\phi+s\psi$ relates to the pressure of the induced system term.
This extends some of Sarig's results to the setting of infinite "equilibrium states".
In addition, limit properties of the family of measures $\mu_{\phi+s\psi}$ as $s\to 0$ are studied and statistical properties (e.g. correlation coefficients) under the limit measure are derived. I will discuss several examples.
This is based on joint work with H. Bruin and M. Todd.

TuesdayNov 14, 201716:15
Geometry and Topology Seminar & Mathematical Analysis and Applications SeminarRoom 290C
Speaker:Ran TesslerTitle:Integrable hierarchies, wave functions and open intersection theoriesAbstract:opens in new windowin html    pdfopens in new window
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.
TuesdayNov 14, 201711:15
Distinguished Lecture SeriesRoom 1
Speaker:Prof. Yakov PesinTitle:The Dynamical Systems Approach to Coupled Map LatticesAbstract:opens in new windowin html    pdfopens in new window
Coupled Map Lattices (CML) of an unbounded media appear as a result of time and space discretization of evolutional partial differential equations but can also be viewed as original phenomenological models of the medium. I will present the dynamical systems approach to study the global behavior of solutions of CML. In particular, I will describe the dynamics of the evolution operator on the set of traveling wave solutions of CML and discuss the phenomenon known as spatio-temporal chaos. I will illustrate this phenomenon in the particular example of CML associated with the famous FitzHue-Nagumo equation that describes propagation of voltage impulse through a nerve axon. When the leading parameter of this equation varies the dynamics undergoes several stages presenting Morse-Smale type dynamics, strange attractors and Smale horseshoes.
TuesdayOct 17, 201716:15
Geometry and Topology Seminar & Mathematical Analysis and Applications SeminarRoom 290C
Speaker:Gabriel Katz Title:Holography of traversing flows and its applications to the inverse scattering problemsAbstract:opens in new windowin html    pdfopens in new window

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.

TuesdayJan 24, 201710:00
Special Guest SeminarRoom 208
Speaker:Yair FieldTitle:Detecting human genetic adaptation in historical timescalesAbstract:opens in new windowin html    pdfopens in new window

Detecting genetic adaptation in recent human history is a major challenge of population genetics. The fundamental problem is to infer historical changes in the frequency of genetic variants (alleles), from data of contemporary genomes. With this we can identify unusual changes that are unlikely to have occurred in the absence of selective pressures. However, a generally applicable method to infer recent allele frequency changes is lacking. Instead, present methods can only detect frequency changes under very restrictive assumptions on the model of selection. Moreover, their time resolution is generally limited to prehistoric scales, on the order of the past 25-75 thousand years. To address these gaps we developed a novel statistical method, Singleton Density Score (SDS), that infers the recent changes in allele frequencies from local variation in contemporary genome sequences with specificity to historical timescales. Applied to data of ~3000 genomes from the UK10K project, SDS reveals that human genetic adaptation continued well into historical times. Over the past ~2000-3000 years, ancestors of modern Britons genetically evolved over a range of phenotypes related to diet, immunity, and physical appearance. Notably, we found that polygenic adaptation, whereby selection acting on many small-effect variants across the genome that together determine a single trait, has played a pervasive, previously undetected role in shaping present genotypic and phenotypic variation.
Field et al, Science 2016, Detection of human adaptation during the past 2000 years.

ThursdayJan 12, 201711:00
Special Guest SeminarRoom 208
Speaker:Amir AbboudTitle:Hardness in PAbstract:opens in new windowin html    pdfopens in new window
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.
TuesdayDec 20, 201611:00
Special Guest SeminarRoom 208
Speaker:Uri Shalit Title:Learning to act from observational dataAbstract:opens in new windowin html    pdfopens in new window

The proliferation of data collection in the health, commercial, and economic spheres, brings with it opportunities for extracting new knowledge with concrete policy implications. Examples include individualizing medical practices based on electronic healthcare records, and understanding the implications of job training programs on employment and income.
The scientific challenge lies in the fact that standard prediction models such as supervised machine learning are often not enough for decision making from this so-called "observational data": Supervised learning does not take into account causality, nor does it account for the feedback loops that arise when predictions are turned into actions. On the other hand, existing causal-inference methods are not adapted to dealing with the rich and complex data now available, and often focus on populations, as opposed to individual-level effects.
The problem is most closely related to reinforcement learning and bandit problems in machine learning, but with the important property of having no control over experiments and no direct access to the actor's model.
In my talk I will discuss how we apply recent ideas from machine learning to individual-level causal-inference and action. I will introduce a novel generalization bound for estimating individual-level treatment effect, and further show how we use representation learning and deep temporal generative models to create new algorithms geared towards this problem. Finally, I will show experimental results using data from electronic medical records and data from a job training program.

ThursdayDec 08, 201612:00
Special Guest SeminarRoom 1
Speaker:Shachar ItzhakyTitle:From Programming Languages to Programming Systems – Software Development by RefinementAbstract:opens in new windowin html    pdfopens in new window

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.

SundayApr 03, 201611:15
Distinguished Lecture SeriesRoom 1
Speaker:Lai-Sang Young Title:Measuring dynamical complexityAbstract:opens in new windowin html    pdfopens in new windowRefreshments after the lecture in Ziskind lobby
I will discuss, for differentiable dynamical systems, three ways to capture dynamical complexity: (A) hyperbolicity, which measures the sensitivity of dependence on initial conditions, (B) entropy, which measures the predictability of future dynamical events in the sense of information theory, and (C) the speed of correlation decay or equivalently the rate at which memory is lost. I will review these ideas in nontechnical terms, present theorems showing how they are related, and give a very brief (and somewhat personal) survey of the progress made in the last decades. For illustration, I will show how these results apply to a concrete example: shear- induced chaos in periodically kicked oscillators, a phenomenon closely related to that observed by van der Pol nearly 100 years ago.
MondaySep 07, 201514:00
Special Guest LectureRoom 1
Speaker:Jasmin FisherTitle:Computing CancerAbstract:opens in new windowin html    pdfopens in new window

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.

MondayJul 20, 201516:00
Geometry and Topology Seminar & Mathematical Analysis and Applications SeminarRoom 261
Speaker:Regina RotmanTitle:Quantitative homotopy theory and the lengths of geodesics on Riemannian manifoldsAbstract:opens in new windowin html    pdfopens in new window

Let M be a closed Riemannian manifold. There are numerous results that establish the existence of various minimal objects on M, such as periodic geodesics, minimal surfaces, or geodesic nets.  We will present some effective versions of these existence theorems.

For example, we will present diameter upper bounds for the lengths of three shortest simple periodic geodesics on a Riemannian 2-sphere, which can be interpreted as an effective version of the existence theorem of Lusternik and Schnirelmann. (Joint with Y. Liokumovich and A. Nabutovsky).

Finding upper bounds for the size of smallest stationary objects is closely related with construction of "optimal" homotopies.  We will show that if M is a closed surface of diameter d (with or without boundary), then any simple closed curve on M that can be contracted to a point over free loops of length less than L, can be contracted over based loops of length at most 3L+2d. (Joint with G. Chambers).

ThursdayApr 30, 201516:00
Special Guest SeminarRoom 261
Speaker:Shmuel GurvitzTitle:Does the measurement take place when nobody observes it?Abstract:opens in new windowin html    pdfopens in new window
MondayFeb 02, 201514:00
Special Guest LectureRoom 1
Speaker:P. AnandanTitle:Inventing the Future: Microsoft Research in its Third DecadeAbstract:opens in new windowin html    pdfopens in new window
Microsoft Research is 23 years old and is a premiere Computer Science research organization in the world. In this talk I will look back at the work done at MSR during the recent years and explain how we are significantly contributing to progress in Science, Technology and Society.