Colloquia and Seminars

In a recent work, Cormode, Dall'Agnol, Gur and Hickey (CCC, 2024) introduced the model of Zero-Knowledge Streaming Interactive Proofs (zkSIPs). Loosely speaking, such proof-systems enable a prover to convince a streaming verifier that the input x, to which it has read-once streaming access, satisfies some property, in such a way that nothing beyond the correctness of the claim is revealed. Cormode et al. also gave constructions of zkSIPs to some specific and notable problems of interest.

In this work, we advance the study of zero-knowledge proofs in the streaming model, by presenting protocols that are significantly more general and more secure. We use a definition of zero-knowledge that is a variation of that used by Cormode et al., which we find more appealing but is technically incomparable.

Our main result is a zkSIP for any NP relation, that can be decided by low-depth polynomial-size circuits. We emphasize that this is the first general purpose protocol in this model, which captures, as a special case, the problems considered by the prior work. We also construct a specialized protocol for the ``polynomial evaluation'' problem considered in that work, with improved parameters.

The protocols constructed by Cormode et al. have an inverse polylogarithmic simulation error (i.e., a gap with which a bounded-space distingiusher can distinguish the simulation from a real execution). This means that their protocols are entirely insecure if run multiple times (say on different inputs). In contrast, our protocols achieve a negligible zero-knowledge error, a stronger and far more robust security guarantee.

Image generative models are advancing rapidly, producing images of remarkable realism and fidelity. However, existing models often lack precise control over the generated content, limiting their image editing capabilities and the integration of real content into synthesized imagery. In this talk, I will demonstrate how a deep understanding of the inner mechanisms of large-scale pretrained generative models enables the design of powerful techniques for a variety of image manipulation tasks. By analyzing the semantic representations learned by these models, I will present methods that enable effective content editing. Additionally, I will discuss the challenges and trade-offs involved in manipulating real content and propose strategies to address these challenges. Finally, I will highlight recent advancements in incorporating real content, with a particular focus on techniques for injecting information into pretrained models.  

Bio: Or Patashnik (https://orpatashnik.github.io/) is a Computer Science PhD candidate at Tel Aviv University, supervised by Daniel Cohen-Or. Her research focuses on computer graphics and its intersection with computer vision, with an emphasis on generative tasks such as image editing, personalization, and image inversion using large-scale pretrained models. Recently, she has been particularly interested in better understanding diffusion models for various applications.

Geometric data and signal processing have made remarkable progress in recent years, and the advent of modern AI tools promises an even brighter future. Many classical and contemporary methods, however, use vast amounts of data, substantial processing power, and considerable natural resources to achieve their results. These approaches can be expensive, environmentally harmful, and ultimately unsustainable. This talk explores efforts to do more with less in geometry processing by ensuring that methods use all the information contained in input data, by maximally utilizing noisy and sparse data, and by developing methods for computer-aided fabrication with sustainable materials. We will dive deeper into surface digitization from extremely low-resolution scans, training generative AI models without collecting terabytes of data, denoising functions on low-quality geometric domains, developing robust geometric algorithms with mathematical guarantees, and design tools for alternative manufacturing methods.

Bio: Oded Stein received his PhD from Columbia University in Applied Mathematics from Columbia University under the supervision of Eitan Grinspun for his research of smoothness energies in geometry processing in 2020. From 2020 to 2022 he was a postdoctoral fellow at MIT’s Computer Science & Artificial Intelligence Lab with the gracious support of the Swiss National Science Foundation’s Early Postdoc.Mobility fellowship. Since 2023 Oded Stein is an Assistant Professor at USC’s Viterbi School of Engineering, supported by the Powell Faculty Research Award and the National Science Foundation.

Over the past decade, several studies have shown that DNA-based storage systems can potentially become the standard for data archival due to their high data density and durability. However, the current bottleneck involves the synthesis and sequencing costs, along with a lack of coding solutions to address the unique error characteristics of DNA-based systems.

This work tackles multiple challenges that hinder the practical implementation of DNA storage. First, we explore theoretical aspects of the deletion channel, presenting detailed findings from the maximum likelihood decoder for both single and dual-channel outputs. Next, we address the DNA reconstruction problem, aiming to accurately reconstruct a DNA sequence from multiple noisy copies. We propose several reconstruction algorithms that significantly enhance accuracy compared to previously published approaches. Furthermore, we investigate two novel synthesis methods, the composite synthesis and the combinatorial composite synthesis, highlighting their potential benefits and inherent complexities. These methods require innovative algorithmic and coding solutions, and thus we design error-correction codes specifically tailored for these technologies.

Finally, we introduce the DNA storalator, a software tool designed to simulate the biological and computational processes of DNA storage, aiding our research and facilitating further exploration within the scientific community. Overall, the results presented in this work advance several aspects of DNA data storage and promote the feasibility of this storage solution further.

Edge computing extends cloud capabilities to the proximity of end-users, offering ultra-low latency, which is essential for real-time applications. Unlike traditional cloud systems that suffer from latency and reliability constraints due to distant datacenters, edge computing employs a distributed model, leveraging local edge datacenters to process and store data.

This talk explores key challenges in edge computing across three domains: workloads, storage, and service allocation. 
The first part focuses on the absence of comprehensive edge workload datasets. Current datasets do not accurately reflect the unique attributes of edge systems. To address this, we propose a workload composition methodology and introduce WoW-IO, an open-source trace generator. The second part examines aspects of edge storage. Edge datacenters are significantly smaller than their cloud counterparts and require dedicated solutions. We analyze the applicability of a promising mathematical model for edge storage systems and raise inherent gaps between theory and practice. The final part addresses the virtual network embedding problem (VNEP). In VNEP, given a set of requests for deploying virtualized applications, the edge provider has to deploy a maximum number of them to the underlying physical network, subject to capacity constraints. We propose novel solutions, including a proactive service allocation strategy for mobile users, a flexible algorithm for service allocation that is adaptable to the underlying physical topology, and  an algorithm for scalable online service allocation.

Labeling schemes are a prevalent paradigm in various computing settings. In such schemes, an oracle is given an input graph and produces a label for each of its nodes, enabling the labels to be used for various tasks. In this talk, I will address the question of what happens in a labeling scheme if some labels are erased, e.g., due to communication loss with the oracle or hardware errors. I will present a new resilient labeling scheme which improves upon the state of the art in several computational aspects and I will show that it is nearly optimal.

In the field of video compression, the pursuit for better quality at lower bit rates remains a long-lasting goal. Recent developments have demonstrated the potential of Implicit Neural Representation (INR) as a promising alternative to traditional transform-based methodologies. Video INRs can be roughly divided into frame-wise and pixel-wise methods according to the structure the network outputs. While the pixel-based methods are better for upsampling and parallelization, frame-wise methods demonstrated better performance. We introduce CoordFlow, a novel pixel-wise INR for video compression. It yields state-of-the-art results compared to other pixel-wise INRs and on-par performance compared to leading frame-wise techniques. The method is based on the separation of the visual information into visually consistent layers, each represented by a dedicated network that compensates for the layer's motion. When integrated, a byproduct is an unsupervised segmentation of video sequence. Objects motion trajectories are implicitly utilized to compensate for visual-temporal redundancies. Additionally, the proposed method provides inherent video upsampling, stabilization, inpainting, and denoising capabilities.

A myriad of authentication mechanisms embody a continuous evolution from verbal passwords in ancient times to contemporary multi-factor authentication: Cryptocurrency wallets advanced from a single signing key to using a handful of well-kept credentials, and for online services, the infamous “security questions” were all but abandoned. Nevertheless, digital asset heists and numerous identity theft cases illustrate the urgent need to revisit the fundamentals of user authentication.  

We abstract away credential details and formalize the general, common case of asynchronous authentication, with unbounded message propagation time. Given credentials' fault probabilities (e.g., loss or leak), we seek mechanisms with maximal success probability. Such analysis was not possible before due to the large number of possible mechanisms. We show that every mechanism is dominated by some Boolean mechanism-defined by a monotonic Boolean function on presented credentials.  We present an algorithm for finding approximately optimal mechanisms by leveraging the problem structure to reduce complexity by orders of magnitude.   

The algorithm immediately revealed two surprising results: Accurately incorporating easily-lost credentials improves cryptocurrency wallet security by orders of magnitude. And novel usage of (easily-leaked) security questions improves authentication security for online services.