Events

As machine learning models get more complex, they can outperform traditional algorithms and tackle a broader range of problems, including challenging combinatorial optimization tasks. However, this increased complexity can make understanding how the model makes its decisions difficult. Explainable models can increase trust in the model’s decisions and may even lead to improvements in the algorithm itself. Algorithms like GradCAM or SHAP provide good explanations in terms of feature importance, typically for classification tasks. Still, they provide little insight when the ML pipeline is designed to work, for example, as an algorithm for solving optimization problems.                                                                      In this talk, we present a concept-learning framework for explaining a neural machine-learning model’s decision-making process from an algorithmic point of view. Using the NeuroSAT algorithm for SAT solving as a case study, we demonstrate how our framework finds the algorithmic concepts that drive the operation of NeuroSAT. Using the concepts that we discover, we can re-write the black box NeuroSAT net as a text-book algorithm that performs typical algorithmic moves like (a) compute confidence levels for every variable, (b) fix variables with the highest confidence and simplify the instance, (c) solve the residual formula using some simple technique. (Such a principle guides, for example, the well-known Belief-Propagation-Decimation algorithm).

Joint work with Elad Shoham (PhD student BGU), Kahalil Wattad (MSc student BGU), Hadar Cohen (MSc student BGU), and Havana Rika (Tel-Aviv-Yafo Academic College). 

Short bio:

Dan Vilenchik holds a PhD in computer science from Tel Aviv University. He did a postdoc at UC Berkeley and UCLA. He is currently a tenured member of the Electrical Engineering School at Ben-Gurion University. His research includes various aspects of machine learning, such as the challenges of high-dimensional data, explainable AI, NLP, and multidisciplinary projects.

The statistical study of human memory requires large-scale experiments, involving many stimuli conditions and test subjects. While this approach has proven to be quite fruitful for meaningless material such as random lists of words, naturalistic stimuli, like narratives, have until now resisted such a large-scale study, due to the quantity of manual labor required to design and analyze such experiments.
Large language models (LLMs) have provided the necessary technological breakthrough for this purpose, given their ability to generate human-like text and carry out novel tasks after being prompted by instructions in natural language, without additional training. In this work, we develop a pipeline that uses large language models (LLMs) both to design naturalistic narrative stimuli for large-scale recall and recognition memory experiments, as well as to analyze the results. We performed online memory experiments with a large number of participants and collected recognition and recall data for narratives of different sizes. We found that both recall and recognition performance scale linearly with narrative length; however, for longer narratives people tend to summarize the content rather than recalling precise details. To investigate the role of narrative comprehension in memory, we repeated these experiments using scrambled versions of the narratives. Although recall performance declined significantly, recognition remained largely unaffected. Recalls in this condition seem to follow the original narrative order rather than the actual scrambled presentation, pointing to a contextual reconstruction of the story in memory. Finally, using LLM text embeddings, we construct a simple measure for each clause based on semantic similarity to the whole narrative, that shows a strong correlation with recall probability. Overall, our work demonstrates the power of LLMs in accessing new regimes in the study of human memory, as well as suggesting novel psychologically informed benchmarks for LLM performance.

Some problems in the theory and applications of stochastic processes reduce to solving integral equations with their covariance operators. Usually, such equations do not have explicit solutions, but useful information can still be extracted through asymptotic analysis with respect to relevant parameters. In this talk, I will survey some recent results on such equations for processes related to the fractional Brownian motion: applications include the problem of small deviations, linear filtering, and statistical inference.

Vizing’s Theorem provides an algorithm that edge colors any graph of maximum degree Δ using Δ+1 colors, which is necessary for some graphs, and at most one higher than necessary for any graph. In online settings, the trivial greedy algorithm requires 2Δ-1 colors, and Bar-Noy, Motwani and Naor in the early 90s showed that this is best possible, at least in the low-degree regime. In contrast, they conjectured that for graphs of superlogarithmic-in-n maximum degree, much better can be done, and that even (1+o(1))Δ colors suffice online. This would make edge coloring a rare problem, for which "online is (nearly) as easy as offline". In this talk I will outline the history of this conjecture, and its recent resolution, together with extensions of a flavor resembling classic and recent results on *list* edge-coloring and “local” edge-coloring.

Talk based in part on joint works with many wonderful and colorful collaborators, including Sayan Bhattacharya, Joakim Blikstad, Ilan R. Cohen, Fabrizio Grandoni, Seffi Naor, Binghui Peng, Amin Saberi, Aravind Srinivasan, Ola Svensson and Radu Vintan.

TBA

TBD

TBA

TBD

TBA

TBD

TBA

A distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy (Hastad, Impagliazzo, Levin, and Luby [SICOMP 99]), and to other cryptographic hardness assumptions, was unclear.

We advance towards a better understating of this notion, showing that a k-incompressible distribution has (k-2) bits of next-block pseudoentropy, a refinement of pseudoentropy introduced by Haitner, Reingold, and Vadhan [SICOMP ’13]. We deduce that a samplable distribution X that is (H(X) + 2)-incompressible, implies the existence of one-way functions.

Joint work with Iftach Haitner and Jad Silbak.