Colloquia and Seminars

In this talk we consider the following adversarial, non-Markovian, random walk on “good enough” expanders: Starting from some fixed vertex, walk according to the instructions X = X1,…,Xt, where each Xi is only somewhat close to having only little entropy, conditioned on any prefix. The Xi-s are not independent, meaning that the distribution of the next step depends not only on the walk’s current node, but also on the path it took to get there. We show that such walks (or certain variants of them) accumulate most of the entropy in X. We call such X-s “almost Chor–Goldreich (CG) Sources”, and our result gives deterministic condensers with constant entropy gap for such sources, which were not known to exist even for standard CG sources, and even for the weaker model of Santha–Vazirani sources. As a consequence, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a “one-shot” simulation is needed. Joint work with Dana Moshkovitz, Justin Oh, and David Zuckerman

The virtual memory subsystem translates the address of each memory reference from its virtual to its physical representation, increasing execution runtimes by as much as 50% and 90% in bare-metal and virtual setups, respectively. We alleviate these overheads by developing improved virtual memory designs: (i) hashed page tables and (ii) TLB partitioning for simultaneous multithreading. We additionally develop an efficient and reliable methodology for evaluating the performance of newly proposed virtual memory designs, replacing conventional full-system, cycle-level simulations with much faster partial simulations of only the virtual memory subsystem, whose outputs are fed into a mathematical model that predicts the execution runtime.

The increasing demand for data storage has prompted the exploration of new techniques, with molecular data storage being a promising alternative. The stored information can be represented as a collection of two-dimensional arrays, such that each row represents a DNA strand. In this work, we present the results of our research into error-correcting codes for molecular data storage using this representation. Although both insertions and deletions have been observed to occur, the focus of our work is deletions, that can be caused by a failure of the bit addition chemistry. On top of this, cells can be lost either partially, which occurs when a defective bit prematurely terminates the chain, or the data within a cell can be corrupted completely. Initial experiments have reported error rates as high as 10%. Those errors can be considered as erasures in the last few symbols. Our study focuses on correcting those erasures and also deletions across rows. We present code constructions and explicit encoders that are shown to be nearly optimal in many scenarios, using bounds we derived. The first construction is based on permuting the columns of a chosen parity check matrix, such that the set of linearly independent columns match the pattern of possible erasures, that is at most a known parameter $d$ of tail-erasures. This construction is optimal for $d=2,3,4$ and nearly optimal for any $d=2t+1$. To design the above code properly, our work introduces a new distance metric, with properties similar to the Hamming distance, but which is better suited for the tail-erasure model. The second construction uses Tensor Product codes (TPC), that underlies Varshamov-Tenengolts (VT) codes to correct $t$ rows that suffer from one deletion each, where $t$ is a parameter. In the last construction we combine the two problems, to construct a code that can correct both tail-erasures and one deletion in $t$ rows. To conclude, as a concrete example, we mention Iridia, a San Diego-based startup, that has developed a new storage method using a two-dimensional arrays, for which our work suggests a suitable solutions. Our findings show that the new coding schemes are capable of effectively mitigating these errors, making Iridia's system a promising solution for DNA data storage.

Substantial efforts have been devoted into improving the capabilities of neural networks to solve algorithmic tasks. Through training, these networks learn to mimic algorithmic behaviour, enabling them to handle tasks such as sorting, navigating, and managing complex data structures like graphs. However, classic algorithms and neural networks are fundamentally different, making it challenging to analyze the complexity of an algorithm learned by a neural network. First, it is necessary to establish that the model has indeed learned an abstract solution resembling algorithmic behaviour. Additionally, while the complexity of classic algorithms is measured asymptotically, the complexity of an algorithm learned by a neural network must be measured within the finite input space supported by the model. This evaluation should also factor into consideration potential degradation in the model’s accuracy on unseen data. To this end, we will discuss these challenges and their implications, and propose methods for measuring the complexity of algorithms learned by neural networks. Finally, we will present experimental results on graph problems.

Mobile robotic agents often suffer from localization uncertainty which grows with time and with the agents' movement. This can hinder their ability to accomplish their task. In some settings, it may be possible to perform assistive actions that reduce uncertainty about a robot’s location. Since assistance may be costly and limited, and may be requested by different members of a team, there is a need for principled ways to support the decision of which assistance to provide to an agent and when, as well as to decide which agent to help within a team. For this purpose, we propose Value of Assistance (VOA) to represent the expected cost reduction that assistance will yield at a given point of execution. We offer a way to compute VOA based on an estimation of the robot's future uncertainty, modeled as a Gaussian process. We specify conditions under which our VOA measure is valid, and empirically demonstrate the ability of our measure to predict the agent's average cost reduction when receiving assistance in both simulated and real-world robotic settings.

Levenshtein's reconstruction model was first introduced in 2001 and suggests transmitting a word over multiple noisy channels, then using the channels' outputs to recover the transmitted word. This talk will discuss the reconstruction model when the channels are prone to combinations of errors, or when unique retrieval of the transmitted word is not guaranteed to succeed. In particular, when the channels introduce a limited number of insertions (or deletions), and unique decoding is not guaranteed to succeed, bounds on the largest list size will be presented. Furthermore, a recently proposed optimization to DNA synthesis using shortmers (i.e., sequences of bases) will be investigated from a theoretical point of view. This optimization differs from the conventional synthesis process by appending in each cycle not only single bases, but also shortmers. The significance of this optimization lies in reducing the number of cycles, which then determines the time and monetary cost of the synthesis process. Hence, the talk will discuss several questions pertaining to this optimization, such as which shortmers to use and how to calculate the minimum number of cycles.

When users can benefit from certain predictive outcomes, they may be prone to act to achieve those outcome, e.g., by strategically modifying their features. The goal in strategic classification is therefore to train predictive models that are robust to such behavior. However, the conventional framework assumes that changing features does not change actual outcomes, which depicts users as "gaming" the system. Here we remove this assumption, and study learning in a causal strategic setting where true outcomes do change. Focusing on accuracy as our primary objective, we show how strategic behavior and causal effects underlie two complementing forms of distribution shift. We characterize these shifts, and propose a learning algorithm that balances between these two forces and over time, and permits end-to-end training. Experiments on synthetic and semi-synthetic data demonstrate the utility of our approach.

CS Special Guest Lecture by Prof. Avi Wigderson, IAS Princeton, on the Occasion of his Being Awarded an Honorary Doctorate from the Technion Recently, a group of theoretical computer scientists posted a paper on the Arxiv with the strange-looking title "MIP* = RE", surprising and impacting not only complexity theory but also some areas of math and physics. Specifically, it resolved, in the negative, the "Connes' embedding conjecture" in the area of von-Neumann algebras, and the "Tsirelson problem" in quantum information theory. It further connects Turing's seminal 1936 paper which defined algorithms to Einstein's 1935 paper with Podolsky and Rosen which challenged quantum mechanics. As it happens, both acronyms MIP* and RE represent proof systems, of a very different nature. To explain them, we'll take a meandering journey through the classical and modern definitions of proof. I hope to explain how the methodology of computational complexity theory, especially modelling and classification (of both problems and proofs) by algorithmic efficiency, naturally leads to the generation of new such notions and results (and more acronyms, like NP). A special focus will be on notions of proof which allow interaction, randomness, and errors, and their surprising power and magical properties. The talk does not require special mathematical background.

Terrain-aided navigation (TAN) was developed before the GPS era to prevent the error growth of inertial navigation. TAN algorithms were initially developed to exploit altitude over ground or clearance measurements from a radar altimeter in combination with a Digital Terrain Map (DTM). After almost two decades of silence, the availability of inexpensive cameras and computational power and the need to find efficient GPS-denied positioning solutions have prompted a renewed interest in this solution. However, vision-based TAN is more challenging in many aspects than the original one, as visual observables can only provide a range up to a scale, preventing a straightforward extension of classical TAN techniques. The main contributions of this work are the introduction of a new, more flexible, and efficient algorithm for solving the visual-assisted TAN. The algorithm combines two fast stages for solving the problem. In addition, a new outlier-rejection step is introduced between the two stages to make the algorithm robust and suitable for real-world data.

Over the course of four decades, the academic field of computer science transformed from a branch of mathematics to a key driver of the evolution of our species. Graduates of academic computer science programs today routinely create systems that would have been considered, just a century ago, miracles of mythic proportions. Judging by cultural impact, computer science departments today resemble Hogwarts much more than they resemble the theoretical havens they used to be before computers got seriously strong. Interestingly, at their core, computer science BSc programs have not changed that much since the 1990's. If indeed with great power comes great responsibility, then it is now incumbent on academic computer science departments to prepare the young witches and wizards, who train in CS, to use their digital powers responsibly - whatever this may mean. Needless to say, almost nothing in the academic computer science literature offers any clues on how to go about this. On the contrary, computer science - like all science and technology - detaches technique from its human impact, focuses almost exclusively on problem solving, and tends to view the world through a narrow quantitative lens. Questions of human impact are typically labelled under the obscure term "ethics" and deferred wholesale to the social sciences and humanities. Clear basic guidelines for individual choices, analogous to those of the medical and life sciences, still seem lightyears ahead. I will argue that academic computer science departments offer the perfect environment to be asking these questions - as Joseph Weizenbaum and Norbert Wiener passionately prophesied at the onset of the digital age - and that it may be our solemn duty to do so. I'll share some experiences from teaching an undergraduate CS class in Hebrew University, which looked for meaningful ways to form a personal perspective on the broader implications of digital information technology. Short Bio: Matan Gavish is an Associate Professor in the Hebrew University School of Computer Science and Engineering. He is the founder of the Israel-Singapore center for AI-based urban agriculture (iSURF), and of the Hebrew University joint CS-Statistics BSc program in Data Science. His research interests include statistical learning, mathematical statistics of spectral algorithms in high dimensions, applied harmonic analysis, random matrix theory, empirical mathematics, reproducible research, data-driven precision agriculture, digital communication studies, and philosophy of technology. Matan received the dual B.Sc. degree in Mathematics and Physics from Tel Aviv University in 2006, the M.Sc. degree in Mathematics from the Hebrew University of Jerusalem in 2008 and the Ph.D. degree in Statistics from Stanford University in 2014.

DNA labeling is a powerful tool in molecular biology and biotechnology that allows for the visualization, detection, and study of DNA at the molecular level. Under this paradigm, a DNA molecule is being labeled by specific k patterns and is then imaged. Then, the resulted image is modeled as a (k + 1)-ary sequence in which any non-zero symbol indicates on the appearance of the corresponding label in the DNA molecule. The primary goal of this work is to study the labeling capacity, which is defined as the maximal information rate that can be obtained using this labeling process. The labeling capacity is computed for any single label and several results are provided for multiple labels as well. Moreover, we provide the optimal minimal number of labels of length one or two that are needed in order to gain labeling capacity of 2.