Title
| When
| Abstract
|
Recent developments in intersection searching
By: Esther
Ezra, BIU
Host: Natan
Rubin
| May 23, 2023
12:00-13:00
Bldg.37, room 202
| Recently, polynomial partitioning became a central tool in solving fundamental algorithmic problems in computational geometry, including eliminating depth cycles, point location, and semi-algebraic range searching. In this talk I will present several recent developments in the study of intersection searching - a family of range searching problems. I will first describe a solution to the ray-shooting problem amid triangles in 3-space, where polynomial partitioning serves as a main tool in order to obtain an efficient data structure supporting ray-shooting queries. Then, I will show an extension of this approach, resulting in efficient data structures for detecting intersections amid flat objects in 3-space and semi-algebraic arcs. These data structures rely on efficient constructions of polynomial partitioning, I will sketch such constructions and discuss their importance. Bio: Esther Ezra is currently an associate professor at the Computer Science department in Bar-Ilan university. Before joining Bar-Ilan, she was an assistant professor at the School of Math in Georgia Institute of Technology. She completed her PhD from Tel-Aviv university, and then continued her postdoctoral research in Duke university and later in NYU. Her research interests lie the area of discrete and computational geometry, in particular, her current work is focused on algebraic methods and their applications to point location and range searching. Her research also contains aspects from learning theory, probabilistic methods and discrepancy and how to apply them in geometric settings.
|
Local Glivenko-Cantelli (or: estimating the mean in infinite dimensions)
By: Aryeh
Kontorovich, BGU
| May 16, 2023
12:00-13:00
Bldg.37, room 202
>>>Zoom Link | If μ is a distribution over the d-dimensional Boolean cube {0,1}d, our goal is to estimate its mean p∈[0,1]d based on n iid draws from μ. Specifically, we consider the empirical mean estimator p̂n and study the maximal deviation M=maxj∈[d]| p̂n(j)-p(j)|. In the classical Universal Glivenko-Cantelli setting, we seek distribution-free (i.e., independent of μ) bounds on M. This regime is well-understood: for all μ, we have 𝔼[M]≲√log(d)/n up to universal constants, and the bound is tight. Our present work seeks to establish dimension-free (i.e., without an explicit dependence on d) estimates on M, including those that hold for d=∞. As such bounds must necessarily depend on μ, we refer to this regime as Local Glivenko-Cantelli, and are aware of very few previous bounds of this type — which are quite sub-optimal. Already the special case of product measures μ is quite non-trivial. We give necessary and sufficient conditions on μ for 𝔼[M]→0, and discover a novel sub-Gamma-type maximal inequality for shifted Bernoullis. A number of challenging open problems are posed for future research. Joint work with Doron Cohen. https://arxiv.org/abs/2209.04054 Bio: Aryeh Kontorovich received his undergraduate degree in mathematics with a certificate in applied mathematics from Princeton University in 2001. His M.Sc. and Ph.D. are from Carnegie Mellon University, where he graduated in 2007. After a postdoctoral fellowship at the Weizmann Institute of Science, he joined the Computer Science department at Ben-Gurion University of the Negev in 2009, where he is currently a full professor. His research interests are mainly in machine learning, with a focus on probability, statistics, Markov chains, and metric spaces.He served as the director of the Ben-Gurion University Data Science Research Center during 2021-2022.
|
A solution to Ringel's 1959 circle problem
By: Chaya
Keller,
Ariel University
Host: Natan
Rubin
| May 2, 2023
12:00-13:00
Bldg.37, room 202
| In 1959, Gerhard Ringel posed the following problem: What is the maximal number of colors needed for coloring any collection of circles, no three tangent at a point, such that any two tangent circles get different colors? The special case where the circles are non-overlapping was shown long ago to be equivalent to the celebrated 4-color theorem. The general case has remained open; it was only known that 4 colors are not sufficient. In this talk we show that no finite number of colors can suffice, by constructing collections of circles whose tangency graphs have an arbitrarily large girth (so in particular, no three are tangent at a point) and an arbitrarily large chromatic number. Our construction, which is one of the first geometric constructions of graphs with a large girth and a large chromatic number, relies on a (multidimensional) version of Gallai's theorem with polynomial constraints, which may be of independent interest. Joint work with James Davies, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak. Brief bio: Chaya Keller is a Senior Lecturer at the School of Computer Science, Ariel University. Her research field is discrete and computational geometry, with a focus on convexity and on coloring problems in geometric graphs and hypergraphs. She won a number of awards, including the Arianne de Rothschild fellowship, the Hoffman fellowship and the Noriko Sakurai award. On the Ringel Problem: https://gilkalai.wordpress.com/2021/12/11/to-cheer-you-up-in-difficult-times-34-ringel-circle-problem-solved-by-james-davies-chaya-keller-linda-kleist-shakhar-smorodinsky-and-bartosz-walczak/
|
Everything you always wanted
to know about Cardinality Estimation* (*but were afraid to ask)
By: Seth Pettie, University of
Michigan, Ann Arbor
Host: Aryeh Kontorovich
| April 18, 2023
12:00-13:00
Bldg.37, room 202
>>>Zoom link
| The Cardinality Estimation/Distinct Elements problem is to approximate the number of distinct elements in a data stream using a small probabilistic data structure called a "sketch". This problem has been studied for 40 years, has many industrial applications, and is featured prominently in most courses on Big Data algorithmics. It is therefore a real puzzle to explain why research on this popular and fundamental problem has been unusually slow.
This talk presents a complete history of the Cardinality Estimation problem from Flajolet and Martin's seminal 1983 paper to the present, and includes an account of how the research community became fractured, delaying many natural developments by decades. I will present our recent efforts to achieve information-theoretically optimal cardinality sketches, which draws on two notions of "information" developed in the 20th century: Fisher information (governing optimal point estimation) and Shannon entropy (governing optimal space/communication).
Joint work with Dingyu Wang:
(STOC 2021) https://arxiv.org/abs/2007.08051
(ICALP 2021) https://arxiv.org/abs/2008.08739
(PODS 2023) https://arxiv.org/abs/2208.10578 Short Bio: Seth Pettie is a Professor of Computer Science and Engineering at the University of Michigan. He received his Ph.D. from UT-Austin in 2003, and was an Alexander von Humboldt Fellow at the Max Planck Institute for Computer Science from 2003-2006. He has held Visiting Professor positions at Aarhus University (2013-14) and Bar-Ilan University (2023). |
The polynomial technique in geometry: Combinatorial past and algorithmic present
By: Micha
Sharir,
Tel-Aviv University
Host: Natan
Rubin
| March 26, 2023
12:00-13:00
Bldg.37, room 202
>>>Zoom link
| We review the "algebraic revolution" in combinatorial and computational geometry, initiated by Guth and Katz, who obtained in a groundbreaking paper in 2010 an almost complete solution of Erdos' distinct distances problem, introducing the new powerful technique of polynomial partitioning. This technique changed the landscape of the field, by facilitating a solution of a large number of difficult problems, which, before the revolution, were deemed too difficult to "solve in our lifetime". These problems involve distinct distances, incidences between points and lines, curves or surfaces in three and higher dimensions, and many other hard problems in combinatorial geometry. Algorithmic applications of the technique were slower to materialize, but major advances on this front took place during the past five years, mainly for range searching with semi-algebraic sets and its diverse applications. The talk will attempt to highlight the major achievements of the technique to date, both combinatorial and algorithmic. Short Bio: https://en.m.wikipedia.org/wiki/Micha_Sharir Micha Sharir received his Ph.D. in Mathematics from Tel Aviv University in 1976, and then switched to Computer Science, doing his postdoctoral studies at the Courant Institute of New York University. Micha is one of the co-founders of the Minerva Center for Geometry at Tel Aviv University. His research interests are in computational and combinatorial geometry and their applications. He has pioneered (with Jack Schwartz) the study of algorithmic motion planning in robotics during the early 1980s, and has been involved in many fundamental research studies that have helped to shape the fields of computational and combinatorial geometry. Among his major achievements, in addition to his earlier work on robotics, are the study of Davenport-Schinzel sequences and their numerous geometric applications, the study of geometric arrangements and their applications, efficient algorithms in geometric optimization (including the introduction and analysis of generalized linear programming), and the study of combinatorial problems involving point configurations, including, since 2008, the application of algebraic techniques to problems involving incidences, distinct and repeated distances, and other related problems in combinatorial and computational geometry. His work won him several prizes, including a Max-Planck research prize (1992, jointly with Emo Welzl), the Feher Prize (1999), the Mif'al Hapais' Landau Prize (2002), and the EMET Prize (2007). He is the incumbent of the Nizri Chair in computational geometry and robotics, a Fellow of the Association for Computing Machinery (since 1997), has an honorary doctorate degree from the University of Utrecht (1996), and is a member of the Israeli Academy of Sciences and Humanities (2018). He has supervised 27 Ph.D. students, many of which are now at various stages of an academic career, in Israel and abroad.
|
Cryptanalysis, via
discrete Fourier analysis
By: Nathan Keller, Bar-Ilan University
Host: Natan Rubin
| March 21, 2023
12:00-13:00
Bldg.37, room 202
>>>Zoom link
| Cryptanalysis studies
the practical security of the encryption schemes we use. The central object in
cryptanalysis is "attack techniques" – which are algorithms that
allow an adversary to intercept communications, forge digital signatures, etc.
While the discovered attack techniques have been very successful, and have
allowed discarding insecure encryption schemes and developing strategies for
better designs, their analysis has always been somewhat ad-hoc. For most of the
techniques, we don't know whether they are optimal, and for some, we don't even
know how to estimate their complexity well.
In this talk we propose a new approach to understanding cryptanalytic attacks,
using seemingly unrelated techniques from discrete Fourier analysis. We will
show that Fourier-analytic techniques can be helpful in addressing core
questions, such as: "Can we prove that certain cryptanalytic attacks are
optimal?" and "Is there a need for post-quantum secret-key
cryptosystems?". We will mostly concentrate on open questions, but
will also show promising results following the new approach.
Joint work with Itai Dinur and Ohad Klein
|
Shortest paths over random sampled points and their
applications to information theory, entropy, manifold learning and high
dimensional data analysis
By: Steven
Damelin, U. Michigan
Host: Aryeh Kontorovich
| Jan 17, 2023
12:00-13:00
Bldg.37, room 202
>>>Zoom link | The shortest path problem is of interest both in theory and in applications since it naturally arises in combinatorial optimization problems, such as optimal routing in communication networks, information theory, entropy, and high dimensional data analysis for example in manifold learning.
Many graph structures over Euclidean sample points have been studied in the context of the Beardwood-Halton-Hammersley (BHH) theorem and its extensions. The BHH theorem states that the law of large numbers (LLN) holds for certain spanning graphs over random samples. Such graph structures include the travelling salesman path (TSP), the minimal spanning tree (MST), and the nearest neighbor graphs.In this talk, we will discuss shortest paths over random sample points embedded in Euclidean and Riemannian spaces as well as the use of power weighted shortest path distance functions for clustering high dimensional Euclidean data, under the assumption that the data is drawn from a collection of disjoint low dimensional manifolds. We will discuss connections of our work to information theory, entropy and manifold learning. This is joint work with Alfred Hero (University of Michigan), Sung Jin Wang (Google) and Daniel McKenzie (Colorado School of Mines).
Bio: Steve Damelin, completed his Ph.D under Doron Lubinsky, now at Georgia Tech where he solved several open problems in weighted polynomial approximation related in part to work of Paul Erdos. He has written 79 research papers, two books, the first published by Cambridge University Press and his second which will be published by John Wiley & Sons. He has edited two volumes. His research interests are both pure and interdisciplinary and include, approximation theory, signal processing, manifold learning, vision, shortest paths and information theory, optimal transport, harmonic analysis and mathematics education. His research papers have appeared in journals at the level of the Annals of Applied Probability. His honors include a New Directions Professorship (only two awarded internationally per year) at the Institute for Mathematics and its Applications, University of Minnesota. He has held faculty and visiting positions at numerous academic institutions both in the United States and abroad including Penn State University, American Mathematical Society, Georgia Southern University and University of Minnesota. His work has been funded by many international funding agencies including National Science Foundation, the United States Department of Defense and the British EPRSC. His work constantly promotes diversity for example in a large Center for High Computing flagship award for the University of the Witwatersrand, South Africa. He has worked with many research students and with over 30 research collaborators both in the United States and abroad, for example in Stanford, Israel and Germany. He currently is affiliated to the University of Michigan and lives in Ann Arbor Michigan, the United States.
|
On structure and performance in the era of (really) big data
By: Amit Levi, Huawei Noah's ark lab in Toronto
Host: Jonathan Mosheiff | Jan 16, 2023
12:00-13:00
Bldg.37, room 202
>>>Zoom link
| The influx of data witnessed during the last decade gave rise to groundbreaking applications in data sciences and machine learning. However, due to hardware constraints, the volume of data grows much faster than the growth of the available computational resources. Such modern setting poses new challenges for algorithm design as more efficient methods are needed. One way to obtain such methods is by exploiting the underlying structure of the data.
In this talk, we will discuss three examples, ranging from theory to practice, where structure can be leveraged to obtain performance. The first two examples are from sublinear computation, where the combinatorial/geometric structure of the data is used to obtain dramatic time and space savings, and the third coming from Graph Neural Networks, where local structure is exploited to obtain superior real-world models.
Bio: Amit Levi is a research scientist at Huawei Noah's ark lab in Toronto. He obtained his PhD from the University of Waterloo, where he was advised by Eric Blais. He is interested in developing a rigorous understanding of the interplay between structured data and performance of algorithms, with a particular focus on sub-linear computation and graph neural networks.
|
The
Interconnection Between Approximation, Optimization and Generalization in Deep
Learning Theory.
By: Itay
Safran,
Purdue University
Host: Aryeh
Kontorovich
| Jan 10, 2023
12:00-13:00
Bldg.37, room 202
>>>Zoom link
| The modern study of deep learning theory can be crudely partitioned into three major aspects: Approximation, which is concerned with the ability of a given neural network architecture to approximate various objective functions; optimization, which deals with when we can or cannot guarantee that a certain optimization algorithm will converge to a network with small empirical loss; and generalization, which asks how well the network we trained is able to generalize to previously unseen examples. Despite being studied independently for the most part, we will demonstrate how considering all aspects simultaneously gives rise to end-to-end learnability results, which will establish a rich interconnection between the three aspects. This highlights the importance of studying the individual pieces as a whole to better understand the bigger picture, and to improve our theoretical understanding of the unprecedented practical success of deep learning.
Bio: Itay Safran is a Post-Doctoral Research Associate at Purdue University, and a former Postdoctoral Research Fellow at Princeton University. He received his MSc and PhD from the Weizmann Institute of Science, and a dual BSc in mathematics and computer science from Ben-Gurion University of the Negev. Itay's research focuses on theoretical machine learning, with emphasis on the theory of deep learning. For his achievements, he was recognized with the Dan David Scholarship Prize for outstanding doctoral students of exceptional promise in the field of artificial intelligence, and an excellence postdoctoral scholarship awarded by the Council for Higher Education in Israel to highly distinguished PhDs in data science fields.
|
Complexity-Performance
Tradeoffs in Mechanism Design
By: Moshe Babaioff, Microsoft Research
Host: Klim Efremenko
| Jan 3, 2023
12:00-13:00
Bldg.37, room 202
>>>Zoom link
| Online computational platforms that directly engage with users must account for the strategic behavior of self-interested individuals. The goal of mechanism design is to optimize an objective, such as efficiency or revenue, in such scenarios, i.e., when the agents that participate in the mechanisms act strategically. In many fundamental computational settings the theoretical optimal mechanisms are highly complex and thus are not practical. In this talk I will discuss the tradeoff between the complexity of mechanisms and their performance, illustrated on the fundamental problem of profit maximization when selling multiple goods. Optimal mechanisms for this problem are highly complex. Nevertheless, I will present a simple deterministic mechanism that guarantees a constant percentage of the optimal revenue. I will then present results regarding the complexity of mechanisms that are almost optimal, and regarding the tradeoff between performance and complexity for this problem.
Bio: Moshe Babaioff is a Senior Principal Researcher at Microsoft Research, located in Israel. His research focuses on establishing rigorous theoretical foundations of solutions to real-world problems in the intersection of Economics and Computation (EC), using tools and approaches from Computer Science, Game Theory, and Microeconomic Theory. Moshe has served on multiple leadership positions at the EC community, including serving as Program co-Chair of ACM-EC 2017, as General Chair of ACM-EC 2014, and as co-chair of the Economics, Monetization, and Online Markets Track of The Web Conference (2023). Moshe has been at Microsoft Research (MSR) for 15 years, first at MSR Silicon Valley lab (2007-2014) and then at MSR in Israel (since 2014). Before joining MSR he was a postdoctoral scholar at the University of California, Berkeley. He received his PhD in Computer Science from the Hebrew University in Jerusalem.
|
Data Tools for Accelerated
Scientific Discoveries
By: Brit Youngmann, MIT
Host: Yuval
Moskovitch
| Dec 27, 2022
12:00-13:00
Bldg.37, room 202
>>>Zoom link
| 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. Bio: Brit is a postdoc researcher at CSAIL MIT, working with Prof. Michael Cafarella. She received her Ph.D. at Tel-Aviv University under the supervision of Prof. Tova Milo. Her research is centered around informative and responsible data science and causal analysis. Brit is the recipient of several awards, including the data science fellowship for outstanding Ph.D. students of the planning and budgeting committee of the Israeli council for higher education (VATAT), the Schmidt postdoctoral award for women in mathematical and computing sciences, and the planning and budgeting committee of the Israeli council for higher education (VATAT) postdoctoral scholarship in Data Science. She served on multiple program committees, including at the SIGMOD and ICDE conferences.
|
Experiment Design and Evaluation of Empirical Models in Natural Language Processing
By: Rotem Dror, UPENN
Host: Michael Elhadad
| Dec 20, 2022
12:00-13:00
Bldg.37, room 202
>>>Zoom link | The research field of Natural Language Processing (NLP) puts a lot of emphasis on empirical results. It seems that models are reaching state-of-the-art and even “super-human" performance on language understanding tasks on a daily basis, thanks to large datasets and powerful models with billions of parameters. However, the existing evaluation methodologies are lacking in rigor, leaving the field susceptible to erroneous claims. In this talk, I will describe efforts to build a solid framework for evaluation and experiment design for diverse NLP tasks. To begin, I describe how NLP researchers currently conduct experiments and measure model performance, highlighting some important limitations. I will present our work, in which we propose statistical analyses for comparing models that allow researchers to make credible and statistically valid claims in many experimental settings in NLP, such as experimenting with deep neural network models or reporting model performance across multiple languages. Then, I will discuss challenges related to evaluating text-generation tasks, such as machine translation or automatic summarization. Evaluation of text-generation models is not straightforward because different texts can convey the same meaning. Therefore, comparing a model's output with a human-written reference may not reflect the true quality of the output. Researchers have designed metrics to automatically evaluate text-generation systems. However, none of them measures all of the aspects we wish to evaluate. Therefore, I will propose methods for estimating the quality of these evaluation metrics and introduce limitations for a certain type of evaluation technique known as reference-free. Finally, I will discuss future research directions and challenges in estimating the true performance of NLP models. This talk is based on papers published in TACL (2017, 2021), ACL (2018, 2019), NAACL 2022, EMNLP 2022, and a book published by Morgan and Claypool Publishers in 2020. Bio: Rotem Dror is a postdoctoral researcher at the University of Pennsylvania Cognitive Computation Group, mentored by Prof. Dan Roth. She received her Ph.D. from the Technion - Israel Institute of Technology, where she was advised by Prof. Roi Reichart. With a focus on Natural Language Processing applications, her research involves developing statistically sound methodologies for empirical investigation and evaluation.
|
SQL and Incomplete Information
By: Liat Peterfreund, The French National Centre for Scientific Research (CNRS)
Host: Yuval Moskovitch
| Dec 19, 2022
12:00-13:00
Bldg.37, room 202
>>>Zoom link
| Handling incomplete information is a subject of key importance in databases, and the way it is handled in commercial database management systems has many well-known deficiencies. A key reason for that is a flaw in the design of SQL, the de-facto standard query language for relational databases. Instead of using the familiar two-valued Boolean logic, SQL reverts to three-valued logic with an additional truth value “unknown" to handle incomplete data. While being viewed as indispensable for SQL, this design decision has been criticized for leading to unintuitive behavior and being a source of programmers' mistakes.
In this talk, I will explain that, contrary to the widely held view, SQL could have been designed based on Boolean logic, without any loss of expressiveness and without giving up nulls (representing missing values). This applies to the core of the language including all of its key features (the 1999 SQL standard). I will also explain how this new version of SQL leads to better optimizations and more intuitive query results, which is further confirmed by a user study. I will conclude by discussing the possible impact on the design of new query languages and on the interaction with the standards committee, and by presenting a new direction of theoretical research on incomplete information that is better suitable for SQL analytical queries. The talk is partly based on joint work with Leonid Libkin and will be presented in PODS 2023. Bio: Liat Peterfreund is a permanent CNRS researcher (chargée de recherche) at University Gustave-Eiffel, Paris. Prior to that, she was a postdoctoral scholar at École Normale Supérieure (ENS) Paris and Edinburgh University hosted by Prof. Leonid Libkin. She obtained her PhD at the Technion in 2019 under the supervision of Prof. Benny Kimelfeld. Her research is mainly on the foundations of data management. During her PhD she has been working on algorithms for text-centric databases. Recently, she has been working mainly on the standardization and formal semantics of query languages, and on different aspects of handling incomplete information.
|
An Algorithmic Perspective to Collective Behavior
By: Amos Korman, The French National Centre for Scientific Research (CNRS) Host: Natan Rubin
| Dec 13, 2022
12:00-13:00
Bldg.37, room 202
| In this talk, I will present a new interdisciplinary approach that I have been developing in recent years, aiming to build a bridge between the fields of algorithm theory and collective (animal) behavior. Ideally, an algorithmic perspective on biological phenomena can provide a level of fundamental understanding that is difficult to achieve using typical computational tools employed in this area of research (e.g., differential equations or computer simulations). In turn, this fundamental understanding can provide both qualitative and quantitative predictions that can guide biological research in unconventional directions. I will demonstrate this novel approach by presenting a sequence of works on collective ant navigation (published in the biology journals eLife 2016 and eLife 2020, and the CS venues ESA 2018 and TALG 2021), whose experimental part was done in collaboration with the Feinerman ant lab at the Weizmann Institute. In the second part of the talk, I will present a recent result (published in Science Advances 2021) regarding the search efficiency of common animal movement patterns, addressing a long-standing open problem in the area of foraging. I will conclude the talk by discussing potential avenues to employ an algorithmic perspective in biological contexts.
Bio: Amos Korman received his Ph.D. in computer science at the Weizmann Institute of Science in May 2006, under the guidance of David Peleg. His Ph.D. thesis won Dean's prize for Ph.D. students. He then continued for two years of postdoc at the Technion and has been a researcher at CNRS, France, since Nov. 2007. In 2015 Amos received his Habilitation and in 2017 he was promoted to the rank "Directeur de Recherche". Until 2014 Amos worked primarily in the areas of distributed computing and graph algorithms. Around that time, he made a shift in his research focus, aiming to study biological phenomena through an algorithmic perspective. To support this pioneering initiative Amos received an ERC Consolidator Grant that lasted during the years 2015 - 2021. In 2020 Amos received the SIROCCO Prize for Innovation in Distributed Computing. As mentioned in the laudatio, the award was given for "pioneering contributions to distributed computing methods for system biology''.
|
Recovering Data Semantics
By: Roee Shraga, Northeastern University
Host: Gil Einziger
| Dec 6, 2022
12:00-13:00
Bldg. 37, room 202
>>>Zoom link
| In data science, it is increasingly the case that the main challenge is finding, curating, and understanding the data that is available to solve a problem at hand. Furthermore, modern-day data is challenging in that it lacks many forms of semantics ("meaning of data"). Metadata may be incomplete or unreliable, data sources are unknown, and data documentation rarely exists. To address these challenges, the objective of my research is to recover data semantics throughout data discovery, versioning, integration, and quality. In this talk, I will discuss current data science challenges and highlight two specific aspects of my research that assist with such challenges. In particular, I will present ALITE, the first scalable integration solution for tables that may have been discovered in data lakes (repositories of big data). ALITE relaxes previous assumptions that tables share common attribute names (which completely determine the join columns), are complete (without null values), and have acyclic join patterns. I will also introduce Explain-Da-V, a solution that explains dataset versions by generating data transformations that resolve data changes. Bio: Roee Shraga is a Postdoctoral fellow at the Khoury College of Computer Science at Northeastern University in Boston. He received his PhD degree in 2020 from the Technion in the area of Data Science. Roee has published more than a dozen papers in leading journals and conferences on the topics of data integration, human-in-the-loop, machine learning, process mining, and information retrieval. He is a recipient of the Council for Higher Education [VATAT] scholarship for outstanding data science postdocs. He is also a recipient of several PhD fellowships including the Leonard and Diane Sherman Interdisciplinary Fellowship (2017), the Daniel Excellence Scholarship (2019), and the Miriam and Aaron Gutwirth Memorial Fellowship (2020).
|
Coresets for Computer Vision with Robotics Applications
By: Dan
Feldman, The
Robotics & Big Data Labs, Computer Science Department, University of Haifa
Host: Natan Rubin
| Nov 22, 2022
12:00-13:00
Bldg. 37, room 202
>>>Zoom link
| A fundamental problem in robotics is to localize a robot in the real-world using only a monocular 2D RGB camera. Here, localization means 6 degrees of freedom: x,y,z-axes and rotations around them. Our group suggested the first solution with provable guarantees that can be applied in real-time on a very weak and lightweight micro-computer (RPI0, <5 grams, <$6). The motivation was to provide the first autonomous nano-drone of weight <100 grams, but we also used it for smart carts, and flying ads in the supermarket of Rami-Levi (near the lab). The main theoretical challenge was to provide the first provable approximation for the Perspective-n-Point problem: Compute a rotation and translation of a set of n points (in the 3d world) that minimize their sum of distances to n paired lines (2D pixels with missing depth). This is by proving that there is always a small subset of pairs (called core-set) that yields such an approximation and can be computed in O(n) time. Based on papers with my awesome students: - International Conference on Intelligence Robots and Systems (IROS'22), with Ibrahim Jubran, Fares Fares, Yuval Alfassi, and Firas Ayoub.
- International Conference on Computer Vision (ICCV'21), with Ibrahim Jubran and Alaa Maalouf. Bio: https://www.rbd-labs.com |
Methods
for Computer-Assisted Linearizability Verification of Implementations of
Concurrent Data Structures
Presenter: Avi Hayoun
Advisors: Uri Abraham and Gera
Weiss | Nov 20, 2022
14:00-15:00
Bldg. 37, room 201
>>>Zoom link | Since distributed implementations of data
structures are at the core of critical software, verification of these
implementations is needed. A central challenge in this is that verifying the
correctness of concurrent software is difficult, requiring a mathematical
background not usually available to engineers, not even to experts in
verification technologies. This talk will focus on the practicality of
verifying and validating the correctness of implementations of concurrent
objects, presenting two orthogonal approaches. First, practical and efficient
techniques for verifying and validating concurrent implementations of the
fundamental snapshot object. Second, a structured approach to proving the
correctness of concurrent binary-search trees, which do not fit the methodology
in our first approach.
|
Learning
to Route Under Demand Uncertainty
By: Michael
Shapira, Rachel and Selim Benin School of Computer Science and Engineering, the
Hebrew University of Jerusalem
Host: Natan
Rubin
| Nov 8, 2022
12:00-13:00
Bldg. 37, room 202
>>>Zoom link
| Routing in the presence of uncertainty about future traffic is a fact of life in many operational environments.Today, this challenge is typically addressed by attempting to predict future traffic demands and optimizing with respect to these. However, as we explain, this might give rise to both far-from-optimal routing and prohibitively expensive optimization runtimes. We explore an alternate approach to this fundamental challenge: directly learning high-performance routing via stochastic optimization. We exemplify the usefulness of our approach through the important use-case of traffic engineering across the backbone networks of large content providers. We demonstrate that our approach yields both superior quality solutions and significantly faster runtimes.
Bio: Michael Schapira is professor of Computer Science at Hebrew University. His research focuses on the design and analysis of (Inter)network architectures and protocols and, in particular, on the interface of networking and machine learning. Prior to joining Hebrew U, he worked at Google NYC's Infrastructure Networking Group and was a postdoctoral researcher at UC Berkeley, Yale University, and Princeton University. He is a recipient of the Allon Fellowship, the Wolf Foundation's Krill Prize, an ERC Starting Grant, faculty awards from Microsoft, Google, and Facebook, IETF/IRTF Applied Networking Research Prizes, and the IEEE Communications Society William R. Bennett Prize.
|
Fear Not, Vote Truthfully: Secure E-Voting Protocols for Score- and
Order-Based Rules By: Tamir Tassa, Dept. of Mathematics and Computer Science, The
Open University of Israel Host: Gil Einziger
| Oct 25, 2022
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link | Abstract: Electronic voting
systems are essential for holding virtual elections, and the need for such
systems increases due to the COVID-19 pandemic and the social distancing that
it mandates. One of the main challenges in e-voting systems is to secure the
voting process: namely, to certify that the computed results are consistent
with the cast ballots, and that the privacy of the voters is preserved. We
propose secure voting protocols for elections that
are governed by two central families of voting rules: score-based and order-based
rules. Our protocols offer perfect ballot secrecy, in the sense that they issue
only the required output, while no other information on the cast ballots is
revealed. Such perfect secrecy, which is achieved by employing secure
multiparty computation tools, may increase the voters’ confidence and,
consequently, encourage them to vote according to their true preferences.
The protocols' high level of privacy, and their extremely lightweight
nature, make them a most adequate and powerful tool for democracies of any
size. If time permits, we will briefly describe a Python open source
implementation of our protocol for score-based rules.
Joint work with Lihi Dery (Ariel U) and Avishay Yanai
(VMware Research)
Bio. Professor Tamir Tassa is a faculty member in the Department of
Mathematics and Computer Science at the Open University of Israel. Previously,
he served as a lecturer and researcher in the School of Mathematical Sciences
at Tel Aviv University, and in the Department of Computer Science at Ben Gurion
University. During the years 1993-1996 he served as an assistant professor of
Computational and Applied Mathematics at the University of California, Los
Angeles. He earned his PhD in mathematics from Tel Aviv
University in 1993. His recent research interests include secure multiparty
computation, privacy-preserving data publishing and data mining, and secret
sharing.
|
Proactive and Online Distributed Load Balancing By: Manish Kumar
Host: Shlomi Dolev | Sep 6, 2022
16:00-17:00
Bldg. 37, Room 202
>> Zoom Link | In this talk, I will present the main results of my Ph.D. research work.
● The load balancing problem is defined when there is an undirected network
(graph) of computers (nodes). Each one is assigned a non-negative working load
and would like to balance their loads. We study the classic load balancing
problem on dynamic general graphs, where the graph changes arbitrarily between
the computational rounds, remaining connected with no permanent cut.
We solve the load balancing problem in the most general setting (in relation to
the previous work) and best-known efficiency. Our solutions are anytime,
monotonic, and deterministic distributed algorithms based on a short local
deal-agreement communication of proposal/deal in the neighborhood of each node
and proposed synchronous, asynchronous, and self-stabilizing algorithms. [SSS
2020 and Theory of Computing Systems 2022]
● Another research direction focuses on the diverse solutions for optimization
problems, such as finding the multi-criteria k-shortest paths, prioritized
multi-criteria 2-disjoint shortest paths, and k disjoint all-criteria-shortest
paths. These algorithms help in balancing the load efficiently in the
communication network. [CSCML 2021 and submitted to SN Computer Science
Journal]
● Additionally, we have initiated a study on testing randomness using
randomness, which helps during prediction-based load balancing. [CSCML 2022 and
will be submitted to Cryptography and Communication Journal]
My advisor is Shlomi Dolev. During my Ph.D., I collaborated with Daniel Berend
and Yefim Dinitz. |
Scalable Bayesian Nonparametric Mixtures for
Computer Vision and Deep Learning By: Or Dinari (Host: Oren Freifeld) | Jul 5, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link | In the unsupervised-learning task of clustering, Bayesian
Nonparametric (BNP) mixtures provide a principled approach for inferring the
model complexity (i.e., the number of clusters) together with the other
parameters. Inference in such models, however, is more difficult than in the
parametric case (namely, when the number of clusters is known). In particular,
existing BNP methods usually scale poorly. This is a key obstacle in using such
models in real-world problems in general and, more specially, in Computer
Vision, where both the number of samples and the dimensions are usually high.
In this talk, I will present a few of our recent works that aim to bridge this
practicality gap, via new models, new inference algorithms, and efficient
distributed implementations.
References:
1) [Or Dinari and Oren Freifeld, AISTATS 2022]: Sampling
in Dirichlet Process Mixture Models for Clustering Streaming Data.
2) [Or Dinari and Oren Freifeld, UAI 2022]: Revisiting
DP-Means: Fast Scalable Algorithms via Parallelism and Delayed Cluster
Creation.
3) [Or Dinari*, Angel Yu, Oren Freifeld, and John Fisher
III. HPML Workshop, 2019]: Distributed MCMC Inference in Dirichlet Process Mixture
Models Using Julia.
4) [Or Dinari*, Raz Zamir*, John Fisher III, and Oren
Freifeld, Currently Under Review]: CPU- and GPU-based Distributed Sampling in
Dirichlet Process Mixtures for Large-scale Analysis.
About the speaker:
Or Dinari is a PhD student in the Department of Computer
Science at Ben-Gurion University, working in the areas of computer vision and
machine learning under the supervision of Dr. Oren Freifeld. His current
research focus is on unsupervised/semi-supervised learning, clustering, Bayesian
nonparametrics, deep learning, and computer-vision applications. >> Meeting Recording
|
A study of privacy and
compression in learning theory. By: Meni Sadigurschi (Host: Aryeh Kontrovich) | Jun 28, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link | Motivated by the
increasing awareness and demand for user privacy, the line of work on private
learning aims to construct learning algorithms that provide privacy protections
for their training data. It is especially desirable to achieve differential
privacy, a privacy notion which has been widely adopted by the academic
community, government agencies, and big corporations like Google, Apple, and
Microsoft.
In our work we study the task of private learning from various directions. In
this talk I will focus on two of these directions. The first is the fundamental
problem of learning
Axis-Aligned-Rectangles with differential privacy, for which I will present a
novel algorithm with optimal sample complexity. In the second part of the talk
I will present our study on ptivacy preserving universally Bayes consistent
learning, a notion of learning which is arguably more realistic than the
classical PAC learning framework. |
Implicit bias in machine learning By: Ohad Shamir (Host: Aryeh Kontrovich) | Jun 21, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link | Most practical
algorithms for supervised machine learning boil down to optimizing the average
performance over a training dataset. However, it is increasingly recognized
that although the optimization objective is the same, the manner in which it is
optimized plays a decisive role in the properties of the resulting predictor.
For example, when training large neural networks, there are generally many
weight combinations that will perfectly fit the training data. However,
gradient-based training methods somehow tend to reach those which, on the one
hand, do not overfit, and on the other hand, are very brittle to adversarially
crafted examples. Why the dynamics of these methods lead to such "implicit
biases" is still far from being fully understood. In this talk, I'll
describe several recent theoretical results related to this question, in the
context of benign overfitting and adversarial examples.
Based on joint work with Gal Vardi and Gilad Yehudai.
|
Federated Learning: Collaborative Learning on
Private Data By: Friedman Award - Amit Portnoy (Host: Danny Hendler) | Jun 14, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link | Federated learning is a distributed machine learning
paradigm where clients collaboratively train a model without sending their
local data samples. Federated learning opens new opportunities for data
partnerships at scale, with applications in healthcare, transportation, IoT,
and more.
We introduce federated learning, discuss the
communication challenges it poses, and present EDEN—a robust lossy compression
technique tailored for its specific communication patterns and constraints. We
discuss EDEN's appealing theoretical guarantees and present empirical results
that demonstrate that it consistently improves over the state-of-the-art. EDEN
will be presented at ICML '22. It is a generalization of our previous
compression technique named DRIVE, presented at NeurIPS '21.
This talk is for a general CS audience.
Amit Portnoy is a Ph.D. student in the CS department,
advised by Prof.
Danny Hendler. This is joint work with Ran Ben Basat,
Yaniv Ben-Itzhak, Gal Mendelson, Michael Mitzenmacher, and Shay Vargaftik.
|
New Directions in
Derandomization: Non-Black-Box Techniques, Superfast Algorithms By: Roei Tell (Host: Yuval Pinter) | Jun 7, 2022
15:20
zoom talk
Bldg. 37, Room 201>>Zoom Link | This talk will present
two new directions in the study of derandomization, which are related to each
other.
The first direction is avoiding pseudorandom generators in favor of
*non-black-box techniques*, thereby replacing the classical
hardness-vs-randomness framework with a new framework. The non-black-box
techniques extract pseudorandomness for a probabilistic machine from the code
of that specific machine.
The second direction is trying to minimize the computational overhead when
eliminating randomness, hoping for *free lunch results* in derandomization.
This is possible both for probabilistic algorithms, and for interactive proof
systems.
We will mention results from the last two years by myself and by others, most
prominently from joint works of mine with Lijie Chen. |
Matching vertices of
correlated random graphs
By: Mark Rudelson
(Host: Aryeh Kontrovich) | May 24, 2022
12:00-13:00
Bldg. 37, Room 201>>Zoom Link | Consider two copies of the same graph with a large number of
vertices.
In each copy, we independently delete a few edges. Our aim is to match
exactly the vertices of the first and the second copy. This problem
originates in particular in social networks, where you know the
identities of users in one network and want to recover the identities
in another one. This problem is computationally hard in a
deterministic setting, so it is often considered for typical, i.e.,
random graphs. We will discuss a computationally efficient
probabilistic algorithm which allows an exact recovery with high
probability even if one deletes a small constant proportion of edges.
Joint work with Cheng Mao and Konstantin Tikhomirov.
|
Quantum Pseudorandomness
and Classical Complexity
By: William Kretschmer
(Host: Dr. Or Sattath) | May 24, 2022
10:00-11:00
Bldg. 37, Room 201 >>Zoom Link | Pseudorandom quantum
states (PRSs) are a recently-introduced primitive
that have found exciting new applications in quantum cryptography and
black hole physics. In this talk, I will explore some connections
between PRSs and structural complexity theory. I will present a
surprising and counterintuitive result: a quantum oracle relative to
which BQP = QMA but PRSs exist. On the other hand, I will show that
PRSs do not exist if BQP = PP, a result which holds relative to all
oracles. I will discuss some implications of these results, including
a new impossibility result for shadow tomography.
Based on https://arxiv.org/abs/2103.09320
Homepage: https://www.cs.utexas.edu/~kretsch/ >> Meeting Recording |
Access strategies for network caching
By: Itamar Cohen
(Host: Dr. Gil Einziger) | Apr. 12, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link | Caching systems commonly advertise the cached content, thus allowing users to select which cache to query for the desired datum. The data structure used to advertise the cached content is called indicator. Due to bandwidth and energy constraints, a practical indicator is typically not a fresh, accurate list of all the items currently stored in the cache. Instead, the indicator is a stale approximation of the list of the currently cached items. As a result, indicators experience false indications. These false indications significantly increase costs, and may even result in a scenario where using indicators does more harm than good.
Our work introduces the cache selection problem, namely, the problem of selecting which cache to access in the face of such false indications. We formally model this problem as a cost minimization problem and introduce practical algorithms with guaranteed approximation ratios. We further perform an extensive simulation study with multiple real system traces. We show that our algorithms incur a significantly lower access cost than existing approaches or match the cost of these approaches while requiring an order of magnitude fewer resources (e.g., caching capacity or bandwidth).
Itamar Cohen received his B.Sc. degree in computer engineering and M.Sc. in electrical engineering from the Technion – I.I.T, and Ph.D. from the Ben-Gurion University of the Negev. He worked as a Chip Designer with EZchip Technologies, as a Test Engineer at Marvell, and as a Research Assistant at REMON—Israel 4G Mobile Consortium. He is currently a Post-Doctoral Fellow with the Politecnico di Torino, Italy. His research interests include network algorithms and resource allocation problems, and specifically issues related to scheduling, cooperative caching, and decision making under uncertainty. |
Projection Methods, Superiorization and Applications
By: Aviv Gibali
(Host: Dr. Eran Treister)
| Mar. 31, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link
| Projection methods are iterative algorithms that use projections onto sets
while relying on the general principle that when a family of sets is present,
then projections onto the given individual sets are easier to perform than
projections onto other sets that are derived from the given individual sets.
Their robustness, low computational effort and their ability to handle
huge-size problems make them very useful for many convex and non-convex real-world problems
such as Image Reconstruction, Intensity-Modulated Radiation Therapy
(IMRT) Treatment Planning as well as Sudoku and 8 Queens Puzzle.
The Superiorization Methodology is a heuristic tool and its goal is to find certain good, or superior, solutions to feasibility and optimization problems. In many scenarios, solving the full problem can be rather demanding from the computational point of view, but solving part of it, say the feasibility part is, often, less demanding.
In recent years "superiorized" projection methods and other iterative methods have been developed and applied successfully to feasibility, single and multi-objective optimization.
In this talk I will provide an overview on the above concepts, present several theoretical and practical results and also potential direction for future research.
|
Generalization in Overparameterized Machine Learning
By: Yehuda Dar
(Host: Eran Treister)
| Mar. 23, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link
| Deep neural networks are highly overparameterized models, i.e., they are highly complex with typically many more parameters than the number of training data examples. Such overparameterized models are usually learned to perfectly fit their training data; yet, in sharp contrast to conventional machine learning guidelines, they still generalize extremely well to inputs outside of their training dataset. This practical generalization performance motivates numerous foundational questions that have not yet been addressed even for much simpler models like linear regression.
This talk presents new analyses of the fundamental factors that affect generalization in overparameterized machine learning. Our results characterize the so-called “double descent phenomenon," which extends the classical bias-variance tradeoff, in several overparameterized learning settings. First, we consider a transfer learning process between source and target linear regression problems that are related and overparameterized. Our theory characterizes the generalization performance and hence the cases where transfer learning is beneficial. Second, we consider linear subspace learning problems for dimensionality reduction and data generation. We define semi- and fully supervised extensions to the common unsupervised forms of these subspace learning problems and demonstrate that overparameterization in conjunction with supervision can improve generalization performance.
Bio:
Yehuda Dar is a postdoctoral research associate in the Electrical and Computer Engineering Department at Rice University, working on topics in the foundational understanding of modern machine learning. Before that, he was a postdoctoral fellow in the Computer Science Department of the Technion — Israel Institute of Technology where he also received his PhD in 2018. Yehuda earned his MSc in Electrical Engineering and a BSc in Computer Engineering, both also from the Technion. His main research interests are in the fields of machine learning, signal and image processing, optimization, and data compression.
>> Link to Lecture
|
Information geometry of Markov kernels
By: Shun Watanabe
(Host: Aryeh Kontorovich)
| Mar. 22, 2022
12:00-13:00
>> Zoom Link
| In this talk, we first review basic concepts on the information geometry,
such as the e-family , m-family, and the Pythagorean identity, in the context
of probability distribution. We will also discuss an application of information
geometry to the problem of statistical hypothesis testing. Then, we will
discuss how the concepts of information geometry are extended to Markov
kernels. Finally, we will present our recent result that the set of reversible
Markov kernels constitute both e-family and m-family of Markov kernels.
This talk is based on a joint work with Geoffrey Wolfer.
>> Link to Lecture
|
Seeing the Unseen - a Generalized Scheme for Missing Mass Estimation
By: Amichai Painsky
(Host: Aryeh Kontorovich)
| Mar. 21, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link
| Consider a finite sample from an unknown distribution over a countable
alphabet. The missing mass refers to the probability of symbols that do not appear
in the sample. Estimating the missing mass is a basic problem in statistics,
machine learning and related fields, which dates back to the early work of
Laplace, and the more recent seminal contribution of Good and Turing. The
missing mass problem has many applications in a variety of domains. For
example, given the observed population of Covid mutations, what is the
probability that we encounter a new variant that has not been seen before? In
this work we introduce a generalized framework for missing mass estimation. Our
framework provides novel risk bounds and improves upon currently known
estimation schemes. Importantly, it is easy to apply and does not require
additional modeling assumptions. This makes it a favorable choice for many
practical setups. Furthermore, we show that by utilizing our scheme, we improve
the estimation accuracy of large alphabet probability distributions.
Bio:
Amichai Painsky is a Senior Lecturer (Assistant Professor) at Tel Aviv
University. Amichai received his B.Sc. in Electrical Engineering from Tel Aviv
University (2007), his Masters in Electrical Engineering from Princeton
University (2009) and his Ph.D. in Statistics from Tel Aviv University (2016).
Following his graduation, Amichai joined Massachusetts Institute of Technology
(MIT) as a postdoctoral fellow (2019). Amichai's research focuses on
statistical inference and learning, and their connection to information theory.
>> Link to Lecture
|
Rank Aggregation with Proportionate Fairness
By: Baruch Schieber
(Host: Michael Elkin)
| Mar. 15, 2022
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
| Given multiple individual rank orders over a set of candidates or items,
where the candidates belong to multiple (non-binary) protected groups, we study
the classical rank aggregation problem under proportionate or p-fairness (RAPF
in short), considering Kemeny distance.
We first study the problem of producing a closest p-fair ranking for an
individual ranked order (IPF in short) considering Kendall-Tau distance, and
present multiple solutions for IPF. We then present a deterministic algorithm
and a randomized algorithm to solve RAF that leverage the solutions of IPF as a
subroutine.
We make several algorithmic contributions: (i) we prove that when the group
protected attribute is binary, IPF could be solved exactly using a greedy
technique; (ii) when the group protected attribute is multi-valued, solving IPF
is non-trivial: we present two different solutions for it, one is exact under
the assumption that the number of attribute values is constant, and the other
admits a 2 approximation factor; (iii) we present the guiding principle of designing
the solution for RAPF with an approximation factor that is 2+ the approximation
factor of the IPF solution, resulting in 3 and 4 approximation algorithms.
We run extensive experiments using multiple real world and large scale
synthetic datasets and compare our proposed solutions against multiple
state-of-the-art related works to demonstrate the effectiveness and efficiency
of our studied problem and proposed solution.
This is joint work with Senjuti Basu Roy, Mouinul Md Islam, and Dong Wei.
>> Link to Lecture
|
Sequential and distributed clustering algorithms
By: Tom Hess
(Supervisor: Prof. Sivan Sabato)
| Mar. 1, 2022
12:00-13:00
>> Zoom Link
| This seminar is about sequential and distributed clustering.
First, I introduce and study the setting of no-substitution sequential k-median
clustering. In this setting, an i.i.d. sequenceof examples is observed. An example can be selected as a center only
immediately after it is observed, and it cannot be substituted later.
The goal is to select a set of centers with a good k-median cost on the
distribution generated the sequence.
I provide algorithms for this setting in a general bounded metric space and
show that these algorithms obtain a similar cost guarantee for the best offline
algorithm. In addition, I study the k-median clustering under the sequential
no-substitution setting, without any structural assumption on the metric space.
I give the first algorithm for this setting that obtains a constant
approximation factor on the optimal cost, an exponential improvement over
previous work. Moreover, the number of selected centers is only quasi-linear in
k.
Second, I provide a new k-means algorithm for the distributed setting, where
the data is distributed across many machines, and a coordinator communicates
with these machines to calculate the output clustering. This algorithm
guarantees a cost approximation factor and a number of communication rounds
that depend only on the computational capacity of the coordinator. Moreover,
the algorithm includes a built-in stopping mechanism, which allows it to use
fewer communication rounds whenever possible. I show both theoretically and
empirically that in many natural cases, indeed 1-4 rounds suffice.
>> Link to Lecture
|
Optimal Linear Numeric
Planning
By: Dr. Alexander
Shleyfman
(Host: Prof. Ronen Brafman)
| Feb. 1, 2022
12:00-13:00
>> Zoom Link
| Forward search, such as A*, equipped with an informative heuristic and a strong pruning technique, proved to be one of the most efficient methods to solve planning problems. Most of these heuristics and pruning techniques, however, are currently limited by an assumption that all variables involved have finite domains. While numeric variables play an important, sometimes central, role in many planning problems arising from real world scenarios, most of the currently available heuristic search planners either do not support such variables or impose heavy restrictions on them. In particular, most current planners do not support heuristics and pruning techniques that account for linear numeric effects. The contribution of our work is twofold.
First, we extend the symmetry breaking pruning methods such as DKS and Orbit Space Search, proposed by Domshlak et al. (2012, 2015) to support actions with linear conditions and effects. Our experiments further show that symmetry reduction can yield a substantial reduction in search effort even if the algorithm is equipped with a strong heuristics.
Second, we adapt the well-known classical planning heuristic LM-cut (Helmert and Domshlak, 2009) to account for both additive constant and linear effects, where for linear effect we show a way to efficiently exploit specific variable structures. Empirical comparison shows that the proposed LM-cut heuristic favorably competes with the currently available state-of-the-art heuristics and achieves significant improvement in coverage.
Bio:
Alex did his Master's and PhD degrees in the field of Artificial Intelligence at the Faculty of Industrial Engineering and Management at the Technion under the supervision of Prof. Carmel Domshlak. After that, he moved to Canada for a postdoctoral fellowship at the University of Toronto, where he was hosted by Prof. J. Christopher Beck, and worked on resource management for cloud services and numeric planning. Today, Alex is back in Israel. He is a postdoctoral fellow at the Technion, at the Cognitive Robotics lab, hosted by Prof. Erez Karpas.
>> Link to Lecture
|
On the Role of Data in Algorithm Design
By: Tal Wagner
(Host: Prof. Sivan Sabato)
| Jan. 11, 2022
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
| Recently, there has been a growing interest in harnessing the power of big datasets and modern machine learning for designing new scalable algorithms. This invites us to rethink the role of data in algorithm design: not just as the input to pre-designed algorithms, but also a factor that enters the algorithm design process itself, driving it in a strong and possibly automated manner. This talk will show how to leverage data and learning for better algorithm design in two fundamental areas: high-dimensional similarity search and efficient linear algebra.
In particular, I will show the following:
1. Using data-dependent compression, we obtain optimal compressed representations of high-dimensional Euclidean distances. This result marks the first improvement over classical data-oblivious compression schemes, which provably cannot match its performance.
2. Using neural networks, we show how to learn to construct better data structures for high-dimensional similarity search.
3. We then show how those techniques also give rise to fast algorithms for low rank approximation of matrices.
Our algorithms are both proven analytically and implemented and validated empirically, showing improvements over previous methods on standard benchmark datasets.
Bio:
Tal Wagner is a postdoctoral researcher in the Machine Learning Foundations group at Microsoft Research Redmond. His research interests are in designing algorithms for massive high-dimensional datasets and large-scale machine learning. He received his PhD from the EECS department at MIT in September 2020. Previously, he earned his MSc from the Weizmann Institute and BSc from the Technion. During his PhD, he spent time as a research intern in Microsoft, Amazon and VMware.
|
Information in Mechanism Design
By: Alon Eden
(Host: Dr. Sigal Oren)
| Jan. 4, 2022
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| The modern economy is becoming highly digital, demanding a combination of both economic and computational techniques. The abundance of data and the unique nature of digital markets highlight the special role of information in today's economic systems. In this talk, I will discuss two domains of interest. The first is auction design in the interdependent value (IDV) setting. In IDV settings, buyers hold partial information regarding the quality of the good being sold, but their actual values also depend on information that other buyers have about the good. The second is indirect mechanism design, in which the economic system can only observe partial information regarding the buyers' preferences, if any. In both domains, impossibilities are known for very basic settings. I will show how my research has pushed the boundary of what is possible via a computational approach. For IDV settings, I utilize techniques from approximation algorithms to obtain the first general positive results for combinatorial auctions. For indirect mechanisms, I initiate the use of reinforcement learning for the design of such mechanisms.
>> Link to Lecture
|
Learning with Less Data
and Labels for Language Acquisition and Understanding
By: Elior Sulem
(Host: Prof. Michael Elhadad)
| Jan. 2, 2022
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| Natural Language Processing has attracted a lot of interest in recent years and has seen large improvements with the use of contextualized neural language models. However, the progress is limited to specific tasks where large datasets are available and models are often brittle outside of these datasets. Also, current models are usually pretrained on extremely large unlabeled datasets, which limits our understanding of low-resource scenarios and makes their use unfeasible for many in the academia and industry. On the other hand, children learn with much less data, which makes the study of child language acquisition an appealing research direction to address these issues. In the first part of the talk, I will focus on pretraining on unlabeled data and show what can be learned with an input both quantitatively and qualitatively comparable to that of an average English-speaking 6 year old. In the second part of the talk I will focus on Natural Language Understanding and show how zero-shot and transfer learning strategies can be used to go beyond task-specific training. In particular, I will present a zero-shot approach to Event extraction, which is usually based on the annotation of large domain-specific corpora, using Textual Entailments (TE) and Question-Answering (QA) tasks. I will show the challenge of missing arguments in this context, presenting new models that identify unanswerable questions, leveraging different QA and TE tasks.
Bio:
Elior Sulem is a Postdoctoral Researcher at the Department of Computer and Information Science at the University of Pennsylvania, working with Prof. Dan Roth on computational semantics, event extraction and computational psycholinguistics. He completed his PhD. in the School of Computer Science and
Engineering at the Hebrew University of Jerusalem under the supervision of Prof. Ari Rappoport in 2019, working on the integration of semantic information into text simplification and machine translation. Before that, he graduated with a master's degree (magna cum laude) in Cognitive Science at the Hebrew University of Jerusalem, under the supervision of Prof. Ari Rappoport (Cognitive Sciences Department's prize for outstanding thesis). He previously completed a B.Sc. degree in Mathematics (extended program) and
Cognitive Sciences at the Hebrew University. He was a fellow of the Language, Logic and Cognition Center from 2012 to 2016. He received the Best Paper Award Runner Up at CoNLL 2021.
>> Homepage
Links to related papers:
https://aclanthology.org/2021.conll-1.49/
https://aclanthology.org/2021.findings-emnlp.385.pdf
|
Informed Data Science
By: Amir Gilad
(Host: Prof. Ehud Gudes)
| Dec. 28, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| 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, exploring it, 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 approaches for addressing them. 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. Bio: Amir Gilad is a postdoctoral researcher in the Database group at Duke University. He received his Ph.D. in Computer Science from Tel Aviv university under the supervision of Prof. Daniel Deutch. His work focuses on developing tools and algorithms that assist users in understanding and gaining insights into data and the systems that manipulate it. His research relates to classic database tools such as data provenance, as well as natural language processing, causal inference, and privacy. Amir is the recipient of the VLDB best paper award, the SIGMOD research highlight award, and the Google Ph.D. fellowship for Structured Data and Database Management. |
Sublinear-time graph algorithms: motif counting and
uniform sampling
By: Talya Eden
(Host: Prof. Michael Elkin)
| Dec. 21, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| In this talk I will survey recent developments in approximate subgraph-counting and subgraph-sampling in sublinear-time. Counting and sampling small subgraphs (aka motifs) are two of the most basic primitives in graph analysis, and have been studied extensively, both in theory and in practice. In my talk, I will present the sublinear-time computational model, where access to the input graph is given only through queries, and will explain some of the concepts that underlie my results. I will then explain how we can get improved bounds for a very natural graph family: the family of bounded arboricity graphs. Finally, I'll present a recent application, where again we take advantage of the unique structure of social networks in order to get improved bounds for a very basic and well-studied problem.
Bio: Talya Eden is a postdoctoral fellow jointly affiliated with MIT and Boston University. She works on sublinear-time graph algorithms and randomized algorithms for huge data sets. Her work focuses on theoretical and applied graph parameter estimation in sublinear-time, as well as graph algorithms in other related areas, such as the streaming model, the massively parallel computation model, and learning-augmented algorithms. Talya completed her PhD at the School of Electrical Engineering at Tel Aviv University under the supervision of Prof. Dana Ron, and then continued on to a postdoctoral fellowship with the Foundations of Data Science Institute at MIT. Talya has won several awards for her work, including the EATCS Distinguished Dissertation Award in Theoretical Computer Science, a Rothschild Postdoctoral Fellowship, a Schmidt Postdoctoral Award, a Ben Gurion University postdoctoral fellowship, a Weinstein Graduate Studies Prize, and the Azrieli Fellows Scholarship. >> Homepage >> Link to Lecture
|
Harnessing Scientific Literature for Boosting Discovery and Innovation
By: Tom Hope
(Host: Dr. Yuval Pinter)
| Dec. 14, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| 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.
Bio:
Tom Hope is a postdoctoral researcher at The Allen Institute for AI (AI2) and
The University of Washington, working with Daniel Weld on accelerating
scientific discovery and closely collaborating with Eric Horvitz, CSO at
Microsoft. Tom completed his PhD with Dafna Shahaf at the Hebrew University of
Jerusalem in January 2020. His work has received four best paper awards,
appeared in top venues (PNAS, KDD, EMNLP, NAACL, WSDM, CHI, AKBC, IEEE), and
received media attention from Nature and Science on his systems for COVID-19
researchers. In parallel to his PhD studies Tom created and led an applied AI
research team at Intel that published award-winning work. Tom was selected for
the 2021 Global Young Scientists Summit and 2019 Heidelberg Laureate Forum, and
was a member of the KDD 2020 Best Paper Selection Committee.
>> Link to Lecture
|
Large-scale multi-robot systems: From algorithmic
foundations to smart-mobility applications
By: Kiril Solovey
(Host: Prof. Ronen Brafman)
| Dec. 7, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| 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 safe, 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.
BIO: Kiril Solovey is a roboticist specializing in multi-robot systems and their applications to smart mobility. He is currently a Postdoctoral Scholar in the Faculty of Computer Science at the Technion. Prior to that, he was a postdoc in the Department of Aeronautics and Astronautics, Stanford University. He obtained a PhD in Computer Science from Tel Aviv University, where he was advised by Dan Halperin.
Kiril's research focuses on the design of scalable algorithmic approaches for multi-robot systems. His work draws upon ideas across the disciplines of computer science, engineering, and transportation science, to develop methods with substantial guarantees on solution quality and robustness. He received multiple awards, including the Clore Scholars and Fulbright Postdoctoral Fellowships, best paper awards and nominations (at Robotics: Science and Systems, International Conference on Robotics and Automation, International Symposium on Multi-Robot and Multi-Agent System, and European Control Conference), and teaching awards.
>> Homepage
SELECTED PAPERS:
* Rahul Shome, Kiril Solovey, Andrew Dobson, Dan Halperin, Kostas E.
Bekris: dRRT*: Scalable and informed asymptotically-optimal multi-robot motion planning. Auton. Robots 44(3-4): 443-467 (2020)
* Kiril Solovey, Mauro Salazar, Marco Pavone: Scalable and Congestion-Aware Routing for Autonomous Mobility-On-Demand Via Frank-Wolfe Optimization. Robotics: Science and Systems 2019
* Devansh Jalota, Kiril Solovey, Karthik Gopalakrishnan, Stephen Zoepf, Hamsa Balakrishnan, Marco Pavone: When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes. EAAMO 2021: 9:1-9:11
>> Link to Lecture
|
Efficient Secure Multi-Party Computation: How Low
Can We Go?
By: Ariel Nof
(Host: Prof. Amos Beimel)
| Nov. 30, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| In the setting of secure multi-party computation, a set of parties with private inputs wish to compute a joint function of their inputs, without revealing anything but the output. This computation is carried-out in the presence of an adversary controlling a subset of the parties, who may try to learn private information or disrupt the computation. The problem of constructing efficient protocols for secure computation has gained significant interest in the last decade or so and progress has been extraordinarily fast, transforming the topic from a notion of theoretical interest only, into a technology that is even being commercialized by multiple companies. A useful metric for measuring efficiency of secure protocols is the ratio between the communication cost of the protocol, and that of the best known protocol with a “minimal" level of security, namely security against semi-honest (passive) adversaries, who act as prescribed by the protocol but try to learn additional information from messages they receive. In this talk, I will describe recent efforts to minimize this ratio and show, in the honest majority setting, new results that close (in the amortized sense) the communication gap between secure protocols against adversaries who act in any arbitrary manner, and protocols against semi-honest adversaries.
|
A Theoretical Analysis of Generalization in Graph Convolutional Neural
Networks
By: Ron Levie (LMU Munich)
(Host: Dr. Eran Treister)
| Nov. 23, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| In recent years, the need to accommodate non-Euclidean structures in data science has brought a boom in deep learning methods on graphs, leading to many practical applications with commercial impact. In this talk, we will review the mathematical foundations of the generalization capabilities of graph convolutional neural networks (GNNs). We will focus mainly on spectral GNNs, where convolution is defined as element-wise multiplication in the frequency domain of the graph. In machine learning settings where the dataset consists of signals defined on many different graphs, the trained GNN should generalize to graphs outside the training set. A GNN is called transferable if, whenever two graphs represent the same underlying phenomenon, the GNN has similar repercussions on both graphs. Transferability ensures that GNNs generalize if the graphs in the test set represent the same phenomena as the graphs in the training set. We will discuss the different approaches to mathematically model the notions of transferability, and derive corresponding transferability error bounds, proving that GNNs have good generalization capabilities. Links to related papers:
>> https://arxiv.org/pdf/1907.12972.pdf
>> https://arxiv.org/pdf/1705.07664.pdf
Bio:
Ron Levie received the Ph.D. degree in applied mathematics in 2018, from Tel Aviv University, Israel. During 2018-2020, he was a postdoctoral researcher with the Research Group Applied Functional Analysis, Institute of Mathematics, TU Berlin, Germany. Since 2021 he is a researcher in the Bavarian AI Chair for Mathematical Foundations of Artificial Intelligence, Department of Mathematics, LMU Munich, Germany. Since 2021, he is also a consultant at the Huawei project Radio-Map Assisted Pathloss Prediction, at the Communications and Information Theory Chair, TU Berlin. He won excellence awards for his MSc and PhD studies, and a Postdoc Minerva Fellowship. He is a guest editor at Sampling Theory, Signal Processing, and Data Analysis (SaSiDa), and was a conference chair of the Online International Conference on Computational Harmonic Analysis (Online-ICCHA 2021).
His current research interests are in the theory of deep learning, geometric deep learning, interpretability of deep learning, deep learning in wireless communication, harmonic analysis, signal processing, wavelet theory, uncertainty principles, continuous frames, and randomized methods.
>> Homepage
|
Towards Revealing Visual
Relations Between Fixations: Modeling the Center Bias During Free-Viewing
By: Rotem Mairon
(Adviser: Prof. Ohad Ben Shahar)
| Nov. 16, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| Understanding eye
movements is essential for comprehending visual selection and has numerous
applications in computational vision and human-computer interfaces.
Eye-movement research has revealed a variety of behavioral biases that guide
the eye regardless of visual content.
However, computational models of eye-movement behavior only partially account
for these biases. The most well-known of these biases is the center bias, which
refers to the tendency of observers to fixate on the stimulus's center. In this
study, we investigate two aspects of the center bias to help distinguish it
from visual content-driven behavior. One aspect concerns standard procedures
for collecting eye-movement data during free viewing. Specifically, the
requirement to fixate on the center of the display prior to the appearance of
the stimulus, as well as the presentation of the stimulus in the display's
center. Our findings support a fundamental shift in data collection and
analysis procedures, all in the name of obtaining data that reflects more
content-driven and less bias-related eye-movement behavior. The second aspect is how the
center bias manifests during viewing, as opposed to how it is reflected in the
spatial distribution of aggregated fixations, which is used in almost all
computational models of eye-movement behavior. To that end, this work proposes
an eye-movement data representation based on saccades rather than fixations.
This representation not only demonstrates the dynamic nature of the center bias
throughout viewing, but it also holistically demonstrates other eye-movement
phenomena that were previously investigated exclusively. Finally, we
demonstrate that the proposed representation allows for more accurate modeling
of eye-movement biases, which is critical for establishing a baseline for
computational models. Such a baseline paves the way for researchers to learn
how, if at all, visual content guides the human eye from one fixation to the next
while freely viewing natural images.
|
Mind Reading: Decoding Visual Experience from Brain Activity
By: Guy Gaziv (WIS)
(Host: Dr. Eran Treister)
| Nov. 9, 2021
12:00-13:00
Bldg. 37, Room 202
| Reconstructing and semantically classifying observed natural images from
novel (unknown) fMRI brain recordings is a milestone for developing
brain-machine interfaces and for the study of consciousness. Unfortunately,
acquiring sufficient “paired” training examples (images with their
corresponding fMRI recordings) to span the huge space of natural images and
their semantic classes is prohibitive, even in the largest image-fMRI datasets.
We present a self-supervised deep learning approach that overcomes this
barrier, giving rise to better generalizing fMRI-to-image decoders. This is
obtained by enriching the scarce paired training data with additional easily
accessible “unpaired” data from both domains (i.e., images without fMRI, and
fMRI without images). Our approach achieves state-of-the-art results in image
reconstruction from fMRI responses, as well as unprecedented large-scale
(1000-way) semantic classification of never-before-seen classes.
Bio:
Guy Gaziv is a postdoctoral fellow in the Michal Irani Computer Vision group at
The Weizmann Institute of Science. This spring he will be starting his postdoc at the DiCarlo Lab at MIT. His PhD research focused on the intersection between machine and human vision,
and specifically on decoding visual experience from brain activity. Guy earned his BSc in Electrical and Computer Engineering from The Hebrew
University of Jerusalem, and his MSc in Physics and PhD in Computer Science
from The Weizmann Institute of Science.
|
Research-oriented
gathering of students and faculty members
By: Various Faculty Members
(Host: Dr. Eran Treister) | Nov. 2, 2021
12:00-13:00
Bldg. 37, Room 202
| You are invited for a small research-oriented gathering of students and faculty members on Nov 2nd, at 12:00, room 202/37 (invitation attached). The gathering is mostly intended for new students who did not find an adviser yet, but everyone is welcome. There will be six faculty members presenting their research briefly, two of them are new in the department. These faculty members and others that will also attend the meeting are looking for students, and this is a good opportunity to talk to them. We will also encourage faculty members to be available for personal meetings with you.
So - if you haven't done so already, we encourage you to visit our department's research page and follow the links according to your field(s) of interest. Try to read about the research fields and visit the web-pages of the relevant faculty members. Once you find a faculty member that looks relevant - email him/her and try to schedule a meeting (optionally, but not necessarily on that day).
|
Scaling laws for deep learning
By: Jonathan Rosenfeld
(Host: Dr. Eran Treister)
| Oct. 26, 2021
12:30-13:30
>> Zoom Link
| Running faster will only get you so far -- it is generally advisable to
first understand where the roads lead, then get a car ...
The renaissance of machine learning (ML) and deep learning (DL) over the last
decade is accompanied by an unscalable computational cost, limiting its
advancement and weighing on the field in practice. In this talk, we take a
systematic approach to address the algorithmic and methodological limitations
at the root of these costs. We first demonstrate that DL training and pruning
are predictable and governed by scaling laws -- for state of the art models and
tasks, spanning image classification and language modeling, as well as for
state of the art model compression via iterative pruning. Predictability, via
the establishment of these scaling laws, provides the path for the principled
design and trade-off reasoning, currently largely lacking in the field. We then
continue to analyze the sources of the scaling laws, offering an
approximation-theoretic view and showing through the exploration of a noiseless
realizable case that DL is in fact dominated by error sources very far from the
lower error limit. We conclude by building on the gained theoretical understanding
of the scaling laws' origins. We present a conjectural path to eliminate one of
the current dominant error sources -- through a data bandwidth limiting
hypothesis and the introduction of Nyquist learners -- which can, in principle,
reach the generalization error lower limit (e.g. 0 in the noiseless case), at
finite dataset size.
|
Expanding the hub and spoke model
By: Clara Shikhelman (Chaincode Labs)
(Host: Dr. Or Sattath)
| Oct. 19, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
| When two parties transact often using banks, Bitcoin, or any other financial device that entails fees, they might choose to turn to second-layer solutions. In these solutions, both parties lock a certain amount as escrow in a channel and transact freely with reduced fees. This gives rise to a network of channels in which any two nodes can transact with each other. A downside of these solutions, especially if they are decentralized, is the tendency of the network toward the hub and spoke model. Most nodes in this model, the “spokes", are connected to a single “hub", a high degree node that the spokes believe to be well connected. This graph topology is known to be prone to various attacks and privacy issues. In this work, we present a solution that benefits the spokes, by saving on costs, and the network, by giving it higher connectivity and good expansion properties. We use probabilistic and spectral techniques for the proofs. Short Bio: Clara Shikhelman holds a PhD in mathematics from Tel Aviv University. Following a year at Simons institute in Berkeley and CalTech, she is currently a PostDoc at Chaincode Labs.
|
