You are here

Other seminars

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