This dissertation describes three systems to help people better understand and debug the behavior of embedded electronic systems. The underlying shared principles across these projects are automatic instrumentation, visualization, and checking. The first, Toastboard, is a system for electronics prototyping that combines an instrumented breadboard with a web-based GUI and checks for common circuit construction mistakes. Bifröst extends this idea to systems that involve both code and circuits by simultaneously instrumenting a user's embedded code and microcontroller pins. Bifröst focuses on tricky to debug errors that can occur at the boundary between software and hardware. Finally, Wifröst addresses difficulties encountered when connecting embedded devices to the Internet. Wifröst instruments and collects data from a user's code as well as network infrastructure in order to guide users to the underlying reasons for and solutions to failures. These systems were evaluated through debugging tasks and user feedback. Taken together, these systems envision a future in which non-experts have a much greater understanding of the behavior of embedded computing devices in order to more effectively build, combine, repair, and audit their functionality.

Three of the most pressing questions in human disease genetics are: 1) which genes cause disease, 2) how genes relate to each other to form biological pathways, and 3) how the environment modulates genetic disease risk. This thesis describes contributions to methods addressing each of these three questions. Regarding the problem of identifying causal genes for complex traits, this thesis explores properties of transcriptome-wide association studies (TWAS), a class of methods which intersect GWAS and expression quantitative trait locus (eQTL) datasets to find gene-trait associations, using simulations and case studies of literature-curated candidate causal genes for schizophrenia, LDL cholesterol and Crohn's disease. We explore risk loci where TWAS accurately prioritizes the likely causal gene, as well as loci where TWAS prioritizes multiple genes, some of which are unlikely to be causal, because they share the same variants as eQTLs. We illustrate that TWAS is especially prone to spurious prioritization when using expression data from tissues or cell types that are less related to the trait, due to substantial variation in both expression levels and eQTL strengths across cell types. Nonetheless, TWAS prioritizes candidate causal genes at GWAS loci more accurately than simple baselines based on proximity to lead GWAS variant and expression in trait-related tissues. We discuss current strategies and future opportunities for improving the performance of TWAS for causal gene prioritization. Our results showcase the strengths and limitations of using expression variation across individuals to determine causal genes at GWAS loci and provide guidelines and best practices when using TWAS to prioritize candidate causal genes. Regarding the problem of understanding environmental modulation of complex traits, this thesis describes an application of Mendelian Randomization (MR) to 328,459 individuals in the UK Biobank cohort to interrogate the relationship between BMI and diabetes risk across diverse strata of body mass index (BMI), diabetes family history, and genome-wide polygenic risk scores. Though lifestyle interventions to reduce BMI are critical public health strategies for type 2 diabetes prevention, and weight loss interventions have shown demonstrable benefit for high-risk individuals, it is unclear whether the same benefits apply to those at lower risk. We found that diabetes prevalence increased sharply with BMI, family history of diabetes, and genetic risk, and increased marginally with BMI-adjusted genetic risk. However, genetic risk scores were much less predictive of diabetes status than family history, particularly after correcting for BMI. Conversely, predicted risk reduction from weight loss was strikingly similar across BMI and genetic risk categories. Weight loss was predicted to substantially reduce diabetes risk even among lower-risk individuals: a 1 kg/m2 BMI reduction was associated with a 1.31-fold reduction (95% confidence interval [CI], 1.25-1.38) in diabetes odds among individuals without a family history of diabetes, a 1.26-fold reduction (95% CI, 1.18-1.35) among individuals at low genetic risk, and a 1.28-fold reduction (95% CI, 1.19-1.37) among individuals at low BMI-adjusted genetic risk, all nearly identical to the full cohort (1.29-fold reduction, 95% CI, 1.25-1.35). In fact, individuals without family history were predicted to have even greater risk reduction than individuals with family history (1.31-fold vs 1.19-fold reduction, p = 0.02). Overall, we found that lower BMI is consistently associated with reduced diabetes risk across BMI, family history and genetic risk categories, suggesting all individuals can substantially reduce their diabetes risk through weight loss. Our results support the broad deployment of weight-loss interventions to individuals at all levels of diabetes risk. Regarding the problem of how genes relate to each other, this thesis describes the development of an approach to map co-essentiality, the tendency of genes with similar functions to have correlated knockout fitness profiles across cell lines, using generalized least squares (GLS). Our approach is well-powered, flexible and statistically well-calibrated, and avoids the pervasive false positives of previous approaches by appropriately accounting for the relatedness among cell lines. Applying the method to a compendium of 485 genome-wide CRISPR/Cas9 essentiality screens substantially improves recapitulation of known protein complexes and pathway interactions relative to prior approaches. Our methodological improvements enable unbiased genome-wide clustering based on co-essentiality profiles; we recover pathways and complexes as diverse as MAPK/ERK, PI3K/ACT/mTOR, the ribosome, the peroxisome, regulators of the DNA damage response and chromatin remodeling. These clusters also nominate roles for uncharacterized and poorly characterized genes in known pathways. Our genome-wide pathway map is a valuable resource for biological hypothesis generation.

Most congestion control algorithms rely on a reactive control system that detects congestion and then marches carefully toward a desired operating point (e.g., by modifying the window size or picking a rate). These algorithms often take hundreds of RTTs to converge—an increasing problem in networks with short-lived flows. Motivated by the need for fast congestion control, this thesis focuses on a different class of congestion control algorithms, called proactive explicit rate-control (PERC) algorithms, which decouple the rate calculation from congestion signals in the network. The switches and NICs exchange control messages to run a distributed algorithm to pick explicit rates for each flow. PERC algorithms proactively schedule flows to be sent at certain explicit rates. They take as input the set of flows and the network link speeds and topology, but not a congestion signal. As a result, they converge faster and their convergence time depends only on fundamental "dependency chains, " essentially couplings between links that carry common flows, that are a property of the traffic matrix and the network topology. We argue that congestion control should converge in a time limited only by fundamental dependency chains. Our main contribution is s-PERC: a new practical distributed proactive scheduling algorithm. It is the first PERC algorithm to provably converge in bounded time without requiring per-flow state or network synchronization. It converges to the exact max-min fair allocation in 6N rounds (where N is the number of links in the longest dependency chain). In simulation and on a P4-programmed FPGA hardware test bed, s-PERC converges an order of magnitude faster than reactive schemes such as TCP, DCTCP, and RCP. Long flows complete in close to the ideal time, while while short-lived flows are prioritized, making it relevant for data centers and wide-area networks (WANs).

Genome sequencing is widely used in clinical practice. Individuals typically have over 4 million variants genome wide and approximately 500 variants of uncertain significance (VUS) near protein coding genes, with no clear clinical interpretation, identified through exome sequencing. Given that clinicians require dozens of hours to diagnose each patient and the estimates that 60 million individuals will be sequenced over the next 5 years patient diagnosis and genomic analysis is becoming a critical bottleneck. Developing automated and effective computational tools is essential to handle the increasing scale of patient genomes. Predicting the pathogenicity of these variants is a first step to identifying the genetic basis of a monogenic disease. Effective strategies for Mendelian disease diagnosis bring together the patient's genetic data from sequencing and phenotype data found in the electronic medical record (EMR) system to prioritize the genetic variation causing the patient's disease. In chapter 1, we provide an overview of Mendelian disease diagnosis, challenges, current approaches and an overview of the solutions we developed towards automating disease diagnosis. In chapter 2, 3 and 4 we introduce methods to improve interpretation of patient's genetic variation. Specifically in chapter 2 we introduce M-CAP, the first clinically applicable pathogenicity classifier for VUS that alter the encoded amino acid, the largest class of known pathogenic mutations. In chapter 3, we then extend this methodology to build S-CAP, the first model to predict the pathogenicity of previously ignored variants that disrupt pre-mRNA splicing mechanism, the second largest class of known pathogenic mutations. In chapter 4 we then explore a strategy to start identifying noncoding disease causing mutations from whole genome sequencing. In chapter 5 we introduce Phrank, a method to measure similarity between sets of phenotypes and prioritize those genes that best explain the patient's disease symptoms. Just as each patient has a list of phenotypes in the medical record describing signs and symptoms, genes also have associated phenotypes listed in databases such as OMIM. Incorporating phenotype information into the diagnostic pipeline greatly improves the effectiveness and interpretability of the patient's genomic data. The above methods highlight the serve or protect dilemma commonly seen when working with patient data. The tools in chapters 2-5 require patient data (both genotype and phenotype) to be shared with clinicians and between hospitals. All of these inputs are extremely sensitive. To protect patient privacy, genotypes and phenotypes should not be shared with anyone. In chapter 6 we introduce a novel set of secure cryptographic protocols to diagnose Mendelian diseases while revealing the minimal amount of genetic information. In chapter 7, we extend these strategies to securely compute the Phrank similarity operation over patient phenotype information. We conclude in chapter 8 where we summarize the novel developments in this dissertation and enumerate the next steps based on this research work. Chapter 2 was published in Nature Genetics. Chapter 3 has also just been published in Nature Genetics. Chapter 4 has been published in the European Journal of Human Genetics. Chapter 5 is published in Genetics in Medicine. Chapter 6 is published in Science and Chapter 7 is currently being submitted for publication.

Botanical trees are ubiquitous in many real-world environments, and they are consequently also pervasive in the virtual environments created for film special effects, games, virtual reality, etc. The motion of these trees ranges from subtle swaying that is easily overlooked to dramatic deformation in extreme weather conditions. The geometry of these trees is highly intricate, with features including bark, knots, intricate networks of fine twigs and branches, and at times leaves, fruits, and flowers. This dissertation presents a set of frameworks for modeling a tree's motion via artist-directed simulation and its geometry via image-based reconstruction. First, we address the challenge of efficiently simulating tree motion for complex tree models. Efficient simulation of tree movement is difficult due to the many degrees of freedom needed to represent a high fidelity tree; this challenge is further compounded by the typically stiff material properties of a tree, making it difficult to simulate at interactive frame rates using standard time integration techniques. To address these issues, we present an algorithm with linear time complexity that simulates trees as articulated rigid bodies with as-stiff-as-desired rotational joints by taking the analytic solution to an approximated problem. Our method supports a variety of effects including wind, fictitious forces, collisions, plasticity, and leaf and fruit fracture, and it can be used to interactively parameterize tree models, run tree simulations using a game engine on a commodity tablet, simulate and render high quality trees with thousands to millions of rigid bodies, etc. Second, we address the challenge of reconstructing high fidelity, simulation-ready geometry of a tree from the real world. Beginning with a set of drone-mounted cameras, we acquire image data and apply traditional structure from motion and multi-view stereo techniques, then use the resulting point cloud data to build a simulatable representation of the tree's trunk and major branches. To reconstruct smaller twigs, we present an image annotation approach and subsequent improvements to simplify or automate parts of the annotation process using stereo correspondence information and a trained network for semantic segmentation of tree images. Finally, we combine the resulting model with our simulation framework to animate the reconstructed tree geometry.

Training a machine learning model today involves minimizing a loss function on datasets that are often gigantic, and so almost all practically relevant training algorithms operate in an online manner by reading in small chunks of the data at a time and making updates to the model on-the-fly. As a result, online learning, a popular way to analyze optimization algorithms operating on datastreams, is at the heart of modern machine learning pipelines. In order to converge to the optimal model as quickly as possible, online learning algorithms all require some user-specified parameters that reflect the shape of the loss or statistics of the input data. Examples of such parameters include the size of the gradients of the losses, the distance from some initial model to the optimal model, and the amount of variance in the data, among others. Since the true values for these parameters are often unknown, the practical implementation of online learning algorithms usually involves simply guessing (called ``tuning''), which is both inefficient and inelegant. This motivates the search for parameter-free algorithms that can adapt to these unknown values. Prior algorithms have achieved adaptivity to many different unknown parameters individually - for example one may adapt to an unknown gradient sizes given a known distance to the optimal model, or adapt to the unknown distance given a known bound on gradient size. However, no algorithm could adapt to both parameters simultaneously. This work introduces new lower bounds, algorithms, and analysis techniques for adapting to many parameters at once. We begin by proving a lower bound showing that adapting to both the size of the gradients and distance to optimal model simultaneously is fundamentally much harder than adapting to either individually, and proceed to develop the first algorithm to meet this lower bound, obtaining optimal adaptivity to both parameters at once. We then expand upon this result to design algorithms that adapt to more unknown parameters, including the variance of the data, different methods for measuring distances, and upper or lower bounds on the second derivative of the loss. We obtain these results by developing new techniques that convert non-parameter-free optimization algorithms into parameter-free algorithms. In addition to providing new and more adaptive algorithms, the relative simplicity of non-parameter-free algorithms allows these techniques to significantly reduce the complexity of many prior analyses.

From smart homes that prepare coffee when we wake, to phones that know not to interrupt us during important conversations, our collective visions of human-computer interaction (HCI) imagine a future in which computers understand a broad range of human behaviors. Today our systems fall short of these visions, however, because this range of behaviors is too large for designers or programmers to capture manually. In this thesis I will present three systems that mine and operationalize an understanding of human life from large text corpora. The first system, Augur, focuses on what people do in daily life: capturing many thousands of relationships between human activities (e.g., taking a phone call, using a computer, going to a meeting) and the scene context that surrounds them. The second system, Empath, focuses on what people say: capturing hundreds of linguistic signals through a set of pre-generated lexicons, and allowing computational social scientists to create new lexicons on demand. The final system, Codex, explores how similar models can empower an understanding of emergent programming practice across millions of lines of open source code. Between these projects, I will demonstrate how semi-supervised and unsupervised learning can enable many new applications and analyses for interactive systems.

The number of enterprises that exploit the data they collect in their decision making processes has been rapidly growing. A fundamental component to achieve this goal, is data integration, the process of combining and unifying data from multiple sources. Through data integration, an enterprise can find the underlying types of entities and entity attributes in the collected data, and map the data to those types and attributes. Enterprises expect constant improvements in the quality of the data integration outcome. At the same time, the volume and diversity of the collected data increases at a fast pace, as enterprises decide to monitor and collect data from more of their operations or other external sources. To satisfy the quality-improvement requirements, human involvement in data integration has been proposed and applied in the last years: the main idea is to use human intelligence in tasks that require the understanding of data semantics or involve data containing images, video, or natural language. In this thesis, we study approaches for different data integration tasks that combine machine algorithms and human intelligence. In particular, we focus on three data integration tasks: entity resolution, top-k item detection, and data aggregation. In entity resolution, for each underlying entity in a set of records (e.g., peoples' face images), the goal is to create one cluster containing only the records that refer to the same entity (e.g., same person). In top-k item detection, the input is a set of records (e.g., restaurant images) and the goal is to find the top-k records based on some criteria (e.g., how nice the restaurant looks in the image). In data aggregation, the goal is to create a summary of some input content (e.g., 5-minute summary of a 2-hour movie or summary of the main points in the reviews for a movie or product). The approaches we develop, provide solutions to a spectrum of challenges that hybrid machine-human, data-integration approaches face. Furthermore, our approaches provide significant performance, accuracy, and monetary-cost gains compared to state-of-the-art alternatives. The gains come from efficiently solving a number of fundamental problems for hybrid data-integration approaches: a) combining human errors with machine algorithm errors, b) selecting the best questions to ask humans, c) selecting between different interfaces for human questions, d) managing the resources available for human questions, e) preprocessing data before human curation is applied, and f) creating a context describing the whole dataset, to assist humans in accurately answering questions.

The field of computer vision has made enormous progress in the last few years, largely due to convolutional neural networks. Despite success on traditional computer vision tasks, our systems are still a long way from the general visual intelligence of people. An important facet of visual intelligence is composition - understanding of the whole derives from an understanding of the parts. To achieve the goal of compositional visual intelligence, we must explore new computer vision tasks, create new datasets, and develop new models that exploit compositionality. In this dissertation I will discuss my work on three different computer vision tasks involving language, where embracing compositionality helps us build systems with richer visual intelligence. I will first discuss image captioning: traditional systems generate short sentences describing images, but by decomposing images into regions and descriptions into phrases we can that generate two types of richer descriptions: dense captions and paragraphs. Second, I will discuss visual question answering: existing datasets consist primarily of short, simple questions; to study more complex questions requiring com- positional reasoning, we introduce a new benchark dataset where existing methods fall short. We then propose an explicitly compositional model for visual question an- swering that internally converts questions to functional programs, and executes these programs by composing neural modules. Third, I will discuss text-to-image: existing systems can retrieve or generate simple images of a single object conditioned on text descriptions, but struggle with more complex descriptions. By replacing freeform natural language with compositional scene graphs of objects and relationships, we can retrieve and generate complex images containing multiple objects.

Neural networks are a core component of both biological and artificial intelligence. Despite advances in training artificial networks to solve complex tasks, they are often brittle in ways that biological networks are not, and our understanding of how they work remains incomplete. In this thesis, I take steps towards applying machine learning to better understand biological neural networks, and leverage ideas from biology to improve artificial neural networks. First, I present a new set of computational tools for processing, analyzing and understanding large-scale datasets in neuroscience. Applying these tools to calcium imaging from direction-selective neurons in the fruit fly visual system, I identify the algorithm the fly uses for computing motion, resolving a nearly 60 year old debate in fly visual neuroscience. In the second part of this thesis, I draw inspiration from neuroscience to advance the capabilities of artificial neural networks. By augmenting neural networks with higher-dimensional synapses, I drastically improve the ability of neural networks to acquire new information without forgetting old information when learning sequences of tasks. I also demonstrate how Poisson-like noise often found in biological systems can be incorporated into artificial neural networks to improve their sparsity, robustness, and ability to generalize. Finally, I demonstrate the reason neural networks are so expressive by analyzing signal propagation in random neural networks using tools from Riemannian geometry and mean field theory. Increasing the depth of even random neural networks exponentially increases their expressivity allowing them to disentangle highly complex manifolds in input space. The results presented in this thesis highlight the increasingly strong relationship between machine learning and neuroscience, both in terms of tools for understanding neural systems as well as inspiration for the capabilities and mechanisms needed for building artificial intelligence.

The popularity of wearable and mobile devices, including smartphones and smartwatches, has generated an explosion of detailed behavioral data. These massive digital traces provide us with an unparalleled opportunity to realize new types of scientific approaches that enable novel insights about our lives, health, and happiness. However, gaining actionable insights from these data requires new computational approaches that turn observational, scientifically "weak" data into strong scientific results and can computationally test domain theories at scale. In this dissertation, we describe novel computational methods that leverage digital activity traces at the scale of billions of actions taken by millions of people. These methods combine insights from data mining, social network analysis, and natural language processing to improve our understanding of physical and mental well-being: (1) We show how massive digital activity traces reveal unknown health inequality around the world, and (2) how personalized predictive models can support targeted interventions to combat this inequality. (3) We demonstrate that modeling the speed of user search engine interactions can improve our understanding of sleep and cognitive performance. (4) Lastly, we describe how natural language processing methods can help improve counseling services for millions of people in crisis.

Among all digital representations we have for real physical objects, 3D is arguably the most expressive encoding. 3D representations allow storage and manipulation of high-level information (e.g. semantics, affordances, function) as well as low-level features (e.g. appearance, materials) about the object. How much we can understand and transform the 3D world is thus largely determined by the performance of algorithms that analyze and create 3D data. While 3D visual computing has predominantly focused on single 3D models or small model collections, the amount of accessible 3D models has increased by several orders of magnitude during the past few years. This significant growth pushes us to redefine 3D visual computing from the perspective of big 3D data. In the thesis, a series of topics on data-driven 3D visual computing will be discussed. These include: constructing an information-rich large-scale 3D model repository, generating synthetic data for supervising neural networks, and learning end-to-end neural networks for analysis and synthesis of 3D geometries. Under the guiding principle of using large-scale 3D data for representation learning, the efforts described in this thesis have led to top-performing algorithms for pure-3D data processing, as well as 3D-assisted semantic, geometric and physical property inference from 2D images. The thesis will conclude by describing several promising directions for future research.

From Twitter hashtags such as #metoo to protests by Amazon Mechanical Turk workers in the public sphere, collectives come together online to make progress on shared issues. Research has long celebrated the web's affordances for galvanizing such coordinated action. By lowering the costs of communication, the web promises to enable distributed collectives to gather and act around shared issues. However, in practice even highly motivated collectives often fail to envision shared outcomes and act on them collectively. This dissertation introduces social computing systems that directly center trust and familiarity to more effectively support collective action. I will demonstrate this concept through three projects. The first, Hive, explores how social systems can help build strong networks by organizing a collective into small teams, then intermixing viewpoints by gradually rotating team membership. I deployed this project with Mozilla to reimagine accessible web browsing with disability advocates online. The second project, Huddler, demonstrates an algorithmic solution to the problem of teams benefiting from highly familiar members but experiencing unpredictable availability. Finally, the third project, Dynamo, shows how structured human labor can help move efforts forward when they stall. I undertook this project in collaboration with worker rights advocates on Amazon Mechanical Turk. Through the body of work in this dissertation I envision alternate roles for social computing ecosystems in society that directly support efforts for social change.

Current trends in technology scaling, coupled with the increasing compute demands with a limited power budget, has spurred research into specialized accelerator architectures. Field-Programmable Gate Arrays (FPGAs) have gained traction in the past few years as energy- efficient accelerator subtrates as they avoid the energy overheads of instruction-based processor architectures with a statically programmable data path. FPGA architectures sup- port fine-grained reconfigurability at the bit level, which provides flexibility required to implement arbitrary state machines and data paths. However, bit-level reconfigurability in FPGAs creates programming inefficiencies; low-level programming models limit the accessibility of FPGAs to expert hardware designers, and complicates the compiler flow which often takes several hours. Furthermore, bit-level reconfigurability also creates architectural inefficiencies, which increases area and power overheads while reducing compute density. This dissertation addresses both programming and architectural inefficiencies of FPGAs, by describing a compiler flow and a new reconfigurable architecture based on high- level parallel patterns. Parallel patterns are high-level programming abstractions under- lying several domain-specific languages (DSLs) that capture parallelism, memory access information and data locality in applications. To address programming inefficiencies, a new representation based on composable, parameterized hardware templates is proposed that is designed to be targeted from parallel patterns. These templates are designed to capture nested parallelism and locality in applications, and parameterized to expose the application design space to the compiler. A compiler flow is described that performs two key transformations: tiling, and metapipelining, to automatically translate parallel patterns to templates, and hardware. Evaluation of the compiler framework on a Stratix V FPGA shows speedups of up to 39.4× over an optimized baseline. To address architectural inefficiencies, this dissertation proposes a new coarse-grained reconfigurable architecture (CGRA) called Plasticine. Plasticine is built with reconfigurable primitives that natively exploits SIMD, pipelined parallelism, and coarse-grained parallelism at multiple levels. A configurable on-chip memory system with programmable address generation, address interleaving across banks, and buffering enables efficiently exploiting data locality and sustain compute throughput for various access patterns. Pipelined, static interconnects at multiple bus widths allow communication at multiple granularities while minimizing area overhead. Dedicated off-chip address generators and scatter-gather units maximize DRAM bandwidth utilization for dense and sparse accesses. With an area footprint of 113mm2 in a 28-nm process and a 1-GHz clock, Plasticine has a peak floating-point performance of 12.3 single-precision Tflops and a total on-chip memory capacity of 16 MB, consuming a maximum power of 49 W. Plasticine provides an improvement of up to 76.9× in performance-per-watt over a conventional FPGA over a wide range of dense and sparse applications.

For decades, legal and policy analysis of data privacy issues have tended to be informed by factual assumptions rather than rigorous empirics. The motivation for this dissertation is to recast these assumptions into a set of empirical computer science research questions. Decision makers are, in essence, relying on a set of heuristics to analyze data privacy issues. Are the assumptions behind those heuristics accurate, and what are the consequences of applying those heuristics? The first chapter of this dissertation examines third-party web tracking and advertising, an area that has vexed policymakers in both the United States and Europe. The chapter contributes new methodologies for measuring web tracking, including instrumenting an ordinary web browser and simulating user activity (FourthParty) and collecting tracking-related data directly from ordinary users (BrowserSurvey). The results include new perspectives on the web tracking marketplace, identification of numerous non-cookie tracking technologies, and evidence of inconsistent performance and usability from consumer control mechanisms. The chapter also presents a new design for privacy-preserving third-party advertising (Tracking Not Required) that would provide a specific privacy guarantee, would not require modifying browsers, and would be externally auditable. The second chapter analyzes the distinction between metadata and content, a concept that is foundational to surveillance law and policy in the United States and worldwide. The chapter contributes a new crowdsourcing methodology for studying telephone metadata privacy. It then uses a crowdsourced dataset to demonstrate that telephone metadata is densely interconnected, susceptible to re-identification, and enables highly sensitive inferences. The third chapter assesses data territoriality, another surveillance distinction that is shared by the United States and across the globe. Results from simulated browsing activity indicate that data territoriality is a poor fit for modern web architecture; Americans unknowingly send a large volume of domestic online activity outside the United States, and foreign citizens send a large volume of (from their perspective) domestic online activity into the United States. The conclusion considers the relationship between the computer science community and policymaking about data privacy. It suggests how computer scientists can and must play a greater role in government decision making, to ensure that policy and law reflect the best available privacy science.

The ability to automatically reason about programs and extract useful information from them is very important and has received a lot of attention from both the academic community as well as practitioners in industry. Scaling such program analyses to real system is a significant challenge, as real systems tend to be very large, very complex, and often at least part of the system is not available for analysis. A common solution to this problem is to manually write models for the parts of the system that are not analyzable. However, writing these models is both challenging and time consuming. Instead, we propose the use of guided randomized search to find models automatically, and we show how this idea can be applied in three diverse contexts. First, we show how we can use guided randomized search to automatically find models for opaque code, a common problem in program analysis. Opaque code is code that is executable but whose source code is unavailable or difficult to process. We present a technique to first observe the opaque code by collecting partial program traces and then automatically synthesize a model. We demonstrate our method by learning models for a collection of array-manipulating routines. Second, we tackle automatically learning a formal specification for the x86-64 instruction set. Many software analysis and verification tools depend, either explicitly or implicitly, on correct modeling of the semantics of x86-64 instructions. However, formal semantics for the x86-64 ISA are difficult to obtain and often written manually with great effort. Instead, we show how to automatically synthesize formal semantics for 1,795 instruction variants of x86-64. Crucial to our success is a new technique, stratified synthesis, that allows us to scale to longer programs. We evaluate the specification we learned and find that it contains no errors, unlike all manually written specifications we compare against. Third, we consider the problem of program optimization on recent CPU architectures. These modern architectures are incredibly complex and make it difficult to statically determine the performance of a program. Using guided randomized search with a new cost function we are able to outperform the previous state-of-the-art on several metrics, sometimes by a wide margin.

Domains such as law, healthcare, and public policy often involve highly consequential decisions which are predominantly made by human decision-makers. The growing availability of data pertaining to such decisions offers an unprecedented opportunity to develop machine learning models which can help humans in making better decisions. However, the applicability of machine learning to such scenarios is limited by certain fundamental challenges: a) The data is selectively labeled i.e., we only observe the outcomes of the decisions made by human decision-makers and not the counterfactuals. b) The data is prone to a variety of selection biases and confounding effects. c) The successful adoption of the models that we develop depends on how well decision-makers can understand and trust their functionality, however, most of the existing machine learning models are primarily optimized for predictive accuracy and are not very interpretable. In this dissertation, we develop novel computational frameworks which address the aforementioned challenges, thus, paving the way for large-scale deployment of machine learning models and algorithms to address problems of significant societal impact. We first discuss how to build interpretable predictive models and explanations of complex black box models which can be readily understood and consequently trusted by human decision-makers. We then outline novel evaluation strategies which allow us to reliably compare the quality of human and algorithmic decision-making while accounting for challenges such as selective labels and confounding effects. Lastly, we present approaches which can diagnose and characterize biases (systematic errors) in human decisions and algorithmic predictions.

Many suspect that decisions in employment, college admissions, lending, and the criminal justice system are systematically biased against certain groups. To date, efforts to provide statistical support for these concerns are often hampered by subtle statistical flaws that are known to affect popular tests for discrimination. The first part of this dissertation introduces these tests and their flaws, before proposing two new statistical tests for discrimination. The threshold test uses a hierarchical Bayesian model to identify the standards that decision-makers apply to different protected groups, while risk-adjusted regression aims to determine whether observed differences in treatment are justified by legitimate policy goals. Decisions aided by machine learning algorithms have also come under scrutiny for bias. As humans use machines to inform more and more consequential decisions, it is becoming crucial to understand how bias might occur in algorithmic systems. The study of identifying bias in algorithmic decisions is young, and many of the initial approaches suffer from the same statistical limitations as tests for bias in human decisions. The second part of this dissertation explores these approaches to algorithmic fairness, demonstrates their deficiencies, and provides a framework for the development of fair algorithmic decisions. Throughout this dissertation we apply our methods to large datasets from the US criminal justice system, studying citizens' interactions with the police and defendants' interactions with the courts. Despite this criminal justice focus, our work is applicable to studying bias in any domain, whether the decisions are made by humans or algorithms.

Non-interactive argument systems are an important building block in many cryptographic protocols. In this work, we begin by studying non-interactive zero-knowledge (NIZK) arguments for general NP languages. In a NIZK argument system, a prover can convince a verifier that a statement is true without revealing anything more about the statement. Today, NIZK arguments can be instantiated from random oracles, or, in the common reference string (CRS) model, from trapdoor permutations, pairings, or indistinguishability obfuscation. Notably absent from this list are constructions from lattice assumptions, and realizing NIZKs (for general NP languages) from lattices has been a long-standing open problem. In this work, we make progress on this problem by giving the first construction of a multi-theorem NIZK argument from standard lattice assumptions in a relaxed model called the preprocessing model, where we additionally assume the existence of a trusted setup algorithm that generates a proving key (used to construct proofs) and a verification key (used to verify proofs). Moreover, by basing hardness on lattice assumptions, our construction gives the first candidate that plausibly resists quantum attacks. We then turn our attention to constructing succinct non-interactive arguments (SNARGs) for general NP languages. SNARGs enable verifying computations with substantially lower complexity than that required for classic NP verification. Prior to this work, all SNARG constructions relied on random oracles, pairings, or indistinguishability obfuscation. This work gives the first lattice-based SNARG candidates. In fact, we show that one of our new candidates satisfy an appealing property called "quasi-optimality, " which means that the SNARG simultaneously minimizes both the prover complexity and the proof size (up to polylogarithmic factors). This is the first quasi-optimal SNARG from any concrete cryptographic assumption. Again, because of our reliance on lattice-based techniques, all of our new candidates resist quantum attacks (in contrast to existing pairing-based constructions).

When a person says something that has multiple possible interpretations, which interpretation stands out as the most likely intended meaning often depends on context outside the utterance itself: salient objects in the environment, utterances the speaker could have chosen but didn't, common-sense knowledge, etc. Systematically predicting these contextual effects is a major unsolved problem in computational natural language understanding. A recently-developed framework, known in cognitive science as the rational speech acts (RSA) model, proposes that speaker and listener reason probabilistically about each other's goals and private knowledge to produce interpretations that differ from literal meanings. The framework has shown promising experimental results in predicting a wide variety of previously hard-to-model contextual effects. This dissertation describes a variety of methods combining RSA approaches to context modeling with machine learning methods of language understanding and production. Learning meanings of utterances from examples avoids the need to build an impractically large, brittle lexicon, and having models of both speaker and listener also provides a way to reduce the search space by sampling likely subsets of possible utterances and meanings. Using recently-collected corpora of human utterances in simple language games, I show that a combination of RSA and machine learning yields more human-like models of utterances and interpretations than straightforward machine learning classifiers. Furthermore, the RSA insight relating the listener and speaker roles enables the use of a generation model to improve understanding, as well as suggesting a new way to evaluate natural language generation systems in terms of an understanding task.