לוח שנה משולב

The classical literature on streaming algorithms has mainly studied two types of algorithms: randomized and deterministic.
However, almost all classical analyses of randomized streaming algorithms assume that the stream is “fixed in advance”, making them unfit for use in adaptive settings where future stream updates depend on previous outputs of the algorithm. Meanwhile, deterministic algorithms are guaranteed to work in adaptive settings, but many important problems in the streaming literature do not admit efficient deterministic algorithms. This raises the question of whether one can enjoy both worlds: do there exist robust randomized streaming algorithms, which are space-efficient and provably work in adaptive settings?

The recent couple of years have seen a surge of work on this topic, starting from a generic robustification framework we developed, which turns “standard” randomized algorithms into robust ones. As it turns out, the answer to the above question is largely positive for insertion-only streams, but still unknown in general turnstile (insertion-deletion) streams. I will present our framework and mention several lines of follow-up work on this topic, including improved frameworks, results for specific algorithms, and connections to a wide range of topics within computer science, including differential privacy, cryptography, learning theory and others. Focusing on classical problems such as distinct elements counting and norm estimation, I will highlight what we know in the turnstile setting and present several directions for future work.

Based in part on joint works with Rajesh Jayaram, David Woodruff, and Eylon Yogev, and with Talya Eden and Krzysztof Onak. (I will also briefly mention related joint works with Noga Alon, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev.)

The Covid-19 pandemic emphasized the need for antiviral drugs to block infection and spread of emerging coronaviruses (CoVs). We designed a high-content screen based on Vesicular Stomatitis pseudoviruses that lack the G glycoprotein and express instead a fluorescent reporter (VSVΔG). We used the platform to conduct a high-throughput screen of 173,227 unique small molecules for their ability to inhibit pseudoviruses bearing the SARS-CoV-2 S protein.

To identify broad-spectrum inhibitors, hits were counter screened against VSVΔG pseudoviruses bearing the unrelated G glycoprotein and subsequently classified based on their ability to inhibit infection of pseudoviruses bearing the S protein of MERS-CoV that uses a different cell-surface receptor, and the SARS-CoV-2 S protein variants, alpha, delta, and omicron. This analysis identified novel compounds that inhibit infection at sub-micromolar concentrations, and the previously identified broad spectrum inhibitor Nafamostat, validating the screening approach and paving the way to studies in vivo.

The lack of interpretability is a much-criticised feature of deep neural networks. Often, a neural network is effectively a black box. However, we have recently found a group-theoretical procedure that brings inner layer signalling into a human-readable form. We applied it to a signal processing network used in magnetic resonance spectroscopy, and found that the network spontaneously invents a bandpass filter, a notch filter, a frequency axis rescaling transformation, frequency division multiplexing, group embedding, spectral filtering regularisation, and a map from harmonic functions into Chebyshev polynomials – in ten minutes of unattended training.