This paper addresses the $H$-Coloring problem, parameterized by the vertex cover number $k$, which asks for an edge-preserving map (homomorphism) to a fixed graph $H$. It improves upon the prior general kernel size bound of O($k^\Delta(H)$) by presenting two new kernelization algorithms: a combinatorial kernel whose size is governed by a structural property of $H$ (the non-adjacency witness number), yielding fixed polynomial-sized kernels for classes like planar graphs; and a linear-algebraic kernel that strengthens the general bound and is near-optimal for certain classes. These new upper bounds, combined with derived conditional lower bounds, nearly settle the kernel complexity of the $H$-coloring problem for various target graphs $H$.

בתורת החבורות, ישנה תוצאה קלאסית שמוכיחה שאם בחבורה $G$ ההסתברות ששני איברים מתחלפים (כלומר, $xy=yx$) היא יותר מ-5/8 (= 62.5%) אז החבורה אבלית (כלומר, כל שני איברים מתחלפים). בהרצאה, נוכיח תוצאה זו מתורת החבורות, נסקור בקצרה את תורת המבנה של "חבורות לא-אסוציאטיביות" הנקראות גם לולאות, ונוכיח גרסה של תוצאה זו ללולאות.

האפשרות להציג כל מספר שלם גדול מ-1 כמכפלת גורמים ראשוניים ויחידות הצגה זו היא אחת התוצאות היסודיות של האריתמטיקה, והשלכותיה המעשיות והמושגיות, על התפתחות המתמטיקה בכלל והאלגברה בפרט רחבות ועמוקות. ההרצאה תעסוק באופן מימושו של רעיון הפירוק הראשוני בתורת החבורות הסופיות, והיא מכוונת לשומעים אפלטוניים חסרי ידע מוקדם בחבורות. נפתח, כמתבקש, בהגדרת המושג חבורה. מוטיב הפירוק הראשוני מתחבר לשאלות מחקריות שהעסיקו וממשיכות להעסיק אותי, אך בחרתי להניח שאלות אלו בצד, לטובת דיון נינוח עם דוגמאות פשוטות ככל הניתן במקצת התוצאות הקלסיות בנושא הנ"ל. אם בכל זאת יישאר מעט זמן בסוף ההרצאה, אנצל אותו להצגת הקשר למחקר שלי.

ערכים עצמיים של מטריצות הם מהמושגים היותר פופולריים ושימושיים באלגברה. הם קשורים להפיכות, לכסון, חישוב חזקות גבוהות וסדרות נסיגה מבין הנושאים השונים. השאלה מה אפשר ללמוד עליהם במקרה הלא-חילופי מעסיקה מתמטיקאים לפחות במאה השנים האחרונות. נדבר על מגוון השאלות השונות, מה ידוע עליהן בספרות ומה חידשנו לאחרונה.

ההרצאה מבוססת חלקית על עבודה משותפת עם סולומון וישקאוצן (ממכללת תל-חי).

A function that maps between binary strings is called an isometric embedding from the Hamming metric space to the edit metric space if: for all input strings, the Hamming distance between them equals the edit distance between their corresponding output strings. The rate of such an embedding is defined as the ratio of the input length to the output length.

It is well known in the literature how to construct isometric embeddings with a rate of 1/log n, (where n is the input length). However, achieving even near-isometric embeddings with a positive constant rate has remained elusive until now.

In this talk, I will present an isometric embedding with a rate of 1/8 by discovering connections to synchronization strings, which were studied in the context of insertion-deletion codes (Haeupler-Shahrasbi~[JACM'21]). En route, we also improve the analysis of the construction of synchronization strings that appear in literature.

As an immediate consequence of our constant rate isometric embedding, we improve known conditional lower bounds for the several optimization problems over the edit metric with optimal dependency on the dimension.

At a technical level, we introduce a framework for obtaining high-rate isometric embeddings using a novel object called misaligners. We speculate that, with sufficient computational resources, our framework could potentially yield isometric embeddings with a rate of 1/5.

This is a joint work with: Sudatta Bhattacharya, Karthik C.S., Sanjana Day, Mursalin Habib, Bernhard Haeupler and Michal Koucký.

In distributed computing with rational agents, it is usally assumed that the network size $n$ is known in advance to all participants.

We show a general impossibily result when agents have no a-priori knowledge of $n$. For a wide range of problems and protocols, when agents have no a-priori knowledge of $n$, equilibrium is impossible.

The Uniform Information Density (UID) hypothesis posits that speakers optimize the communicative properties of their utterances by avoiding spikes in information, thereby maintaining a relatively uniform information profile over time. This paper investigates the impact of UID principles on syntactic reduction, specifically focusing on the optional omission of the connector "that" in English subordinate clauses. Building upon previous research, we extend our investigation to a larger corpus of written English, utilize contemporary large language models (LLMs) and extend the information-uniformity principles by the notion of entropy, to estimate the UID manifestations in the usecase of syntactic reduction choices.

One of the most interesting open questions in Galois theory these days is: Which profinite groups can be realized as absolute Galois groups of fields? Restricting our focus to the one-prime case, we begin with a simpler question: which pro-$p$ groups can be realized as maximal pro-$p$ Galois groups of fields?

For the finitely generated case over fields that contain a primitive root of unity of order $p$, we have a comprehensive conjecture, known as the Elementary Type Conjecture by Ido Efrat, which claims that every finitely generated pro-$p$ group which can be realized as a maximal pro-$p$ Galois group of a field containing a primitive root of unity of order $p$, can be constructed from free pro-$p$ groups and finitely generated Demushkin groups, using free pro-$p$ products and a certain semi-direct product.

The main objective of the presented work is to investigate the class of infinitely-ranked pro-$p$ groups which can be realized as maximal pro-$p$ Galois groups. Inspired by the Elementary Type Conjecture, we start our research with two main directions:

1. Generalizing the definition of Demushkin groups to arbitrary rank and studying their realization as absolute/maximal pro-$p$ Galois groups.

2. Investigating the possible realization of a free (pro-$p$) product of infinitely many absolute Galois groups.

In this talk we focus mainly on the second direction. In particular, we give a necessary and sufficient condition for a restricted free product of countably many Demushkin groups of infinite countable rank, to be realized as an absolute Galois group.

Historical manuscripts serve as invaluable windows into past civilizations, preserving knowledge, culture, and traditions. However, their analysis presents significant challenges due to factors such as physical degradation, complex writing styles, and non-standard text layouts. One particularly intricate case is the study of Aramaic incantation bowls, where text is often inscribed in spiral formations. Another major challenge lies in the study of palimpsests—manuscripts that have been erased and overwritten—where reconstructing the original text requires advanced computational methods to separate and recover obscured layers of writing.

This research introduces AI-driven methods for detecting and aligning text lines in historical documents, focusing on incantation bowls and reconstructing erased texts in palimpsests. By employing deep learning and image processing techniques, the study enables precise segmentation, structure recognition, and content restoration. These advancements contribute to the broader field of digital humanities, offering tools to enhance the readability and interpretation of historical texts, thereby unlocking new insights into the past.

Fix $g \in \mathbb{N}$ such that $g$ is not a perfect square. Artin's primitive root conjecture (1927) states that there exist infinitely many primes $p \in \mathbb{N}$ such that $g$ generates the finite cyclic group $(\mathbb{Z}/p\mathbb{Z})^{\times}$. Nearly a century later, Artin's conjecture remains wide-open: in fact there is no known specified $g$ for which the conjecture has been resolved. In this talk, we survey the interesting history of Artin's conjecture and introduce several new variants to the problem. Specifically, we discuss an "Artin Twin Primes Conjecture"; and prove an appropriate analogue of Artin's conjecture for algebraic function fields (with potential applications to LFSRs).

What connects efficient data storage, minimizing network transmissions, and the royal crown? In this talk, I will describe two computational problems from coding theory – Storage Capacity and Index Coding – and discuss efficient algorithms for certain instances of them. To achieve this, we will adopt the approach of parameterized complexity, with the royal crown playing a surprising role.

In the last decade, the theory of high dimensional expanders has emerged and already found a wide variety of applications throughout theoretical computer science. Some of the results include major breakthroughs in the construction of size-efficient PCPs with small soundness, fast mixing of markov chains, and better classical and quantum error correcting codes.

In this talk I will present high dimensional expanders and some of their applications. This talk will contain an exposition of the main ideas of some of my works - The introduction of high dimensional random walks, and the notions of agreement expansion and cosystolic expansion.

Large Language Models (LLMs) are emerging as transformative tools in the security domain, with new tasks reshaping the landscape of threat detection, response, and prevention. In this research, we suggest using LLMs to fight against increasingly sophisticated cyber threats - scams. LLMs can analyze vast amounts of data in real time to identify and mitigate scams such as phishing, financial fraud, and fake social media accounts with greater speed and accuracy than traditional methods. The importance of LLMs lies in its ability to proactively safeguard sensitive data, reduce financial losses, and enhance trust in digital platforms. Furthermore, we evaluate the success of LLMs in scam detection from different dimensions, such as model size, temperature, top-p, and prompting style. Then, we fine-tune these models to show their true potential. Scam detection using LLMs is revolutionizing the fight against increasingly sophisticated cyber threats.

כתיבת בחינה טובה שמעריכה נכונה את הידע של הסטודנטים והמיומנויות שלהם היא אחת המשימות החשובות של כל מרצה. פורמט המבחן וסוג השאלות בו משפיעים על הדרך בה תלמידים לומדים לאורך כל הקורס, ובחינה מתוכננת היטב יכולה לשפר למידה משמעותית.

אנו מתייחסים לנושא זה בהקשר של הקורסים מבני נתונים ואלגוריתמים, אם כי בהחלט ייתכן שהדבר רלבנטי לקורסים נוספים, בעיקר בתאוריה, וטוענים כי בחינה טובה צריכה להכיל שאלות שהסטודנטים ראו במהלך הסמסטר, כולל פתרון, וכמו כן שהניקוד של שאלות אלו צריך להיות קפדני.

ערכנו מחקר במשך שלושה סמסטרים, שתומך בטענה כי מענה על שאלות כאלו מצריך הבנה (רמה 2 בטקסונומיה של בלום), וכי אסטרטגיה זו מעודדת למידה משמעותית יותר ומעריכה טוב יותר את הידע של התלמידים.

כמו כן, סטודנטים מרגישים שהמבחן הוגן, אף על פי שבדרך כלל אין שינוי באחוזי הנכשלים.

Every group carries a natural topological boundary called the Furstenberg boundary, which is crucial for understanding the group, its actions, and some related operator algebras. Furstenberg presented in the 60s a realization of his boundary in case the group is a semisimple connected Lie group. However, in the orthogonal world of discrete groups, the boundary has admitted no realization until now. In this talk, I will present such a realization in terms of a related Boolean algebra consisting of certain kinds of “large” subsets of the group and show how this relates to amenability and strong amenability and certain decomposability properties of the group. I will also explain how these ideas solve the “dense orbit set” problem of Glasner, Tsankov, Weiss, and Zucker. If time permits, I will also tell you about the Lie case and explain how the Furstenberg boundary is related to higher-rank phenomena.

The talk is based on joint work with Matthew Kennedy and Sven Raum, ongoing work with Ariel Yadin, and ongoing work with Uri Bader.

We present a novel framework for uncertain data management. We start with a database whose tuple correctness is uncertain and an oracle that can resolve the uncertainty, i.e., decide if a tuple is correct or not. Such an oracle may correspond, e.g., to a data expert or to a crowdsourcing platform. We wish to use the oracle to clean the database with the goal of ensuring the correct answer for specific mission-critical queries. To avoid the prohibitive cost of cleaning the entire database and to minimize the expected number of calls to the oracle, we must carefully select tuples whose resolution would suffice to resolve the uncertainty in query results. In other words, we need a query-guided process for the resolution of uncertain data.

We develop an end-to-end solution to this problem, based on the derivation of query answers and on correctness probabilities for the uncertain data. At a high level, we first track Boolean provenance to identify which input tuples contribute to the derivation of each output tuple, and in what ways. We then design an active learning solution for iteratively choosing tuples to resolve, based on the provenance structure and on an evolving estimation of tuple correctness probabilities. We conduct an extensive experimental study to validate our framework in different use cases.

Merging the predictions of multiple experts is a frequent task. When ground-truth response values are available, this merging is often based on the estimated accuracies of the experts. In various applications, however, the only available information are the experts’ predictions on unlabeled test data, which do not allow to directly estimate their accuracies. Moreover, simple merging schemes such as majority voting in classification or the ensemble mean or median in regression, are clearly sub-optimal when some experts are more accurate than others. Focusing on regression tasks, in this work we propose U-PCR, a framework for unsupervised ensemble regression. Specifically, we develop spectral-based methods that under mild assumptions and in the absence of ground truth data, are able to estimate the mean squared error of the different experts and combine their predictions to a more accurate meta-learner. We provide theoretical support for U-PCR as well as empirical evidence for the validity of its underlying assumptions. On a variety of regression problems, we illustrate the improved accuracy of U-PCR over various unsupervised merging strategies. Finally, we also illustrate its applicability to unsupervised multi-class ensemble learning.

We explore the notion of a program “size” in various settings. Once a size of a program is properly defined, reducing that size may sometimes induce a “smaller” equivalent program that is easier to analyze. For instance, inverting string procedures might be an easier task, when the underlying alphabet is not the entire set of characters, but rather a smaller, “representative” set. Another example involves the equivalence of hand written string loops to string library functions. Proving such equivalence for loops encountered in the wild is tricky. However, somewhat often, these handwritten loops have an interesting size-agnostic property, which justifies equivalence checks only on strings of constant length. The bounded checks then become feasible. Generalizing the reduction principle, showing it can be repeatedly applied to formulate a novel kind of “induction on space” to prove program specifications. This new induction is in a sense orthogonal to the standard “induction on time” applied via loop invariants in many frameworks. Evidently, this approach was able to automatically prove program specifications that were out-of-reach for existing tools. Last, the concept of repeated size reduction was extended, so that it can support several reductions (rather than just one). This broader viewing angle allowed reasoning about computational complexity of programs that failed automatic complexity classification before.

This presentation will focus extensively on GitHub Copilot, an AI-powered coding assistant, exploring its advanced features, usability, and the profound impact it has on developer efficiency. These new GenAI technologies are reshaping the industry with their advanced capabilities in enhancing coding efficiency and offering conversational coding experiences. We will delve into the nuances of GitHub Copilot Chat, discussing its conversational coding capabilities and its significance in streamlining coding processes. The session will include demonstrations, highlighting how these tools are revolutionizing the coding landscape and their potential applications in academic and professional settings

Modular forms are fundamental objects in modern number theory, which allow us to relate geometric objects and arithmetic ones. Recent advances towards several long standing conjectures depend crucially on explicit computation of these objects.

In this talk, we will present novel algorithms that achieve this goal and some of their applications.

Prominent questions about the role of sensory vs. linguistic input in the way we acquire and use language have been extensively studied in the psycholinguistic literature. However, the relative effect of various factors in a person's overall experience on their linguistic system remains unclear. We study this question by making a step forward towards a better understanding of the conceptual perception of colors by color-blind individuals, as reflected in their spontaneous linguistic productions. Using a novel and carefully curated dataset, we show that red-green color-blind speakers use the "red" and "green" color terms in less predictable contexts, and in linguistic environments evoking mental image to a lower extent, when compared to their normal-sighted counterparts. These findings shed some new and interesting light on the role of sensory experience on our linguistic system.

This lecture will explore the concept of time-encoding for continuous-time signals as an alternative to Shannon sampling. In time-encoding, signals are encoded using a sequence of time instants corresponding to an event. The presentation will focus on integrate-and-fire time encoding machines (IF-TEMs), which offer a power-efficient method for signal sampling without requiring a global clock. This lecture will cover theoretical guarantees for recovery of finite rate of innovation (FRI) inputs, as well as propose a modified sampling approach for robust recovery in the presence of noise. Additionally, the effect of quantization will be investigated for IF-TEM and conventional samplers for FRI and bandlimited signals, showing that quantization using IF-TEM improves the recovery of FRI and bandlimited signals in comparison with classical uniform sampling in the Fourier-domain and Nyquist methods.

The lecture is designed to be accessible to those without prior knowledge of signal processing.

We investigate the minimum set of vertices required to take over a network under majority dynamics. We demonstrate that in typical networks, this set must be relatively large, scaling linearly with the size of the network. However, we also identify special cases where the bound on the size of the set is significantly smaller. Additionally, we discuss the specific vertices that make up this minimal influential set.

Joint with Itai Arieli, Galit Golan-Ashkenazi.

בשנים האחרונות חל גידול במה שמכונה "מדעי הרוח הדיגיטליים", חקר מדעי הרוח באמצעות כלים חישוביים. מחקרי הנוכחי, שאת הרעיון מאחוריו אציג בסמינר, בוחן תהליכי האחדה ופירוד בחברה האמריקאית במאה ה-19 באמצעות ניתוח קורפוס נרחב של מאות אלפי גיליונות של עיתונים אמריקאים בין 1840 ל -1884. המחקר מיישם מספר גישות וטכניקות חישוביות לצורך זיהוי ואפיון המבנה, התכנים והדינמיקה של הרשתות העיתונאיות באמריקה. בין השאר, אנו משתמשים בכלים שפותחו לזיהוי מקוריות (plagiarism detection) כדי לאתר שימוש חוזר בטקסטים ובמידול נושאי (topic modeling) כדי לזהות צבירים (clusters) של תוכן בזמן ובמרחב. התוצאה הכוללת היא רשת רשת קשרים בין עיתונים בזמן ובמרחב, שתאפשר לזהות את הכיוון והקצב של זרימת חדשות. מחקר זה זכה השנה במענק ארבע שנתי של הקרן הלאומית למדעים (ISF)

מעבר לשאלות ההיסטוריות הצצות במחקר זה, הקשורות ביחסי הגומלין בין התקשורת האמריקאית עם התפתחויות פוליטיות, אידיאולוגיות, חברתיות וטכנולוגיות, ישנן שאלות רבות הקשורות למדעי הנתונים. כיצד מעבדים יחד את המשתנים הרבים הקשורים לרשת זו, כיצד מייצגים את הרשת וקשריה, וכיצד מבצעים את המעבר בין ה-data להבנה ההיסטורית.

בסמינר אציג את שתי המתודות (זיהוי מקוריות ומידול נושאי) ואת התועלת שלהן לחקר רשתות עיתונות היסטורית. במקביל, אציג את הקשיים הנובעים מיישום של כלים חישוביים לחקר ההיסטוריה.

Motivated by machine learning applications, much research over the last decade was devoted to solving submodular maximization problems under Big Data computational models. Perhaps the most basic such problem is the problem of maximizing a submodular function subject to a cardinality constraint. A recent series of papers has studied this problem in the data stream model, and in particular, fully determined the approximation ratio that can be obtained for it by (semi-)-streaming algorithms both when the objective function is monotone and non-monotone. In this talk we will survey the main ideas behind these tight results.

Based on joint works with Naor Alaluf, Alina Ene, Huy Nguyen, Ashkan Norouzi-Fard, Andrew Suh, Ola Svensson and Rico Zenklusen.

Quantum computers are at an active stage of research and development that may eventually lead to their practical realization, with potential impact on many fields from chemistry and medication, to financial risk analysis and AI. In this talk, we will review the basic concepts of quantum computing: qubits, measurements, quantum gates, quantum circuits, superposition, entanglement etc, and briefly present IBM's quantum software and hardware roadmap.

We will focus on our IBM Quantum Israel team research and open-source code contribution in experimentalists tools and efficient quantum circuit synthesis.

Dr. Shelly Garion is a researcher at IBM Research Israel at the Quantum Computing group, and a contributor to Qiskit open-source

Allocating the right amount of resources to each service in any of the datacenters in a cloud environment is a very difficult task. This task becomes much harder due to the dynamic nature of the workload and the fact that while long term statistics about the demand may be known, it is impossible to predict the exact demand at each point in time. As a result, service providers either over allocate resources and hurt the service cost efficiency, or run into situations where the allocated local resources are insufficient to support the current demand. In these cases, the service providers deploy overflow mechanisms, such as redirecting traffic to a remote datacenter or temporarily leasing additional resources (at a higher price) from the cloud infrastructure owner. The additional cost is in many cases proportional to the amount of overflow demand.

In this work we study this approach and develop a novel mechanism to assign services to datacenters based on the available resources in each datacenter and the distribution of the demand for each service. We use comprehensive analysis to prove that the overall overflow cost is almost optimal for arbitrary demand distributions, as long as there are no dependencies among the services. We further show, using simulation based on real data, that the scheme performs very well on realistic service workloads.

In recent years reactive synthesis from temporal logic specifications has attracted much research interest. Synthesis aims to automatically produce correct by construction models, circuits, implementations, etc. from specifications. In this talk we focus on reactive synthesis from temporal logic specifications. Reactive synthesis creates reactive systems, i.e., systems that receive inputs and produce outputs at every computation step, and are expected to run indefinitely. We focus also on GR(1) specifications. GR(1) is an expressive fragment of Linear Temporal Logic (LTL) that allows efficient synthesis. Several synthesis tools exist for GR(1) with many applications, including industrial ones.

Writing correct and complete formal specifications, reading and understanding formal specifications, and repairing them as needed, are all very challenging tasks. Thus, synthesis in itself is not enough, and tools for assisting engineers in these tasks are essential. These tools must also be efficient enough to deliver results in reasonable time.

We present two works that deal with unrealizability, the case where specifications have no correct implementation. The first work localizes causes for unrealizability. The second work automatically repairs unrealizable specifications. Finally, we will briefly discuss two other works that improve the quality of specifications and synthesized controllers, by locating, explaining, and removing redundant specification elements.

In many real-life scenarios, a group of agents needs to agree on a common action, e.g., on a location for a public facility, while there is some consistency between their preferences, e.g., all preferences are derived from a common metric space. The facility location problem models such scenarios, and it is a well-studied problem in social choice. We study mechanisms for facility location on unweighted undirected graphs that are resistant to manipulations (strategy-proof, abstention-proof, and false-name-proof) by both individuals and coalitions on one hand and anonymous and efficient (Pareto-optimal) on the other. We define a new family of graphs, ZV-line graphs, and show a general facility location mechanism for these graphs that satisfies all these desired properties.

This mechanism can also be computed in polynomial time, and it can equivalently be defined as the first Pareto-optimal location according to some predefined order. Our main result, the ZV-line graphs family and the mechanism we present for it, unifies all works in the literature of false-name-proof facility location on discrete graphs, including the preliminary (unpublished) results we are aware of. In particular, we show mechanisms for all graphs of at most five vertices, discrete trees, bicliques, and clique tree graphs.

Finally, we discuss some generalizations and limitations of our result for facility location problems on other structures: Weighted graphs, large discrete cycles, infinite graphs, and facility location problems concerning infinite societies.

Major features of bilingualism, including grammatical, cognitive, and social aspects, have been extensively studied by scholars for over half a century. Crucially, much of this research has been conducted with small, carefully-curated datasets or in a laboratory experimental setup. Nowadays, the ubiquity of English as an online lingua franca offers a rich opportunity for computational research on second language acquisition and on tools for aiding non-native speakers. The availability of large and diverse datasets stimulates new opportunities for pursuing the emerging direction of computational investigation of bilingualism, thereby tying empirical results with well-established theoretical foundations.

I tackle empirical tasks motivated by theoretical hypotheses on second language acquisition, leveraging linguistic insights and foundations into practical value through applications in the area of second-language education. My main focus lies in developing robust and practical tools for better understanding, more accurate modeling and processing of the language of advanced, highly proficient non-native speakers – a population that has enjoyed very little attention in computational investigation thus far.

Indicators reduce costs in caching systems by allowing a user to select which cache to query for the desired datum. Such indicators are used in large-scale systems, such as content delivery networks, 5G networks, and information-centric networks.

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.

Our work targets the problem of minimizing costs while satisfying bandwidth constraints. To this end, we develop lightweight, dynamic, auto-adjusting algorithms for both the cache and user sides. Using rigorous mathematical analysis, we provide performance guarantees for our algorithms. Our extensive evaluation study, based on real-world cache traces, shows a significant improvement over existing approaches.

Imagine being able to prove the correctness of massive computations while only communicating a few bits. Such schemes can be used to solve many of the challenges of the modern online world. Formally, these schemes are known as Succinct Non-interactive ARGuments (SNARGs): a proof system that lets a prover convince a verifier about the truthfulness of a statement via a single short message.

In a seminal work, Micali (FOCS 1994) gave the first succinct non-interactive argument in the random oracle model (ROM). The construction is elegant and compiles an information-theoretic PCP and a cryptographic commitment scheme. The resulting SNARG has many attractive features: it is fast, requires no setup, and satisfies post-quantum security. However, it also has one major drawback: a large (quadratic) argument size.

Are all SNARG constructions in the random oracle model inherently large? The answer to this question is still open, and I will survey recent work that makes significant progress towards a solution. In particular, we will see a new construction that achieves a smaller argument size. This is the first progress on the Micali construction since it was introduced over 25 years ago. Our construction relies on a strong soundness notion for PCPs and a weak binding notion for commitments. We hope that our work paves the way for understanding if a linear argument size is achievable in the ROM.

The talk is based on several joint works with a set of authors including Alessandro Chiesa, Daniel Nukrai, and Iftach Hairner.

Deep Learning has revolutionized Artificial Intelligence in the past years. At Mobileye, Deep Learning lies at the core of our computer vision system, allowing cars to drive autonomously in Israel and around the world. In the talk I will present in detail the computer vision and machine learning systems that are used in Mobileye, and discuss how developments in Mobileye are driving some academic progress on the fundamentals of Deep Learning.

Project Debater is the first AI system that can meaningfully debate a human opponent. The system, an IBM Grand Challenge, is designed to build coherent, convincing speeches on its own, as well as provide rebuttals to the opponent's main arguments. In 2019, Project Debater competed against Harish Natarajan, who holds the world record for most debate victories, in an event held in San Francisco that was broadcasted live world-wide. In this talk we will tell the story of Project Debater, from conception to a climactic final event, describe its underlying technology, and discuss how it can be leveraged for advancing decision making and critical thinking.

Arithmetic dynamics is a relatively new field of research. The goal is to study number theoretic properties of classical dynamical systems. The problems in this area are varied, from counting numbers of rational periodic points to Galois actions on orbits. The tools required for research in arithmetic dynamics are also quite varied as it lies in the intersection of analytic and algebraic number theory, arithmetic geometry and classical dynamical systems. In this lecture we discuss recent progress in the field, and some of our recent results.

The orthogonality dimension of a graph is the smallest integer $t$ for which one can assign to every vertex a nonzero vector in $R^t$ so that adjacent vertices in the graph receive orthogonal vectors. The Kneser graph $K(d,s)$ is the graph whose vertices are all the $s$-subsets of a universe of size $d$, where two sets are adjacent if they are disjoint.

In the talk, I will discuss the (generalized) orthogonality dimension of (generalized) Kneser graphs, and present several applications in theoretical computer science and information theory.

A subset of the integer planar grid $[N] \times [N]$ is called corner-free if it contains no triple of the form $(x,y)$, $(x+\delta,y)$, $(x,y+\delta)$. It is known that such a set has a vanishingly small density, but how large this density can be remains unknown. The best previous construction was based on Behrend's large subset of $[N]$ with no 3-term arithmetic progression. Here we provide the first substantial improvement to this lower bound in decades. Our approach to the problem is based on the theory of communication complexity.

No previous knowledge needed.

(Joint work with N. Linial)

In every complex system, faults can occur. Detecting faults, in many cases, is the first step in dealing with them. In this work, we focus on efficient detection of faults in distributed networks. A distributed network is a set of interconnected processors. We consider a standard message-passing model of distributed computation, where there is no central control or shared memory, and processors communicate only by sending messages on communication links in synchronous rounds. Distributed verification has received much attention over the years due to its applications to various domains. For example, checking the results obtained from the execution of a distributed program, constructing self-stabilizing algorithms, and developing a distributed complexity theory inspired by the sequential complexity theory.

In this work, we address the problem of locally verifying global properties of the network, and we study the effect of different network resources and relaxations on the complexity of verification. In particular, we first show that using randomization reduces the communication complexity exponentially. Also, approximations can significantly reduce space and communication complexity. The ability to send a different message on each link is a crucial factor which can greatly reduce the communication complexity of verification as well. Finally, we show that using multiple communication rounds can sometimes reduce space complexity even more than linearly in the number of rounds.

In many algorithms used in computing environments such as massive storage devices, large scale parallel computation, and communication networks, recovering from failures must be an integral part. Therefore, designing algorithms and data-structures whose running time is efficient even in the presence of failures is an important task. In this talk I will present variants of shortest path algorithms and data-structures in setting with failures. A replacement path $P(s,t,e)$ is a shortest path from $s$ to $t$ that does not go through $e$. I will present, at a high level, the results I obtained during my PhD for efficiently computing replacement paths [SODA 2019, ICALP 2019], as well as efficiently constructing compact data-structures for answering replacement paths/distance queries [SODA 2017, STOC 2020]. Then, I will deep-dive into the analysis of one of these results.

I will also present some results obtained during my postdoc in multiple research areas. Motivated by COVID-19 I researched network dynamics and developed a model for the spread of infection in social networks that is motivated by some properties from COVID-19 spreading. I will also present a project in which I developed face-detection deep neural networks that classifies faces as either wearing or not-wearing face-masks, as part of a new "competitive programming with deep learning" course that I lecture.

Feature hashing, also known as the hashing trick, introduced by Weinberger et al. (2009), is one of the key techniques used in scaling-up machine learning algorithms. Loosely speaking, feature hashing uses a random hashing of the entries of an $n$-dimensional $x$ in order to reduce the dimension of the data from $n$ to $m$ (where $m<<n$), while approximately preserving the Euclidean norm. Weinberger et al. showed tail bounds on the norm of the new vector. Specifically they showed that if an $n$-dimensional vector $x$ is sufficiently "balanced", and the target dimension $m$ is sufficiently large, then the norm of the hashed vector approximates the norm of x with high probability. These bounds were later extended by Dasgupta et al. (2010) and most recently refined by Dahlgaard et al. (2017), however, the true nature of the performance of this key technique, and specifically the correct tradeoff between the pivotal parameters (how "balanced" $x$ is, and what are the constraints on the error) remained an open question. We settle this question by giving tight asymptotic bounds on the exact tradeoff between the central parameters, thus providing a complete understanding of the performance of feature hashing. We complement the asymptotic bound with empirical data, which shows that the constants "hiding" in the asymptotic notation are, in fact, very close to $1$, thus further illustrating the tightness of the presented bounds in practice.

(Joint work with Casper Freksen and Kasper Green Larsen)

These days, more than ever, we deal with huge graphs such as social networks, communication networks, roadmaps and so forth. But even when our main interest is only in a small portion of the input graph $G$, we still need to process all or most of it in order to answer our query, since the runtime and memory requirements of many common graph algorithms depend on the input (graph) size. Therefore, a natural question is whether we can find a vertex sparsifier $H$, which is a smaller graph that exactly (or approximately) preserves some properties of the original graph such as distances, cuts and flows. This talk presents the state of the art results of vertex sparsifiers for planar graphs, and further refines these bounds by a topological parameter called the terminal face cover.

In recent years, there is a growing interest in distributed algorithms for networks in which the participants are not faulty but rational, and may deviate from the prescribed algorithm in order to increase their profit. Until now, these distributed algorithms for rational agents have assumed a-priori knowledge of the size of the network.

We generalize the game-theoretic model of distributed computing and present basic building blocks that are in equilibrium, i.e., where no agent can profit by cheating. We then challenge this assumption by proving that, without a-priori knowledge of the network size, there is no equilibrium for many different distributed computing problems.

שדות הם אובייקטים מרכזיים באלגברה ומתמטיקה בכלל, ושדות שונים משרתים מודלים שונים בפיזיקה, מדעי המחשב והנדסה בהתאם לתכונות האריתמטיות שלהם. אחת הדרכים לאפיין את התכונות האריתמטיות של שדות היא על-ידי אינווריאנטים, כגון אינווריאנט יו הקובע את האורך המקסימלי של תבנית ריבועית ללא אפסים לא טריוויאליים מעל השדה. בהרצאה הזאת נדון באינווריאנט יו של שדות שונים ובאינווריאנטים חדשים ועדינים יותר שנועדו להפריד בין שדות עם אינווריאנט יו זהה.