Up Next
Itamar Cohen
On
Is teaching CS theory an NP-Hard problem?
December 18, 2024
Abstract.
Teaching complex CS theory concepts can be a daunting task. How can we effectively bridge the gap between abstract mathematical theory and practical understanding? This talk explores techniques to make challenging topics like k-CNF satisfiability more engaging and comprehensible. We will delve into the use of visual aids, interactive demonstrations, and real-world analogies to simplify complex proofs and concepts. By applying these strategies, we can empower students to grasp the intricacies of CS theory and foster a deeper appreciation for the field.
Itamar Cohen has been teaching in Israeli universities and colleges since 2003. He was awarded prizes for excellence in education from Ben-Gurion University and Azrieli College of Engineering. Previously, he spent three years as a private tutor, preparing students for the matriculation exams in mathematics and Hebrew grammar. With a proven track record of engaging students and fostering a deep understanding of complex concepts, Itamar is passionate about making computer science accessible to all.
Location of Seminar:
Moreshet Building, room 58.3.35.
Schedule
Shay Golan
On
Locally Consistent Parsing for Text Indexing in Small Space
December 11, 2024
Abstract. The Locally Consistent Parsing technique was introduced by Sahinalp and Vishkin [STOC'94], as a way of partitioning a given text into blocks. The partitioning has the property that if a string appears as a substring of the text multiple times, then all these substrings are composed of exactly the same blocks, except for possibly small margins of the substrings. In this talk we will describe how the Locally Consistent Parsing technique could be useful for solving a text indexing problem in sub-linear working space. The problem is the Longest Common Extension (LCE) problem, where a text S of length n is given in read-only memory with some trade-off parameter 1≤𝜏≤ n, and the goal is to construct a data structure that uses O(n/𝜏) words of space and can compute for any pair of suffixes their longest common prefix length in about O(𝜏) time per query. We show how to use ideas based on the Locally Consistent Parsing technique, in some non-trivial ways in order to improve the known results for the problem under the space constraints.
We introduce the first almost-linear, O(n log 𝜏), deterministic construction for the problem, where previous data structure, by Tanimura et al. [CPM'16] takes O(n𝜏) time. Our query time is O(𝜏√log*n) while the query time of previous data structure was O(𝜏 min{log 𝜏,log (n/𝜏)}). We also introduce the first linear-time Las-Vegas algorithm for the problem, achieving O(n) construction time with high probability. This is an improvement over the previous result of Gawrychowski and Kociumaka [SODA'17] which obtained O(n) time for Monte Carlo algorithm, and O(n√(log n/𝜏)) time with high probability for Las-Vegas algorithm.
The talk is based on a joint work with Or Birenzwige and Ely Porat.
Short Bio. Shay is currently a postdoctoral researcher at Reichman University and the University of Haifa, hosted by Shay Mozes and Oren Weimann. Previously, he was a Fulbright Postdoctoral Fellow at the University of California, Berkeley, hosted by Jelani Nelson. Shay completed his Ph.D. at Bar-Ilan University under the supervision of Ely Porat and Tsvi Kopelowitz.
Shay's research focuses on the design and analysis of algorithms, with a particular emphasis on string algorithms under small-space constraints. His work primarily addresses streaming pattern matching, similarity measurements between strings, and computations on strings within limited memory, leveraging combinatorial structures and randomization techniques.
Yohai Trabelsi
On
Fairness and Optimization in Dynamic Multiagent Allocation Problems
December 4, 2024
Abstract. In this talk, I will present several works addressing optimization and fairness problems in dynamic multi-agent environments. These works aim to maximize agent benefits and ensure fairness when key characteristics, such as the identity and the time of the arriving tasks in task allocation problems, are unknown before they arrive and when key factors like agent preferences may evolve as part of the optimization process in resource allocation problems. I will discuss how agents express their preferences, what are the criteria for solution optimality, how to model the problems (in most cases as matching in bipartite graphs), how to provide theoretically optimal solutions, and how to evaluate and optimize the effectiveness of the solutions in practical scenarios.
Short Bio. Yohai Trabelsi is a PhD student under the supervision of Prof. Sarit Kraus at Bar-Ilan University in Ramat Gan, Israel.
His research is on intelligent agents and multi-agent systems focusing on complex resource and task allocation problems involving topics like optimization, fairness, and constraint relaxation by humans. He is interested in both theoretical and experimental research.
Complementing his academic journey, he possesses eight years of practical industry experience in recommender systems, audience targeting, computer vision, and behavioral analysis.
Yohai is expected to begin a postdoctoral position at Harvard University in February.
Mor Vered
On
eXplainable AI ! … ?
November 27, 2024
Abstract. In this talk I’ll provide an overview of my work in eXplainable AI (XAI), examining its state-of-the-art techniques, current trends, and limitations. I'll begin by introducing key XAI methods and explore the growing demand for fairness, accountability, and human-in-the-loop systems, as well as the challenges of balancing model accuracy with explainability. Despite significant progress, XAI faces limitations, including the trade-off between model complexity and interpretability, and the subjective nature of explanations. I’ll also discuss the importance of Human-Centered AI, emphasizing that explanations must be understandable to people, and how insights from the social sciences can inform better explanation design. And finally, I will introduce Evaluative AI, a paradigm shift from the current model of XAI . This concept represents a step toward creating more accountable, robust, and transparent AI systems, ensuring that explanations not only make sense but also align with human values and decision-making needs.
Short Bio. I am a Senior Lecturer at Monash University, Australia, in the Faculty of IT. My research interests lie in the interaction between humans and intelligent agents, where I work to incorporate lessons and inspirations from cognitive science, neuroscience and biology. I am a firm believer that only by focusing on interdisciplinary studies can we achieve results that can strongly impact human life.
My PhD research (in Bar Ilan with the brilliant Prof Gal Kaminka) focused on the field of intention recognition where I have been modeling Mirroring processes in agents in order to perform efficient, human inspired plan recognition. I have since then begun working on Explainable AI, generating explanations built on cognitive theories, considering that these explanations need to be consumed by people and therefore taking into account human situation awareness models. My research interests further include social human agent interaction, cognitive modeling and psychology.
Aryeh Kontorovich
On
Coins, experts, Neyman-Pearson, Naive Bayes
November 20, 2024
Abstract. Starting with the deceptively simple problem of estimating the bias of a coin, we take a detour via optimal decision theory, Neyman-Pearson lemma, minimax guarantees, and open problems.
Short 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. He is also a Research Fellow at Ariel University. 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.
Moran Feldman
On
Parameterization in Submodular Maximization
July 3, 2024
Submodular maximization problems have gained importance over the last two decades due to a lucky combination of theoretical breakthroughs and emerging machine learning applications. Traditionally, the input in such problems is characterized by binary properties that the input is assumed to obey such as monotonicity and down-closed constraints. Recent works have started to replace these binary properties with continuous parameters. In other words, instead of algorithms that work when the property hold, and fail otherwise, we now have algorithms whose performance smoothly deteriorates as the function becomes farther from obeying the property. This has hugely increased the range of problems to which submodular maximization techniques apply, and produced more tailored results for specific problems. In this talk, I will survey some of the main results underlying this exciting development.
YAEL SABATO
On
Source Detection in Networks using the Stationary Distribution of a Markov Chain
June 26, 2024
Nowadays, the diffusion of information or infection through social networks is a common and a powerful phenomenon. One common way to model diffusions in networks is the Independent Cascade (IC) model.
Given a set of infected nodes according to the IC model, a natural problem is the source detection problem, in which the goal is to identify the unique node that has started the diffusion.
Maximum Likelihood Estimation (MLE) is a common approach for tackling the source detection problem, but it is computationally hard.
In this work, we propose an efficient method for the source detection problem under the MLE approach, which is based on computing the stationary distribution of a Markov chain. Using simulations, we demonstrate the effectiveness of our method compared to other state-of-the-art methods from the literature.
LIAV ZAFAR
On
One-Message Secure Reductions: On the Cost of Converting Correlations
June 19, 2024
Correlated secret randomness is a useful resource for secure computation protocols, often enabling dramatic speedups compared to protocols in the plain model. This has motivated a line of work on identifying and securely generating useful correlations.
Different kinds of correlations can vary greatly in terms of usefulness and ease of generation. While there has been major progress on efficiently generating oblivious transfer (OT) correlations, other useful kinds of correlations are much more costly to generate. Thus, it is highly desirable to develop efficient techniques for securely converting copies of a given source correlation into copies of a given target correlation, especially when the former are cheaper to generate than the latter.
In this work, we initiate a systematic study of such conversions that only involve a single uni-directional message. We refer to such a conversion as a one-message secure reduction (OMSR).
Recent works (Agarwal et al, Eurocrypt 2022; Khorasgani et al, Eurocrypt 2022) studied a similar problem when no communication is allowed; this setting is quite restrictive, however, with few non-trivial conversions being feasible. The OMSR setting substantially expands the scope of feasible results, allowing for direct applications to existing MPC protocols.
We obtain the following positive and negative results.
-
OMSR constructions. We present a general rejection-sampling based technique for OMSR with OT source correlations. We apply it to substantially improve in the communication complexity of optimized protocols for distributed symmetric cryptography (Dinur et al., Crypto 2021).
-
OMSR lower bounds. We develop general techniques for proving lower bounds on the communication complexity of OMSR, matching our positive results up to small constant factors.
Anat Paskin-Cherniavsky
On
New Results in Share Conversion
June 5, 2024
We say there is a share conversion from a secret sharing scheme $\Pi$ to another scheme $\Pi'$ implementing the same access structure if each party can locally apply a deterministic function to their share to transform any valid secret sharing under $\Pi$ to a valid (but not necessarily random) secret sharing of the same secret under $\Pi'$.
This notion was introduced by Cramer et al., where they particularly proved that for any access structure, the set of linear schemes over a given field has a maximal element (CNF) and a minimal element (DNF) under the partial ordering of convertibility.
They also show that Shamir is not maximal.
In this work, we initiate a systematic study of convertability between linear schemes, and put forward certain necessary conditions for convertability between a pair of schemes.
In particular, our work implies that Shamir is also not minimal, as well as any scheme where some
party has a share of sufficiently small size. For maximality, our results imply an exponential lower bound on the share size of maximal schemes.
In the setting of evolving secret sharing, recently introduced by Komargodski et. al, the number of parties is not bounded apriori, and every party receives a share as it arrives, which never changes in the sequel. The above conditions have implications to the evolving setting as well. Interestingly, unlike the standard setting, for a broad class of access structures, they imply that no minimal or maximal linear schemes exist (without any restrictions on the scheme beyond linearity).
This is joint work with Tamar Ben-David and Varun Narayanan.
Lev Yuhananov
On
Error Correction in Data Structures and DNA Storage
May 22, 2024
Abstract:
DNA storage is notable for its extraordinary data density, with the recent discovery of DNA stacks added to the method of storing memory bits in DNA. However, the exploration of dynamic DNA data structures for systematic storage and retrieval, such as trees or graphs, remains largely unexplored. These dynamic DNA data structures have the potential to enable innovative applications in information storage and retrieval. Error correction is crucial for maintaining the integrity of every DNA data structure due to the complexity of the biological processes involved. I will present various error-correcting codes relevant to data structures such as trees and graphs and those specifically designed for DNA storage.
Short Bio:
Lev Yohanaov is a postdoctoral researcher at the University of Maryland, and Ben Gurion University. He received the B.Sc., M.Sc., and Ph.D. degrees in computer science from the Technion—Israel Institute of Technology, in 2016, 2018, and 2022, respectively, advised by Professor Eitan Yaakobi. His research interests include coding theory, information theory, algebra, and combinatorics.
ELAD AIGNER-HOREV
On
Resilience of the quadratic Littlewood-Offord problem
May 15, 2024
We study the statistical resilience of high-dimensional data. Our results provide estimates as to the effects of adversarial noise over the anti-concentration properties of the quadratic Radamecher chaos $\bold{\xi}^\intercal M \bold{\xi}$, where $M$ is a fixed (high-dimensional) matrix and $\bold{\xi}$ is a conformal Rademacher vector. Specifically, we pursue the question of how many adversarial sign-flips can $\bold{\xi}$ sustain without ``inflating" $\sup_{x\in \R} \Pr{\bold{\xi}^\intercal M \bold{\xi} = x}$ and thus ``de-smooth" the original distribution resulting in a more ``grainy" and adversarially biased distribution. Our (probabilistic) lower bound guarantees for the resilience of the Rademacher chaos are instance dependent yet depend solely on various norms of $M$ (i.e. the data) offering the ability to efficiently compute non-trivial resilience guarantees directly from the data.
Joint work with Daniel Rosenberg and Roi Weiss.
OFER WALD
On
שימוש בכלי תכנות תחרותי בהוראת מדעי המחשב
May 8, 2024
עופר ולד - מסטרנט לתואר שני באוניברסיטה הפתוחה, מאמן של זוכי אולימפיאדות תכנות ומרכז הוראה בסדנה לתכנות תחרותי באו"פ יציג בקצרה את עבודת התזה שלו. במסגרת ההרצאה נסקור בקצרה את עולם התכנות התחרותי, נציג תחרויות בינלאומיות חשובות ואת ההבדל בין "תכנות תחרותי" ל"תחרות הדורשת תכנות". נראה את העבודה שנעשתה בבניית אתר המרכז שאלות בתכנות תחרותי ככלי אימון ולימוד לתלמידים. ולבסוף נציג ניתוח מקרה של השימוש באתר עבור קורס ספציפי של מבוא וההשפעה שלו על הלמידה בקורס.
AMOS AZARIA
On
Improving Large Language Models (LLMs) for Hebrew Use
May 1, 2024
While language models have been around for nearly a decade, it is only recently that they have reached performance that allows them to be used commercially. Still, they seem to have many drawbacks, which prevent them from becoming much more useful. Particularly, this is true for Hebrew LLMs, mainly due to the relatively small data available in Hebrew, and the smaller market (and thus global interest).
In this talk I will describe two different projects that I am currently involved in. The first project deals with detecting, marking, and deleting generation of false statements. This project was initially developed for an English LLM, but we are currently both improving the results and running experiments with the English LLM and attempting to use the same methodology for a Hebrew LLM. The second project is to develop a learnable translation based Hebrew LLM. Since English LLMs perform much better than Hebrew LLMs, a basic translation based LLM may use an English LLM at its core and translate both the input and output. However, such a solution has multiple drawbacks, as I will describe. Therefore, in the second project we attempt to overcome these drawbacks and propose a data-driven translation approach.