You are here

Other seminars

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

Link: https://arxiv.org/abs/1911.04014

 

 

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.
Reference:
Field et al, Science 2016, Detection of human adaptation during the past 2000 years. https://www.ncbi.nlm.nih.gov/pubmed/27738015

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.