You are here


ThursdayFeb 02, 202312:45
Faculty SeminarRoom 1
Speaker:Aviad Levis Title:Computational Imaging for Scientific Discovery: From Cloud Physics to Black Holes DynamicsAbstract:opens in new windowin html    pdfopens in new window

Imaging plays a key role in advancing science, from revealing the internal structure of clouds to providing the first visual evidence of a black hole. While both examples come from different imaging systems, they illustrate what can be achieved with modern computational approaches. Computational imaging combines concepts from physics, machine learning, and signal processing to reveal hidden structures at the smallest and largest of scales. In this talk, I will highlight how peeling away layers of the underlying physics leads to a spectrum of algorithms targeting new scientific discoveries. I will focus on the Event Horizon Telescope (EHT), a unique computational camera with the goal of imaging the glowing fluid surrounding supermassive black holes. In May of 2022, the EHT collaboration revealed the first images of the black hole at the center of our galaxy: Sagittarius A* (Sgr A*). These images were computationally reconstructed from measurements taken by synchronized telescopes around the globe. While images certainly offer interesting insights, looking toward the future, we are developing new computational algorithms that aim to go beyond a 2D image. For example, could we use EHT observations to recover the dynamic evolution or even the 3D structure? We tackle these challenges by integrating emerging AI concepts with physics models. Our hope is that in the not-too-distant future, these new and exciting prospects will enable scientific discovery and even provide a glimpse into the very nature of space-time itself in our galaxy's most extreme environment.

Aviad Levis is a postdoctoral scholar in the Department of Computing and Mathematics at Caltech, working with Prof. Katherine Bouman. Currently, as part of the Event Horizon Telescope collaboration, his work focuses on developing novel computational methods for imaging black hole dynamics. Prior to that, he received his Ph.D. (2020) from the Technion and his B.Sc. (2013) from Ben-Gurion University. Notably, his Ph.D. research into 3D remote sensing of clouds is a key enabler in a novel interdisciplinary space mission (CloudCT) funded by the ERC and led by Yoav Schechner, Ilan Koren, and Klaus Schilling. Aviad is a recipient of the Zuckerman and the Viterbi postdoctoral fellowships.


SundayDec 18, 202211:00
Faculty SeminarRoom 155
Speaker:Brit Youngmann Title:Data Tools for Accelerated Scientific DiscoveriesAbstract:opens in new windowin html    pdfopens in new window
Like general data scientists, scientists conducting empirical research rely on data and analyze it to extract meaningful insights. Yet, scientists have two qualities that distinguish them from general data scientists: (1) they rely on extensive scientific domain knowledge to make scientific discoveries, and (2) they aim to explain and understand, not simply predict, the real world. These two qualities must be reflected in their data analysis tools to assist them and accelerate the process of making real-world discoveries. In this talk, I will present data tools for accelerated scientific discoveries. In particular, I will present tools that assist scientists in investigating their data using scientific knowledge and helping scientists acquire missing data and domain-specific knowledge required to understand real-world mechanisms and draw trustworthy conclusions.
WednesdayAug 17, 202210:30
Faculty SeminarRoom 155
Speaker:Efrat ShimronTitle:Data Crimes: The Risk in Naive Training of Medical AI AlgorithmsAbstract:opens in new windowin html    pdfopens in new window
Although open-access databases are an important resource in the current deep learning (DL) era, they are sometimes used in an "off label" manner: data published for one task are used during training of algorithms for a different task. In this seminar I will show that this leads to biased, overly optimistic results of well-known inverse problem solvers, focusing on algorithms developed for magnetic resonance imaging (MRI) reconstruction. I will show that when such algorithms are trained using off-label data, they yield biased results, with up to 48% artificial improvement. The underlying cause is that public databases are often preprocessed using hidden pipelines, which change the data features and improve the inverse problem conditioning. My work shows that canonical algorithms - Compressed Sensing, Dictionary Learning, and Deep Learning algorithms - are all prone to this form of bias. Furthermore, once trained, these algorithms exhibit poor generalization to real-world data, thus they could produce unreliable results in clinical setups. To raise awareness to the growing problem of naive use of public data and the associated biased results, the term "data crimes" is coined.
WednesdayJan 12, 202215:15
Faculty Seminar
Speaker:Oded SteinTitle:Mathematical Foundations of Robust Geometry and FabricationAbstract:opens in new windowin html    pdfopens in new windowThe seminar will be over the zoom:
Current geometry methods for creating and manipulating shapes on computers can sometimes be unreliable and fail unpredictably. Such failures make geometry tools hard to use, prevent non-experts from creating geometry on their computers, and limit the use of geometry methods in domains where safety is critical. We will discuss my recent efforts in proving when existing methods work as intended, my work in making methods more robust to imperfect input, my work in the creation of new reliable tools with mathematical guarantees, and my future efforts towards a reliable geometry pipeline. When used for computational fabrication, geometry methods can be expensive, finicky, and require a controlled environment. I will show you how simple and economical manufacturing techniques can be used for computational fabrication by exploiting the geometric constraints inherent in specific materials and fabrication methods. We will take a look at how I create geometric tools to design for constrained fabrication techniques, and discuss how computational fabrication can be made both economical as well as accessible in difficult environments. Zoom:
WednesdayJan 05, 202211:15
Faculty SeminarRoom 1
Speaker:Amir GiladTitle:Informed Data ScienceAbstract:opens in new windowin html    pdfopens in new window
Data science has become prevalent in various fields that affect day-to-day lives, such as healthcare, banking, and the job market. The process of developing data science applications usually consists of several automatic systems that manipulate and prepare the data in different manners. Examples of automatic data manipulations and preparations include generating synthetic data, interactive data exploration, repairing the data, and labeling it for machine learning. These systems can be highly complex and even data scientists can find it difficult to understand and verify their output. Moreover, uninformed use of these systems can lead to errors that may affect the quality of the results of such applications. In the talk, I will highlight prominent challenges in the data science process and present three aspects of my research that are meant to assist in this process. In particular, I will present a solution that generates natural language explanations for query results, a tool for generating synthetic linked data, and a solution that explains complex queries using abstract database instances. Zoom:
SundayJan 02, 202211:00
Faculty SeminarRoom 1
Speaker:Tom HopeTitle:Harnessing Scientific Literature for Boosting Discovery and InnovationAbstract:opens in new windowin html    pdfopens in new window

With millions of scientific papers coming out every year, researchers are forced to allocate their attention to increasingly narrow areas, creating isolated research bubbles that limit knowledge discovery. This fragmentation of science slows down progress and prevents the formation of cross-domain links that catalyze breakthroughs. Toward addressing these large-scale challenges for the future of science, my work develops new paradigms for searching, recommending and discovering scholarly knowledge.

In this talk, I will present methods and systems for recommending research inspirations and creating links across areas and ideas. My approach is based on extracting novel structural representations of scholarly literature, and leveraging them for "matchmaking" between problems and solutions and between scientists. I will also present a new task we introduced for jointly addressing diversity, ambiguity and hierarchy of language in scientific texts. In this new setting, the goal is to learn to construct cross-document coreference clusters along with a hierarchy defined over the clusters. As I will demonstrate, being able to automatically induce this graph structure can help unlock important applications in scientific discovery, but this remains a highly difficult open problem.

WednesdayDec 29, 202111:15
Faculty SeminarRoom 1
Speaker:Naama Ben DavidTitle:Theoretical Foundations for Emerging Multiprocessor HardwareAbstract:opens in new windowin html    pdfopens in new windowThis seminar will be held in Room 1 and also in Zoom at:

Due to the end of Moore’s law, hardware has been developing more rapidly in recent years than it has at any point since the early days of computing. These hardware developments are trending toward multiprocessor settings, which have the potential to deliver the speedups that CPU frequency scaling can no longer support. 
In this talk, I will discuss my work on building theoretical foundations for emerging multiprocessor technologies. I will focus on one line of work that concerns a data center communication primitive called Remote Direct Memory Access (RDMA). RDMA allows accessing the memory of a remote machine without involving its CPU, and has become widely adopted in recent years due to its performance advantages. I’ll present the first theoretical model that captures RDMA’s capabilities, and use it to show that RDMA is more powerful than previous communication technology. I’ll then present the design of a state machine replication system based on those theoretical insights that improves previous state-of-the-art latency both in failure-free executions (by over 2x) and in failure recovery (by over 10x).


TuesdayDec 28, 202111:15
Faculty SeminarRoom 1
Speaker:Talya EdenTitle:Approximating the Arboricity in Sublinear TimeAbstract:opens in new windowin html    pdfopens in new windowThe lecture will be also in Zoom at:

We consider the problem of approximating the arboricity of a graph $G=(V,E)$, which we denote by $arb(G)$, in sublinear time, where the arboricity of a graph is the minimal number of forests required to cover its edges. An algorithm for this problem may perform degree and neighbor queries, and is allowed a small error probability. We design an algorithm that outputs an estimate $\hat{\alpha}$, such that with probability $1-1/poly(n)$, $arb(G)/c log2 n \leq \hat{\alpha} \leq \arb(G)$ , where $n=|V|$ and $c$ is a constant. The expected query complexity and running time of the algorithm are $O(n/arb(G))\cdot \poly(\log n)$, and this upper bound also holds with high probability. This bound is optimal for such an approximation up to a $poly(log n)$ factor. This result has important implications as many sublinear-time algorithms are parameterized by the arboricity, and rely on getting its value as input.

Based on joint work with Saleet Mossel and Dana Ron.


SundayDec 26, 202111:00
Faculty SeminarRoom 155
Speaker:Jonathan Mosheiff Title:Derandomization of elementary random codesAbstract:opens in new windowin html    pdfopens in new window
An error correcting code should ideally be 1) of large rate, 2) noise tolerant and 3) efficiently decodable. Elementary probabilistic constructions, such as random linear codes, achieve an excellent trade-off between the first two objectives, but unfortunately, decoding them is believed to be algorithmically hard. This motivates us to derandomize these constructions in a way that preserves noise tolerance, while adding structure that can be used for algorithmic purposes. In many settings, such as the ubiquitous list-decoding model, noise-tolerance can be seen to be a "local property of codes" - a new concept analogous to the classical notion of a local property of graphs. This observation turns out to yield a highly effective framework for the analysis and derandomization of elementary random codes. In this talk I will discuss the line of research that originates in the analogy between codes and graphs, and culminates, so far, in the recent proof that many Reed-Solomon codes achieve list-decoding capacity. Based on joint works with Venkatesan Guruswami, Ray Li, Nati Linial, Peter Manohar, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas and Mary Wootters.
WednesdayDec 22, 202111:15
Faculty SeminarRoom 1
Speaker:David Wajc Title:Matching in Evolving EnvironmentsAbstract:opens in new windowin html    pdfopens in new window
Traditional computational models consider a one-shot computation, run on a single machine, with full knowledge of the input. In contrast, in many modern applications, the input is evolving, or is too large to be stored on any one machine, and is therefore partially unknown. These aspects of modern computation require decision-making under uncertainty. For example, in ride hailing applications, where drivers and riders arrive over time, the app needs to match users to each other quickly, despite uncertain information about future arrivals. In this talk I will present some of my work on algorithms for scenarios such as the above, where decisions must be made swiftly (and possibly irrevocably) following changes to their evolving input data. First, I will discuss the resolution of two decades-old questions in the area of online algorithms, concerning the online matching and online edge-coloring problems. Throughout, I will show how the use of randomization helps solve problems with uncertain input, highlighting key techniques underlying my work. I will then discuss the resolution of an open question concerning the use of randomization for the dynamic matching problem in the face of adaptively-changing data.
MondayDec 13, 202115:40
Faculty Seminar
Speaker:fTitle:fAbstract:opens in new windowin html    pdfopens in new window

Due to the end of Moore’s law, hardware has been developing more rapidly in recent years than it has at any point since the early days of computing. These hardware developments are trending toward multiprocessor settings, which have the potential to deliver the speedups that CPU frequency scaling can no longer support.


In this talk, I will discuss my work on building theoretical foundations for emerging multiprocessor technologies. I will focus on one line of work that concerns a data center communication primitive called Remote Direct Memory Access (RDMA). RDMA allows accessing the memory of a remote machine without involving its CPU, and has become widely adopted in recent years due to its performance advantages. I’ll present the first theoretical model that captures RDMA’s capabilities, and use it to show that RDMA is more powerful than previous communication technology. I’ll then present the design of a state machine replication system based on those theoretical insights that improves previous state-of-the-art latency both in failure-free executions (by over 2x) and in failure recovery (by over 10x).


SundayDec 12, 202111:00
Faculty SeminarRoom 155
Speaker:Kiril SoloveyTitle:Large-scale multi-robot systems: From algorithmic foundations to smart-mobility applicationsAbstract:opens in new windowin html    pdfopens in new window
Multi-robot systems are already playing a crucial role in various domains such as manufacturing and warehouse automation. In the future, these systems will be incorporated into our daily lives through drone-delivery services and smart-mobility systems that comprise thousands of autonomous vehicles, to give a few examples. The anticipated benefits of multi-robot systems are numerous, ranging from increased safety and efficiency, to broader societal facets such as sustainability. However, to reap those rewards we must develop algorithms that can adapt rapidly to unexpected changes on a massive scale. Importantly, these algorithms must capture (i) dynamical and collision-avoidance constraints of individual robots, (ii) interactions between multiple robots, and (iii), more broadly, the interaction of those systems with their environment. These considerations give rise to extremely complex and high-dimensional optimization problems that need to be solved in real-time. In this talk, I will present progress on the design of systematic control and decision-making mechanisms to allow the effective, and societally-equitable deployment of multi-robot systems. I will highlight results on fundamental capabilities for multi-robot systems (e.g., motion planning and task allocation), as well as applications in smart-mobility systems. I will also discuss challenges and opportunities for smart mobility in addressing societal issues, including traffic congestion and fairness.
TuesdayJan 26, 202116:00
Faculty Seminar
Speaker:Yuval MoskovitchTitle:Towards Reliable Data-Driven ComputationsAbstract:opens in new windowin html    pdfopens in new window

Data-driven methods are increasingly being used in domains such as fraud and risk detection, where data-driven algorithmic decision making may affect human life.
The growing impact of data and data-driven systems on society makes it important that people be able to trust analytical results obtained from data-driven computations.
This can be done in two complementary ways: by providing result explanations so that the user understands the computation and the basis for the observed results; and by profiling and monitoring the data used in the computation, to make the results more reliable in the first place.

In the first part of the talk, I will present the use of provenance -- information regarding the data origin and computational process -- for providing explanations of computational results. In the second part of the talk, I will present a method for data profiling using labels, as an example of a data-focused technique to facilitate an analyst building a reliable decision-making pipeline.


ThursdayJan 14, 202111:00
Faculty Seminar
Speaker:Hila Peleg Title:Next Generation Programming with Program SynthesisAbstract:opens in new windowin html    pdfopens in new window

Program synthesis is the problem of generating a program to satisfy a specification of user intent. Since these specifications are usually partial, this means searching a space of candidate programs for one that exhibits the desired behavior. The lion's share of the work on program synthesis focuses on new ways to perform the search, but hardly any of this research effort has found its way into the hands of users.

We wish to use synthesis to augment the programming process, leveraging both optimized search algorithms and concepts that are part of the programmer's life such as code review and read-eval-print loops (REPL). This talk describes three synthesis-based techniques that bring program synthesis into the development workflow.

A major concern in designing for the user is that it can put the interface of the synthesizer at odds with state of the art synthesis techniques. Synthesis is, at best, a computationally hard problem, and any changes made to make the tool more usable can interfere with the synthesizer and its internals. We therefore demonstrate the process of bringing synthesis theory into practice when tool design also requires an algorithm re-design.

MondayMay 25, 202017:30
Faculty Seminar
Speaker:Rotem Arnon-Friedman Title:Randomness extraction and amplification in the quantum worldAbstract:opens in new windowin html    pdfopens in new windowZoom meeting:

Randomness is an essential resource in computer science. In most applications perfect, and sometimes private, randomness is needed, while it is not even clear that such a resource exists. It is well known that the tools of classical computer science do not allow us to create perfect randomness from a single weak source of randomness - a fact that initiated the study of special functions called randomness extractors.
The first part of the talk will be focused on the performance of randomness extractors in the presence of a quantum adversary and present a new model for two-source extractors, termed the quantum Markov model.
In the second part of the talk I will describe a task called "randomness amplification and privatization", where a single and public Santha-Vazirani source of randomness is being transformed into uniform and private randomness - a cryptographic task that cannot be accomplished using the tools of classical computer science. I will then present a protocol that builds on the extractors discussed in the first part of the talk and explain the main ingredients of its security proof.

Zoom meeting :

SundayJan 26, 202011:15
Faculty SeminarRoom 155
Speaker:Meirav Zehavi Title:On Parameterized Analysis and the Disjoint Paths ProblemAbstract:opens in new windowin html    pdfopens in new window

Parameterized Anaylsis leads both to deeper understanding of intractability results and to practical solutions for many NP-hard problems. Informally speaking, Parameterized Analysis is a mathematical paradigm to answer the following fundamental question: What makes an NP-hard problem hard? Specifically, how do different parameters (being formal quantifications of structure) of an NP-hard problem relate to its inherent difficulty? Can we exploit these relations algorithmically, and to which extent? Over the past three decades, Parameterized Analysis has grown to be a mature field of outstandingly broad scope with significant impact from both theoretical and practical perspectives on computation.

In this talk, I will first give a brief introduction of the field of Parameterized Analysis. Then, I will discuss some recent work in this field, where I mainly address (i) problems at the core of this field, rooted at Graph Minors and Graph Modification Problems, and (ii) applications of tools developed in (i) in particular, and of parameterized analysis in general, to Computational Geometry and Computational Social Choice. Additionally, I will zoom into a specific result, namely, the first single-exponential time parameterized algorithm for the Disjoint Paths problem on planar graphs. An efficient algorithm for the Disjoint Paths problem in general, and on "almost planar" graphs in particular, is a critical part in the quest for the establishment of an Efficient Graph Minors Theory. As the Graph Minors Theory is the origin of Parameterized Analysis and ubiquitous in the design of parameterized algorithms, making this theory efficient is a holy grail in the field.

SundayJan 19, 202011:15
Faculty SeminarRoom 155
Speaker:Oded PadonTitle:Verification of distributed protocols using decidable logicsAbstract:opens in new windowin html    pdfopens in new window

Formal verification of infinite-state systems, and distributed systems in particular, is a long standing research goal. I will describe a series of works that develop a methodology for verifying distributed algorithms and systems using decidable logics, employing decomposition, abstraction, and user interaction. This methodology is implemented in an open-source tool, and has resulted in the first mechanized proofs of several important distributed protocols. I will also describe a novel approach to the problem of invariant inference based on a newly formalized duality between reachability and mathematical induction. The duality leads to a primal-dual search algorithm, and a prototype implementation already handles challenging examples that other state-of-the-art techniques cannot handle. I will briefly describe several other works, including a new optimization technique for deep learning computations that achieves significant speedups relative to existing deep learning frameworks.

ThursdayJan 16, 202011:00
Faculty SeminarSchmidt Auditorium
Speaker:Alon Kipnis Title:Higher Criticism for discriminating frequency-tables and testing authorshipAbstract:opens in new windowin html    pdfopens in new windowNOTE UNUSUAL DAY AND PLACE

The Higher Criticism (HC) test is a useful tool for detecting the presence of a signal spread across a vast number of features, especially in the sparse setting when only few features are useful while the rest are pure noise. We adapt the HC test to the two-sample setting of detecting changes between two frequency tables. We apply this adaptation to authorship attribution challenges, where the goal is to identify the author of a document using other documents whose authorship is known. The method is simple yet performs well without handcrafting and tuning. Furthermore, as an inherent side effect, the HC calculation identifies a subset of discriminating words, which allow additional interpretation of the results. Our examples include authorship in the Federalist Papers, machine-generated texts, and the identity of the creator of the Bitcoin.

We take two approaches to analyze the success of our method. First, we show that, in practice, the discriminating words identified by the test have low variance across documents belonging to a corpus of homogeneous authorship. We conclude that in testing a new document against the corpus of an author, HC is mostly affected by words characteristic of that author and is relatively unaffected by topic structure. Finally, we analyze the power of the test in discriminating two multinomial distributions under a sparse and weak perturbation model. We show that our test has maximal power in a wide range of the model parameters, even though these parameters are unknown to the user.

SundayJan 12, 202011:00
Faculty SeminarRoom 155
Speaker:Yaniv Romano Title:Reliability, Equity, and Reproducibility in Modern Machine Learning Abstract:opens in new windowin html    pdfopens in new windowPLEASE NOTE THE UNUSUAL TIME

Modern machine learning algorithms have achieved remarkable performance in a myriad of applications, and are increasingly used to make impactful decisions in the hiring process, criminal sentencing, healthcare diagnostics and even to make new scientific discoveries. The use of data-driven algorithms in high-stakes applications is exciting yet alarming: these methods are extremely complex, often brittle, notoriously hard to analyze and interpret. Naturally, concerns have raised about the reliability, fairness, and reproducibility of the output of such algorithms. This talk introduces statistical tools that can be wrapped around any "black-box" algorithm to provide valid inferential results while taking advantage of their impressive performance. We present novel developments in conformal prediction and quantile regression, which rigorously guarantee the reliability of complex predictive models, and show how these methodologies can be used to treat individuals equitably. Next, we focus on reproducibility and introduce an operational selective inference tool that builds upon the knockoff framework and leverages recent progress in deep generative models. This methodology allows for reliable identification of a subset of important features that is likely to explain a phenomenon under-study in a challenging setting where the data distribution is unknown, e.g., mutations that are truly linked to changes in drug resistance.

TuesdayJan 07, 202011:00
Faculty SeminarRoom 1
Speaker:Vardan PapyanTitle:Traces of Class/Cross-Class Structure Pervade Deep Learning SpectraAbstract:opens in new windowin html    pdfopens in new windowNOTE THE UNUSUAL DAY AND ROOM

Numerous researchers recently applied empirical spectral analysis to the study of modern deep learning classifiers, observing spectral outliers and small but distinct bumps often seen beyond the edge of a "main bulk". This talk presents an important formal class/cross-class structure and shows how it lies at the origin of these visually striking patterns. The structure is shown to permeate the spectra of deepnet features, backpropagated errors, gradients, weights, Fisher Information matrix and Hessian, whether these are considered in the context of an individual layer or the concatenation of them all. The significance of the structure is illustrated by (i) demonstrating empirically that the feature class means separate gradually from the bulk as function of depth and become increasingly more orthogonal, (ii) proposing a correction to KFAC, a well known second-order optimization algorithm for training deepnets, and (ii) proving in the context of multinomial logistic regression that the ratio of outliers to bulk in the spectrum of the Fisher information matrix is predictive of misclassification.

MondayDec 30, 201911:15
Faculty SeminarSchmidt Auditorium
Speaker:Reviel NetzTitle:What have we Learned from the Archimedes Palimpsest?Abstract:opens in new windowin html    pdfopens in new windowNOTE THE UNUSUAL DAY AND PLACE

The rediscovery of the Archimedes Palimpsest in 1998 was a unique event: one of the most important authors of antiquity was read afresh, with many transformations made in the established text. Twenty years later, what have we learned from the Archimedes Palimpsest? What changed in our picture of the ancient history of mathematics?

Reviel Netz is Pat Suppes Professor of Greek Mathematics and Astronomy at Stanford University. Besides editing the Archimedes Palimpsest, he has published many books and articles on the history of Greek mathematics and on other subjects. His most recent book, "Scale, Space and Canon in Ancient Literary Culture", is now forthcoming from Cambridge University Press.

Refreshments will be served at 11:00am.

ThursdayDec 26, 201911:00
Faculty Seminar
Speaker:Ran Ben Basat Title:Leveraging Programmable Switches for In-network ComputingAbstract:opens in new windowin html    pdfopens in new window De Picciotto Building, Meeting Room 25

The network line rate is constantly on the rise to support the exploding amounts of data. This means that we have less time to process individual packets, despite a growing demand for better network telemetry. Moreover, CPU speeds are not rising at the same rate as we near the end of Moore's law, making it harder to rely on software computations. Programmable hardware switches are an emerging technology that enables flexible packet processing while optimizing for throughput and latency.

In this talk, I will introduce algorithms that leverage programmable switches for accelerating database operations and for improving network telemetry. Switches are orders of magnitude more efficient than traditional hardware accelerators, exist in the datapath, and are ideal for computation offloading. For telemetry, we will discuss how switches can probabilistically encode information across multiple packets to provide fine-grained network visibility with minimal overheads.

SundayDec 15, 201911:15
Faculty SeminarRoom 155
Speaker:Mor Nitzan Title:Representation, inference and design of multicellular systemsAbstract:opens in new windowin html    pdfopens in new window

The past decade has witnessed the emergence of single-cell technologies that measure the expression level of genes at a single-cell resolution. These developments have revolutionized our understanding of the rich heterogeneity, structure, and dynamics of cellular populations, by probing the states of millions of cells, and their change under different conditions or over time. However, in standard experiments, information about the spatial context of cells, along with additional layers of information they encode about their location along dynamic processes (e.g. cell cycle or differentiation trajectories), is either lost or not explicitly accessible. This poses a fundamental problem for elucidating collective tissue function and mechanisms of cell-to-cell communication.
In this talk I will present computational approaches for addressing these challenges, by learning interpretable representations of structure, context and design principles for multicellular systems from single-cell information. I will first describe how the locations of cells in their tissue of origin and the resulting spatial gene expression can be probabilistically inferred from single-cell information by a generalized optimal-transport optimization framework, that can flexibly incorporate prior biological assumptions or knowledge derived from experiments. Inference in this case is based on an organization principle for spatial gene expression, namely a structural correspondence between distances of cells in expression and physical space, which we hypothesized and supported for different tissues. We used this framework to spatially reconstruct diverse tissues and organisms, including the fly embryo, mammalian intestinal epithelium and cerebellum, and further inferred spatially informative genes. Since cells encode multiple layers of information, in addition to their spatial context, I will also discuss several approaches for the disentanglement of single-cell gene expression into distinct biological processes, based on ideas rooted in random matrix theory and manifold learning. I will finally discuss how these results can be generalized to reveal principles underlying self-organization of cells into multicellular structures, setting the foundation for the computationally-directed design of cell-to-cell interactions optimized for specific tissue structure or function.

SundayDec 01, 201911:15
Faculty SeminarRoom 155
Speaker:Ilya GekhtmanTitle:Gibbs measures vs. random walks in negative curvatureAbstract:opens in new windowin html    pdfopens in new window

The ideal boundary of a negatively curved manifold naturally carries two types of measures.
On the one hand, we have conditionals for equilibrium (Gibbs) states associated to Hoelder potentials; these include the Patterson-Sullivan measure and the Liouville measure. On the other hand, we have stationary measures coming from random walks on the fundamental group.
We compare and contrast these two classes.First, we show that both of these of these measures can be associated to geodesic flow invariant measures on the unit tangent bundle, with respect to which closed geodesics satisfy different equidistribution properties. Second, we show that the absolute continuity between a harmonic measure and a Gibbs measure is equivalent to a relation between entropy, (generalized) drift and critical exponent, generalizing previous formulas of Guivarc'h, Ledrappier, and Blachere-Haissinsky-Mathieu. This shows that if the manifold (or more generally, a CAT(-1) quotient) is geometrically finite but not convex cocompact, stationary measures are always singular with respect to Gibbs measures.

A major technical tool is a generalization of a deviation inequality due to Ancona saying the so called Green distance associated to the random walk is nearly additive along geodesics in the universal cover.
Part of this is based on joint work with Gerasimov-Potyagailo-Yang and part on joint work with Tiozzo.

SundayNov 24, 201911:15
Faculty SeminarRoom 155
Speaker: Arie Levit Title:On Benjamini-Schramm convergence Abstract:opens in new windowin html    pdfopens in new window

Benjamini-Schramm convergence is a probabilistic notion useful in studying the asymptotic behavior of sequences of metric spaces. The goal of this talk is to discuss this notion and some of its applications from various perspectives, e.g. for groups, graphs, hyperbolic manifolds and locally symmetric spaces, emphasizing the distinction between the hyperbolic rank-one case and the rigid high-rank case. Understanding the "sofic" part of the Benjamini-Schramm space, i.e. all limit points of "finitary" objects, will play an important role. From the group-theoretic perspective, I will talk about sofic groups, i.e. groups which admit a probabilistic finitary approximation, as well as a companion notion of permutation stability. Several results and open problems will also be discussed.

WednesdayNov 20, 201910:00
Faculty SeminarRoom 1
Speaker:Nir ShlezingerTitle:Exploiting Tasks, Structures, and AI in Digital Communications ReceiversAbstract:opens in new windowin html    pdfopens in new windowNOTE THE UNUSUAL DAY AND PLACE

The broad range of demands which next generation communications systems are required to meet, spanning from increased rates to efficient power consumption, cannot be satisfied by conventional architectures. These requirements give rise to a multitude of new challenges in modern communications and signal processing systems. In this talk we focus on two fundamental aspects of digital communications receivers - signal acquisition and symbol detection - discussing methods to improve their performance and reliability. For signal acquisition, we show how analog-to-digital convertors can be designed in light of the overall system task, achieving optimal-approaching performance while utilizing efficient bit-constrained samplers. Then, we discuss how recent advances in machine learning can be exploited for symbol detection, a task which is typically addressed using channel-model-based methods, such as the Viterbi algorithm and interference cancellation methods. We present a new framework for combining artificial intelligence and model-based algorithms, allowing the latter to be implemented in a data-driven manner. The resulting architectures are capable of approaching the established performance of model-based algorithms, while being invariant of the underlying statistical model, and learning it from a small amount of training samples.

SundayNov 17, 201911:15
Faculty SeminarRoom 155
Speaker:Sarah Keren Title:Automated Design of Better Environments for Intelligent AgentsAbstract:opens in new windowin html    pdfopens in new window

Automated agents and humans increasingly interact and collaborate: at home, at the workplace, on the road, and in many other everyday settings. In all these settings, effectively recognizing what users try to achieve, providing relevant assistance (or, depending on the application, taking relevant preventive measures), and supporting an effective collaboration in the system are essential tasks. All these tasks can be enhanced via efficient system redesign, and often even subtle changes can yield great benefits. However, since these systems are typically complex, hand crafting good design solutions is hard.

Utility Maximizing Design (UMD) addresses this challenge by automating the design process. It does so by offering informed search strategies to automatically and efficiently find optimal design solutions for maximizing a variety of targeted objectives. One example is Goal Recognition Design (GRD), which seeks a redesign to an environment that minimizes the maximal progress an agent can make before its goal is revealed. A second is Equi-Reward Utility Maximizing Design (ER-UMD), which seeks to maximize the performance of a planning agent in a stochastic environment. The third, Reinforcement Learning Design (RLD), parallels ER-UMD, but considers an environment with a reinforcement learning agent.

Among the different ways that may be available to change a setting, the talk will focus on information shaping, which consists of selectively revealing information to a partially informed agent in order to maximize its performance. As an example application, I will demonstrate how information shaping can be applied to enhance the performance of a robot that is navigating in an unfamiliar environment. The talk will conclude with a discussion of future extensions and various applications related to the agenda of Utility Maximizing Design, including human-robot collaboration, intrusion detection, and assisted cognition.