​Title​

​​​​Abstract​​

Lecturer: Idan Attias
Host: Omri Azencot​

Our learning framework extends the traditional PAC learning model to address the challenges posed by adversarial attac​ks.

Within this framework, we investigate statistical and algorithmic aspects of classification and regression for both supervised and semi-supervised settings.

Along the way, we develop general techniques of potential interest to the statistical learning theory community, including estimates on complexity measures for aggregation rules of function classes and sample compression schemes.

This seminar presents an in-depth exploration of adversarial attacks, defenses, and robustness in deep neural networks. The key contributions include: 

• Evolutionary Gradient-Free Black-Box Attack: A query-efficient algorithm designed for generating adversarial instances in convolutional neural networks without relying on gradients. This method optimizes adversarial attacks in a black-box setting.
• Foiling Explanations in Neural Networks: Investigates the vulnerability of neural network explanations to adversarial manipulation, demonstrating how model interpretability can be compromised.
• Patch of Invisibility: Introduces a naturalistic black-box adversarial attack that successfully bypasses object detectors using visually inconspicuous patches, challenging the robustness of detection models.
• Gray-Box Attack on Image-to-Text Models: Explores the adversarial weaknesses of multimodal models, specifically targeting image-to-text systems using a gray-box approach.
• Universal Black-Box Jailbreaking of LLMs: Proposes an attack methodology that universally bypasses the safety mechanisms of large language models, highlighting potential security risks in natural language processing.
• XAI-Based Detection of Adversarial Attacks: Utilizes explainable AI techniques to detect adversarial attacks on deepfake detectors, reinforcing the defenses of AI models against synthetic media threats.
• Fortify the Guardian, Not the Treasure: Suggests a novel strategy for adversarial training, focusing on enhancing the resilience of adversarial detectors rather than the primary models, thereby strengthening security in adversarial scenarios.

Robustness of Kolmogorov-Arnold Networks: Analyzes the robustness of Kolmogorov-Arnold Networks (KANs) compared to traditional multilayer perceptrons (MLPs) under various white-box adversarial attacks, offering insights into their potential as a more resilient neural network architecture.​

The thesis supervised by Prof. Moshe Sipper

Abstract: In 1982, Boros and Füredi, then undergrad students in Budapest, established the following result, which became known as the First Selection Lemma: 
Let P be a set of n points in the Euclidean plane. Then one can always choose a point piercing almost an 2/9-fraction of all triangles that are spanned by P.
The result has been generalized in a number of ways, and underlies the modern notion of "geometric expanders".​

We will focus on the so-called Second Selection Lemma -- a particularly powerful statement dealing with arbitrary simplicial hypergraphs in Euclidean spaces of arbitrary albeit fixed dimension d, which was established in 1990 by Alon, Bárány, Füredi and Kleitman. Its most significant by-product is the first non-trivial bound for the famous Halving Plane problem of  Erdős and Lovász, which asks for the maximum number of ways a 2n-point set can be split by a plane into two parts of size n. Answering this question is quintessential for the analysis of many geometric algorithms. 

https://en.wikipedia.org/wiki/K-set_(geometry)

We will discuss the recent dramatic improvement in the exponent of the Second Selection Lemma, which immediately results in a sharper bound for halving planes in all Euclidean spaces of dimension 5 or higher. In contrast to the previous argument of Alon et al, the new bound is more intuitive, and derives from fairly general properties of geometrically defined hypergraphs.

Progress in Large Language Models (LLMs) has helped improve performance on this challenging task, but dealing with complex questions remains challenging even for very large models.

We propose a method based on the decomposition of complex SQL queries according to their operational semantics. We introduce an intermediary representation for SQL queries which is derived from the hierarchical execution plan of the query that we call Query Plan Language (QPL).  

We show that LLMs fine-tuned to learn how to map questions to QPL perform better than when generating SQL directly, especially for complex queries.

In this talk, I will present additional followup ongoing results that exploit the hierarchical nature of QPL programs to better translate questions into complex queries.

In the first experiment, we evaluate an ensemble model learning different syntactic variants for QPL and how LLMs learn to combine these different views.

In the second experiment, we analyze a recursive decomposition-composition strategy for complex questions. We exploit the QPL dataset we constructed to derive decompositions of questions into simpler natural language questions grounded in the semantics of the data retrieval operations. An LLM fine-tuned to perform question decomposition is then combined at inference time with a recursive question to QPL system.

Preliminary results indicate the potential of this modular approach to address complex semantic parsing tasks, with performance on standard text to SQL benchmark moving from ~75% to about 88% with a small 3B parameters LLM. 

I will conclude with considerations about reasoning and LLMs and how they relate to the general principle of​

In this work, we introduce a new type of regularity lemma dubbed "spread regularity". Its main advantage is that the number of parts it requires is even smaller, merely quasi-polynomial in the error parameter. Translating from graphs to their adjacency matrices, we show that while individual spread matrices are not very "random looking", the product of two such matrices is very close to uniform.

We give two applications of our new spread regularity lemma. The first application is in communication complexity, where we construct an explicit function with a near optimal separation between randomized and deterministic protocols in the 3-player Number-On-Forehead model. The second application is in algorithms, where we design a combinatorial algorithm for matrix multiplication with a quasi-polynomial speedup over the naive algorithm.

Based on joint works with Amir Abboud, Nick Fischer, Zander Kelley and Raghu Meka.

Bio:  Shachar Lovett is a professor at UC San Diego. He has a broad interest in theoretical CS and combinatorics, with emphasis on structure and randomness, coding theory, algebraic constructions, and additive combinatorics. He is a recipient of an NSF career award, a Sloan fellowship and a Simons investigator award.

Natural language processing (NLP) has been revolutionised in recent years to the point where it is an inseparable part of our daily lives. The transition to transformer-based models allows us to train models on vast amounts of text efficiently, proving that scale plays a crucial role in improving performance. Unfortunately, many people worldwide are marginalised from getting access to high-quality NLP models, as the language they speak and the domains they are interested in count for only a tiny fraction of current state-of-the-art models' training sets.
This talk will address the challenges, approaches, and opportunities for democratising NLP across different languages and domains by developing methods to improve NLP in low-resource scenarios. I will start by discussing how we can ease distribution mismatches to improve performance using representation learning.
However, as NLP models become increasingly present in our lives, improving other crucial aspects beyond their performance, such as their fairness, factuality, and our ability to understand their underlying mechanisms, is essential.
Therefore, I will also discuss using spectral methods to remove information from neural networks to reduce undesired attributes, such as bias, to increase fairness where sensitive data is scarce.
Finally, I will explore future directions for making these models accessible to a broader audience by improving the aspects mentioned above in low-resource scenarios.

Bio:Yftah Ziser is a Postdoctoral Researcher at the School of Informatics at Edinburgh University, hosted by Shay Cohen.
He focuses on Deep-Learning methods for dealing with the resource bottleneck, which seriously challenges the worldwide accessibility of NLP technology.
His research develops methods to improve low-resource models' performance, fairness, and factuality while developing analysis methods for deepening our understanding of them.
He co-organised the Domain Adaptation for NLP Workshop at EACL 2021.
Before joining the University of Edinburgh, Yftah worked as a research scientist at Amazon Alexa. Yftah obtained his PhD from the Technion, where Roi Reichart advised him.

With the aim of verifying program correctness, the two major challenges are (1) providing a specification language that can precisely express the desired properties; and (2) providing scalable verification algorithms. In this talk, I will give an overview of my recent work on addressing these two challenges. 

First, I will present the new logic Hyper^2LTL, which uses second-order quantification over sets of executions to express a wide range of complex hyperproperties such as common knowledge in multi-agent systems and asynchronous hyperproperties.

Second, I will present a (sound but necessarily incomplete) model-checking algorithm for Hyper^2LTL; While the verification of Hyper^2LTL is undecidable, we manage to handle undecidability by characterizing a rich fragment of the logic that allows for sound approximations, providing the first verification algorithm for Hyper^2LTL specifications. ​

Bio: Hadar Frenkel is a postdoctoral researcher at CISPA Helmholtz Center for Information Security in Saarbrücken, Germany, hosted by Prof. Bernd Finkbeiner. She obtained her PhD from the Technion, Israel Institute of Technology, in 2021, under the supervision of Prof. Orna Grumberg and Dr. Sarai Sheinvald. Hadar studies complex hyperproperties, such as knowledge, causality, and asynchronous hyperproperties, and searches for logical formalisms and verification algorithms for them. She also studies automata learning and its applications in program verification and repair.

 Based on joint work with Constantinos Daskalakis, Anthimos Vardis Kandiros, Nishanth Dikkala, Siddhartha Jayanti, Surbhi Goel and Davin Choo.

Bio: Yuval Dagan is a postdoctoral researcher at the Simons Institute for the Theory of Computing at UC Berkeley and at the Foundations of Data Science Institute (FODSI). He received his PhD from the Electrical Engineering and Computer Science Department at MIT, advised by Professor Constantinos Daskalakis (2018-2023). He received his Bachelor's and Master's degrees from the Technion, where he was advised by Professor Yuval Filmus (2011-2017). During his PhD, he received the Meta Research Fellowship in Machine Learning (2021-2022). Further, he was a visitor of the Simons Foundation at the Causality program (2022) and a research intern at Google Mountain View, hosted by Vitaly Feldman (2019). Prior to his PhD, he was a research assistant of Professor Ohad Shamir at Weizmann Institute (2018).​

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.

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/​

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.

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.​

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.  ​

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.

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).​

​Methods for Computer-Assisted Linearizability Verification of Implementations of Concurrent Data Structures

Presenter: Avi Hayoun

​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

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.

​Scalable Bayesian Nonparametric Mixtures for Computer Vision and Deep Learning

By: Or Dinari

(Host: Oren Freifeld)

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 ​Re​cord​​ing​​

​Implicit bias in machine learning

By: Ohad Shamir

(Host: Aryeh Kontrovich)

New Directions in Derandomization: Non-Black-Box Techniques, Superfast Algorithms

By: Roei Tell

(Host: Yuval Pinter)

​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 ​Record​​ing​​

Projection Methods, Superiorization and Applications​

By: ​Aviv Gibali
(Host: Dr. E​ran Treister)

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.
​

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.

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).

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.​