Theses & Reports

---

Instructions for submitting a technical report or thesis.

You can find technical reports published prior to 1990 archived here.

• Ph.D. Thesis 2024 On Efficient Instantiations of Secure Multi-Party Computation in Practice Bienstock, Alexander Abstract | PDF

  Title: On Efficient Instantiations of Secure Multi-Party Computation in Practice

  Candidate: Bienstock, Alexander

  Advisor(s): Yevgeniy Dodis/Marshall Ball

  Abstract:

  Secure Multi-Party Computation (MPC) is an area of cryptography that has been studied extensively since the 1980s. In full generality, MPC allows a set of mutually distrusting parties to privately compute a function of their inputs. That is, the parties interact in some protocol, and at the end obtain the output of the function, and nothing else. In the decades since the inception of MPC, great strides have been made towards making it more efficient. However, despite this progress, the use of MPC in practice still faces some shortcomings.
  
  In this thesis, we take steps to mitigate two such shortcomings. The first deficiency we study is related to the communication networks in which such MPC protocols operate. MPC protocols are usually designed assuming that all parties have pairwise secure communication channels which are stable; i.e., nodes never crash, messages always arrive on time, etc. However, in the real-world, this is rarely the case—it is hard to sustain a stable connection between parties over long periods of time. One such model that has been introduced to address this deficiency is called Fluid MPC (Choudhuri et al., CRYPTO 2021). In this model, parties are not mandated to stay online for long periods of time. Instead, parties come online for short periods of time and work together in committees to compute some function. The benefit is that individual committees are much more likely to be able to sustain stable connections for these shorter interactions. However, existing protocols in this model do not match the level of efficiency that is obtained by traditional MPC protocols. In the first part of this thesis, we study Fluid MPC, and in particular, introduce Fluid MPC protocols with efficiency that matches those of traditional MPC.
  
  The second deficiency of MPC which we study in this thesis is that general-purpose protocols often are still not efficient enough to be used in practice. One way to resolve this is by using protocols that are tailor-made for specific applications. One such application that has gained recent attention is called Private Join and Compute (PJC). In this application, two parties come together with input sets and associated values for each item in their sets. The goal is to privately compute a function over the associated values of the intersection of the two sets. In practice, the size of the intersection is quite small, and therefore the private computation of the intersection is actually much more expensive than whatever computation that needs to be done over it. In the second part of this thesis, we improve the efficiency of tailor-made state-of-the-art protocols that are used to privately compute the intersection, thus improving the efficiency of prior PJC protocols.

• Ph.D. Thesis 2024 Predictive and Generative Models of Protein Sequence and Structure Lin, Zeming Abstract | PDF

  Title: Predictive and Generative Models of Protein Sequence and Structure

  Candidate: Lin, Zeming

  Advisor(s): Yann LeCun

  Abstract:

  Historically, protein engineering has predominantly involved a bottom-up strategy, utilizing naturally occurring components as the building blocks. However, the problem of designing arbitrary protein sequences and structures for specific problems present significant challenges due to the complexity of biological systems. In this work, we tackle the problem of developing models of protein sequences and structures for prediction and generation. We show that neural networks can learn the patterns inherent to these systems and provide results for modeling protein through predicting protein structures from a given sequence and vice versa. Generative models can also model the unconditional distributions of protein sequence and structure.

  To model protein structures, we present an autoencoder architecture that can produce a wide array of protein backbones to model protein structures. These structures exhibit both local and global coherence in terms of secondary and tertiary structures. Using classical techniques to design sequences that fold to generated backbones, we show that the model can generate novel sequences which are validated in-silico. To generate better sequences for these backbones, we then present ESM-IF1, a model for fixed backbone protein design. We designed a large-scale system to predict millions of structures using AlphaFold. By training on the synthetic data, we were able to obtain state of the art results and obtain over 50\% sequence recovery.

  We then scale large protein language models to 15 billion parameters (ESM-2) as an unconditional model of protein sequences. ESM-2 is capable of replacing multiple sequence alignment (MSA) features to obtain nearly state-of-the-art structure prediction results from a single sequence Removing MSA features gives a 60x speed up, allowing us to catalog the largest database of predicted protein structures. We open-sourced the ESM Metagenomic Atlas, a database of over 225 million high-confidence predicted structures, giving us an unprecedented view into the vast breadth and diversity of natural proteins. Finally, the speed and single sequence nature of our model allows us to directly optimize the protein sequence with respect to the protein structure. We show that black box optimization techniques can enable the design of proteins with structural constraints as symmetry, scaffolding, and binding. In sum, we present a series of models that are able to model the conditional and unconditional distributions of protein sequence and structure.

• Ph.D. Thesis 2024 Neural Language Representations and Scaling Semi-Supervised Learning for Speech Recognition Peyser, Cal Abstract | PDF

  Title: Neural Language Representations and Scaling Semi-Supervised Learning for Speech Recognition

  Candidate: Peyser, Cal

  Advisor(s): Prof. Kyunghyun Cho, Prof. Michael Picheny

  Abstract:

  Speech recognition research has been focused for several years on the incorporation of unpaired speech and text data alongside conventional supervised datasets. Dominant methods have emphasized auxiliary tasks for refining speech and/or text representations during model training. These methods have generally performed strongly when paired with very small supervised datasets, but do not yield the same improvements against strong, supervised baselines. We argue in this thesis that the path to scaling these methods lies in the speech and text representations themselves. We investigate statistical properties of these representations, and show that downstream ASR performance corresponds to a model's ability to jointly represent speech and text. We analyze existing methods for semisupervised ASR, and develop an algorithm to improve them at scale by aligning speech and text in representation space.

• Ph.D. Thesis 2024 DrawTalking: Building Interactive Worlds by Sketching and Speaking Rosenberg, Karl Toby Abstract | PDF

  Title: DrawTalking: Building Interactive Worlds by Sketching and Speaking

  Candidate: Rosenberg, Karl Toby

  Advisor(s): Ken Perlin

  Abstract:

  This thesis introduces the design and implementation of an interaction concept called DrawTalking. Through simple combinations of sketching and speaking, the user can improvisationally build an interactive world of graphics, animations, diagrams, and dynamic mechanisms with behavior and rules, as if by narrating a story or explaining a concept to an audience. The interface demonstrates a possible step towards designing future interfaces more closely in-tune with how we naturally communicate and think.
  
  For context, sketching while speaking has played a major part in innovation across disciplines. The combination of visuals and spoken language enables us to make-believe: think about, describe, communicate, and interact with anything that we can think of, including things that do not or cannot exist in the real world. Evolving technology creates opportunities to move beyond sketching and speech alone. Human-computer interactions of the future, drawing inspiration from our process of make-believe, can add interactive computation to the combination of sketching and speech, allowing us to work with explorable worlds, simulations, and mechanics. By enabling such interactions, we might think, learn, design, play, and tell stories in increasingly expressive ways.
  
  Towards this idea, what makes for a good interface for computation-mediated sketching and speaking? This touches upon several fundamental questions in interaction design, human-AI interaction, and human-centered interfaces, chiefly among them, how to balance human control and machine automation?
  
  Inspired by real-world speaking and sketching interactions, and seminal works in dynamic sketching, interactive visual programming, and language interfaces, we designed interaction techniques that draw on the way people describe objects and phenomena when telling stories and explaining processes at a whiteboard.
  
  How does it work? the user speaks to label hand-drawn sketches with names and properties, and to define rules for how their world should behave. This communicates semantic intent to the computer, while giving the user the flexibility to choose how to represent and change their drawings. Now the user can interact with a simulated world simply by narrating stories or describing mechanics, which dynamically creates running interactive programs from built-in primitives and user-customized rules.
  
  To gauge understanding of the mechanics of DrawTalking and to derive use cases, we invited participants to an open-ended one-on-one user-study session with the researcher to discover and explore the features in DrawTalking. Each user improvised and prototyped interactive sketch-based animations and gameplay scenarios by collaborating with the researcher. The resulting artifacts and discussion were oriented around each participant's specific experiences and background.
  
  Feedback suggests that our approach is promising and intuitive: it prioritizes user control; it is flexible and supports improvisation; the workflow is fluid; the features are extensible and adaptable to other application domains and contexts beyond sketching; the design demonstrates how multiple applications can use similar language-based interaction techniques and behaviors predictably alongside other language-based technologies; it enables programming-like capability without code.
  
  Through the research and design process of DrawTalking, we learned that it could represent an approach to designing complex interoperating systems for human-AI collaboration. We hope it can serve as a useful example for research and design of future machine-mediated interfaces, interactions, and computer systems.

• Ph.D. Thesis 2024 Olympiad-level Geometry Theorem Proving without Human Demonstrations Trinh, Trieu Abstract | PDF

  Title: Olympiad-level Geometry Theorem Proving without Human Demonstrations

  Candidate: Trinh, Trieu

  Advisor(s): He He

  Abstract:

  Proving mathematical theorems at Olympiad level represents a significant milestone in human-level automated reasoning, owing to their reputed difficulty among the world’s best talents in pre-university mathematics. Current machine learning approaches, however, are not applicable to most mathematical domains due to the high cost of translating human proofs into machine-verifiable format. The problem is even worse for geometry due to its unique translation challenges, resulting in severe scarcity of training data. We propose G0, a theorem prover for Euclidean plane geometry that sidesteps the need for human demonstrations by synthesizing millions of theorems and proofs across different levels of complexity. G0 is a neuro-symbolic system that uses a neural language model, trained from scratch on our large-scale synthetic data, to guide a symbolic deduction engine through infinite branching points in challenging problems. On a test set of 30 latest Olympiad problems, G0 solves 25, outperforming the previous best method that only solves 10 problems and approaching the performance of an average International Mathematical Olympiad (IMO) gold medalist. Notably, G0 produces human-readable proofs, solves all geometry problems in the IMO 2000 and 2015 under human expert evaluation, and discovers a generalized version of a translated IMO theorem in 2004.

• Ph.D. Thesis 2024 Theory of Symmetric Neural Networks Zweig, Aaron Abstract | PDF

  Title: Theory of Symmetric Neural Networks

  Candidate: Zweig, Aaron

  Advisor(s): Joan Bruna

  Abstract:

  Symmetric functions, which take as input an unordered, fixed-size set, find practical application in myriad physical settings based on indistinguishable points or particles, and are also used as intermediate building blocks to construct networks with other invariances. Symmetric functions are known to be universally representable by neural networks that enforce permutation invariance. However the theoretical tools that characterize the approximation, optimization and generalization of typical networks fail to adequately characterize architectures that enforce invariance.
  
  This thesis explores when these tools can be adapted to symmetric architectures, and when the invariance properties lead to new theoretical findings altogether. We study and prove approximation limitations on the extension of symmetric neural networks to infinite-sized inputs, the approximation capabilities of symmetric and antisymmetric networks relative to the interaction between set elements, and the learnability of simple symmetric functions with gradient methods