Integrated Calendar

Expansion is a manifestation of (pseudo)randomness with expander graphs
and their higher-dimensional analogues being concrete examples. Coding theory
is the study of properties and algorithms of codes, which are, in particular, important
for protecting data and communication against errors. Optimization, especially convex
programs, underlies much of our understanding of efficient computation. Not only
these are fundamental areas in their own right, but they also enjoy great synergy with
mutually nourishing interactions. This synergy has been instrumental in advancing
our understanding at the frontiers of almost optimal codes and expansion.

Expansion is the key ingredient in the breakthrough construction of explicit almost
optimal binary codes of Ta-Shma'17 (approximately matching the random parameters
known since the 1950s!). Using optimization and exploring expansion properties, we
give efficient decoding algorithms for these codes. Our first decoder is based on the
Sum-of-Squares SDP hierarchy and builds on our earlier approximation algorithm for
constraint satisfaction problems (CSPs) on high-dimensional expanders (HDXs). It gives
the first polynomial time decoder for explicit almost optimal binary codes. Our second
decoding algorithm is based on generalizations of weak regularity to expanding
hypergraphs, and it runs in near-linear time.

Regarding almost optimal expansion, we show how to efficiently transform an arbitrary
bounded degree expander into an almost optimal (i.e., almost Ramanujan) one in a way
that preserves its structural properties thereby having many applications. In particular,
we obtain almost optimal Cayley expanders from any expanding group. This is done
by generalizing the breakthrough techniques of Ta-Shma'17 from scalar to operators,
and it is an example of coding theory nourishing back the study of expansion.

Surprisingly, more precise parameters defining optimal binary codes are not known!
This longstanding question is intimately connected to optimization from which the best
bounds were derived in the 1970s. We now have a provably complete hierarchy of linear
programs for the important class of linear codes. This gives a provably sufficient avenue
to make progress on this problem.

In this talk, I will give an account of these developments and these synergetic interactions.
I will also point to some future research directions. Expansion, codes and optimization are
vibrant areas of TCS with several intriguing questions of their own, many interactions and
great potential for even further interactions with other areas.
(This presentation is based on joint work with many collaborators. Please, see my
webpage for details.)

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

Cells carefully regulate the movement of solutes across their membrane using an intricate array of interconnected transport pathways. While beneficial for mediating essential cellular activities, the abundance of complex transport pathways severely limits the elucidation of particular translocation mechanisms in live-cell studies. We alleviate this impediment by taking a reductionist approach to incorporate specific transport pathways (e.g., transport proteins) in simplified artificial cell models, using giant unilamellar vesicles (GUVs) as a biologically-relevant chassis. To gain maximal control over the bioengineering process, we developed an integrated microfluidic platform capable of high-throughput production and purification of monodispersed GUV-based cell models. Using single-vesicle fluorescence analysis, we quantified the passive permeation rate of two biologically important electrolytes, protons (H+) and potassium ions (K+), and correlated their flux with electrochemical gradient buildup across the GUV lipid bilayer. Applying similar analysis principles, we also determined the H+/K+ selectively of two archetypal ion channels, gramicidin A and outer membrane porin F (OmpF). Altogether, our results provide an insight into the transport mechanism of ions across lipid bilayers and set a framework for elucidating protein-based transport in artificial cell models.