For many data-intensive real-world applications, such as recognizing objects from images, detecting spam emails, and recommending items on retail websites, the most successful current approaches involve learning rich prediction rules from large datasets. There are many challenges in these machine learning tasks. For example, as the size of the datasets and the complexity of these prediction rules increase, there is a significant challenge in designing scalable methods that can effectively exploit the availability of distributed computing units. As another example, in many machine learning applications, there can be data corruptions, communication errors, and even adversarial attacks during training and test. Therefore, to build reliable machine learning models, we also have to tackle the challenge of robustness in machine learning.

In this dissertation, we study several topics on the scalability and robustness in large-scale learning, with a focus of establishing solid theoretical foundations for these problems, and demonstrate recent progress towards the ambitious goal of building more scalable and robust machine learning models. We start with the speedup saturation problem in distributed stochastic gradient descent (SGD) algorithms with large mini-batches. We introduce the notion of gradient diversity, a metric of the dissimilarity between concurrent gradient updates, and show its key role in the convergence and generalization performance of mini-batch SGD. We then move forward to Byzantine distributed learning, a topic that involves both scalability and robustness in distributed learning. In the Byzantine setting that we consider, a fraction of distributed worker machines can have arbitrary or even adversarial behavior. We design statistically and computationally efficient algorithms to defend against Byzantine failures in distributed optimization with convex and non-convex objectives. Lastly, we discuss the adversarial example phenomenon. We provide theoretical analysis of the adversarially robust generalization properties of machine learning models through the lens of Radamacher complexity.

We are witnessing an unprecedented growth in the amount of data being sensed, collected and processed to drive modern applications across many domains. This growth has challenged classical algorithms to scale up to big-data regimes. Because time is critically important in settings such as control and decision-making, interventional medical imaging, and security, speeding up widely-used routines has the potential to open up the application space.

In this thesis, we focus on six problems of fundamental importance, and develop fast algorithms for solving them whenever there is an underlying structure of sparsity, which typically holds in most natural settings. Our algorithms attain their speed by being sample and computationally efficient whenever there is sparsity. In particular, the problems we study and a summary of our results are as follows. (1) We propose a novel architecture for sampling continuous-time signals that have band-limited and sparse spectra at their minimum sampling rate, which can be much lower than the Nyquist rate. (2) We improve the noise robustness of divide-and-conquer-based sparse Discrete Fourier Transform algorithms by developing a novel method for fast and sample-efficient frequency identification. (3) We develop a fast algorithm for recovering sparse wavelet coefficients of a signal from its Fourier domain samples. This setting arises in Magnetic Resonance Imaging, and our approach provides a theoretical framework for fast imaging. (4) We propose a sample and computationally efficient algorithm for recovering sparse pseudo-Boolean functions with application to learning a DNA repair outcomes for CRISPR-Cas9 experiments. (5) We propose a computationally efficient method for coded computation to reduce the effect of slow computational nodes in distributed matrix multiplication. (6) We propose a computationally efficient algorithm for large-scale matrix multiplication whenever the output is sparse with application to database search.

Our approach in tackling these diverse problems is based on a unifying divide-and-conquer strategy, where by leveraging ideas from modern coding theory (in particular, Low Density Parity Check Codes) which have previously been studied in the context of communications, we create structures that enable simple and fast peeling-based recovery.

An emerging challenge in recent years for engineers, researchers, and data scientists across the globe is to acquire, store, and analyze ever-increasing amounts of data. In the past decade, a new paradigm in data acquisition called ``compressed-sensing" has emerged to cope with this data explosion. Compressed sensing exploits the fact that in many applications, although the signal of interest has a large ambient dimension, the relevant information resides in a significantly lower dimensional space. For example, the Magnetic-Resonance-Imaging (MRI) data is sparse in the wavelet-domain. In this thesis, we consider the problem of computing a sparse Discrete-Fourier-Transform of a high-dimensional signal from its time-domain samples, as a representative example of compressed-sensing problems. We use this problem to investigate the tradeoff between the number of measurements, noise robustness, and the computational complexity of the recovery algorithm in compressed sensing problems.

We propose a new family of deterministic sparse sensing matrices, obtained by blending together diverse ideas from sparse graph codes, digital signal processing, and number-theoretic concepts like the Chinese-remainder-theorem (CRT). The specific sparse structure of the proposed family of measurement matrices further enables a Peeling-based Ultra-Low complexity algorithms for Sparse signal Estimation, that are accordingly dubbed PULSE algorithms. Further, using the CRT, we establish an intimate connection between the problem of computing a sparse DFT of a signal and decoding over an appropriately designed sparse graph code. This connection is then exploited 1) to design a sample efficient measurement matrix and a low-complexity peeling-style iterative recovery algorithm, and 2) to perform a rigorous analysis of the recovery algorithm by wielding powerful and well-established analytical tools like density-evolution, martingales, and expander graphs from the coding theory literature. In particular, we show that under some mild conditions a k-sparse n-length DFT of a signal can be computed using (nearly optimal) 4k measurements and O(k log k) computations. As a concrete example, when k=300, and n = 3.8 x 10^6, our algorithm achieves computational savings by a factor of more than 6000, and savings in the number of input samples by a factor of more than 3900 over the standard Fast-Fourier-Transform (FFT) algorithms. This can be a significant advantage in many existing applications and can enable new classes of applications that were not thought to be practical so far. Next, we extend these results to the case of noise-corrupted samples, computing sparse 2D-DFTs as well as to interpolation of multi-variate sparse polynomials over the complex field and finite fields. We also demonstrate an application of the proposed PULSE algorithm to acquire the Magnetic-Resonance-Imaging of the Brain. This provides some empirical evidence that PULSE algorithms are applicable for acquiring more

realistic signals. The proposed sensing framework and the recovery algorithm are sample efficient and robust against observation noise. We believe that this framework provides a possible direction towards designing efficient and low-power engineering solutions for sparse signal acquisition.

Big-data systems enable storage and analysis of massive amounts of data, and are fueling the data revolution that is impacting almost all walks of human endeavor today. The foundation of any big-data system is a large-scale, distributed, data storage system. These storage systems are typically built out of inexpensive and unreliable commodity components, which in conjunction with numerous other operational glitches make unavailability events the norm rather than the exception.

In order to ensure data durability and service reliability, data needs to be stored redundantly. While the traditional approach towards this objective is to store multiple replicas of the data, today's unprecedented data growth rates mandate more efficient alternatives. Coding theory, and erasure coding in particular, offers a compelling alternative by making optimal use of the storage space. For this reason, many data-center scale distributed storage systems are beginning to deploy erasure coding instead of replication. This paradigm shift has opened up exciting new challenges and opportunities both on the theoretical as well as the system design fronts. Broadly, this thesis addresses some of these challenges and opportunities by contributing in the following two areas:

(1) Resource-efficient distributed storage codes and systems:

Although traditional erasure codes optimize the usage of storage space, they result in a significant increase in the consumption of other important cluster resources such as the network bandwidth, input-output operations on the storage devices (I/O), and computing resources (CPU). This thesis considers the problem of constructing codes, and designing and building storage systems, that reduce the usage of I/O, network, and CPU resources while not compromising on storage efficiency.

(2) New avenues for erasure coding in big-data systems:

In big-data systems, the usage of erasure codes has largely been limited to disk-based storage systems, and furthermore, primarily towards achieving space-efficient fault tolerance---in other words, to durably store "cold'' (less-frequently accessed) data. This thesis takes a step forward in exploring new avenues for erasure coding---in particular for "hot'' (more-frequently accessed) data---by showing how erasure coding can be employed to improve load balancing, and to reduce the (median and tail) latencies in data-intensive cluster caches.

An overarching goal of this thesis is to bridge theory and practice. Towards this goal, we present new code constructions and techniques that possess attractive theoretical guarantees. We also design and build systems that employ the proposed codes and techniques. These systems exhibit significant benefits over the state-of-the-art in evaluations that we perform in real-world settings, and are also slated to be a part of the next release of Apache Hadoop.

In a free society, people have the right to consume and share public data without fear of retribution. However, today's technological landscape enables large-scale monitoring and censorship of networks by powerful entities (e.g., totalitarian governments); at worst, these entities may punish people for the information they consume or the opinions they espouse. This thesis considers two problems aimed at empowering people to freely share and consume public information: anonymous message spreading and privacy-preserving database search. In both areas, we present algorithmic innovations and analyze their correctness and efficiency. The key assumption underlying our work is that centralized architectures cannot reliably provide privacy-preserving services; not only are the incentive structures misaligned, but centralized infrastructures are often vulnerable to external breaches by hackers or government agencies, for example. We therefore restrict ourselves to distributed algorithms that rely on cooperation and resource-sharing between privacy-conscious individuals.

In the area of anonymous message spreading, we consider a user who wishes to spread a message to as many people as possible over an underlying connectivity network (e.g., a social network); this is the premise of Yik Yak, Whisper, and other popular anonymous messaging networks. Most existing social networks (anonymous or not) use a push-based mechanism to spread content to all of a user's neighbors on the contact network; if a neighbor approves the content by `liking' it, this symmetric spreading propagates to the neighbor's neighbors, and so forth. Recent research suggests that under this spreading model, the true author of a message can be identified with non-negligible probability by a powerful global adversary. We propose an alternative, distributed spreading mechanism called adaptive diffusion, which breaks this symmetry. We show theoretically that adaptive diffusion gives optimal or asymptotically-optimal anonymity guarantees over certain classes of synthetic graphs for various adversarial models, while spreading nearly as fast as traditional symmetric mechanisms. On real-world graphs, we demonstrate empirically that adaptive diffusion gives significantly stronger anonymity properties than existing spreading mechanisms.

In the area of privacy-preserving search, we consider the foundations of a distributed, privacy-preserving search engine built over public data. Architecturally, we envision a peer-to-peer (P2P) network in which each user stores a small piece of a public database; when a user wishes to search for something, she obtains it by requesting the information from her peer nodes, which execute a distributed search over the relevant data index. Critically, this operation should be privacy-preserving---that is, no peer node should learn anything about the contents of the user's query. Distributed search engines are not a new idea, but making such a service privacy-preserving and robust is algorithmically challenging.

One challenge is that if the database is changing over time and the network is not centrally controlled, distributed users may not have a unified view of the database. That is, some peers may be storing an outdated portion of the global database, causing existing private search and retrieval algorithms to fail. We introduce a distributed private retrieval algorithm that is robust to servers with similar, but not identical, views of the database, and show that it incurs asymptotically negligible overhead compared to traditional algorithms. Another challenge is that most search engine users submit queries with multiple keywords, and expect the result to contain all of the queried keywords; this is known as a conjunctive query. Existing distributed algorithms return results that contain at least one of the queried keywords. This approach can incur significant communication overhead, as well as computational overhead for the client, who must sort through the results. We propose a new privacy-preserving search algorithm that processes conjunctive queries while incurring a communication cost that scales linearly in the number of documents that contain all the queried keywords. Our private-search algorithms build on principles from distributed source coding, which permit us to reduce the communication cost by exploiting correlations between the data of distributed peer nodes.

Modern data centers have been providing exponentially increasing computing and storage resources, which have been fueling core applications ranging from search engines in the early 2000's to the real-time, large-scale data analysis of today. All these breakthroughs were made possible only due to the scalability in computing and storage resources offered by modern large-scale clusters, comprising individually small and unreliable low-end devices. Given the individually unpredictable nature of the underlying devices in these systems, we face the constant challenge of securing predictable and high-quality performance of such systems in the face of uncertainty.

In this thesis, distributed storage and computing systems are viewed through a coding-theoretic lens. The role of codes in providing resiliency against noise has been studied for decades in many other engineering contexts, especially in communication systems, and codes are parts of our everyday infrastructure such as smartphones, WiFi, cellular systems, etc. Since the performance of distributed systems is significantly affected by anomalous system behavior and bottlenecks, which we call "system noise", there is an exciting opportunity for codes to endow distributed systems with robustness against such system noise.

Our key observation – channel noise in communication systems is equivalent to system noise in distributed systems – forms the key motivation of this thesis, and raises the fundamental question: "can we use codes to guarantee robust speedups in distributed storage and computing systems?". In this thesis, three main layers of distributed computing and storage systems – storage layer, computation layer, and communication layer – are robustified through coding-theoretic tools. For the storage layer, we show that coded distributed storage systems allow faster data retrieval in addition to the other known advantages such as higher data durability and lower storage overhead; for the computation layer, we inject computing redundancy into distributed algorithms that are robust to stragglers or nodes that are substantially slower than the other nodes; for the communication layer, we propose a novel data caching and communication protocol, based on coding-theoretic principles that can significantly reduce the network overhead of the data shuffling operation, which is necessary to achieve higher statistical efficiency when running parallel/distributed machine learning algorithms.

Graph-structured data appears in many modern applications like social networks, sensor networks, transportation networks and computer graphics. These applications are defined by an underlying graph (e.g. a social graph) with associated nodal attributes (e.g. number of ad-clicks by an individual). A simple model for such data is that of a graph signal--a function mapping every node to a scalar real value. Our aim is to develop signal processing tools for analysis of such signals de- fined over irregular graph-structured domains, analogous to classical Fourier and Wavelet analysis defined for regular structures like discrete-time sequences and two-dimensional grids.

In this work, we start by reviewing the notion of a Graph Fourier Transform (GFT), which has been defined in the literature for graph signals. We examine the spatial and spectral features of circulant graphs, which accommodate linear shift-invariant operations. We describe fundamental operations such as shifting, sampling, graph-reconnection and linear filtering for signals on circulant graphs and derive associated sampling and graph-reconnection theorems. We also develop wavelet filter bank structures for multi resolution analysis of large-scale graphs.

We present a method to decompose an arbitrary graph into a linear combination of circulant graphs. This helps extend fundamental operations such as sampling, filtering and multi resolution filter banks to general graphs. We present an application in the area of graph semi-supervised learning where some of the existing algorithms can be viewed as suitably designed filters defined in the GFT domain. We propose a wavelet regularized learning algorithm and evaluate the performance on some real-world datasets.

The development of intelligent transportation systems is one of the most important strategies for making roads safer and more efficient. The key technology underpinning all such systems, from cooperative safety systems to electronic tolling, is wireless communications. Vehicles must be able to communicate with each other, and with fixed infrastructure, in real time. One promising architecture involves forming an ad hoc network among the vehicles and taking advantage of the peer-to-peer connectivity to reduce infrastructure costs.

In this dissertation, we consider the design and analysis of medium access control and network layer protocols for vehicular ad hoc networks. In particular, we examine the problem of distributing content over many hops from a source to a destination. The fundamental challenge in such systems is the inability of the vehicles to coordinate with each other. Because of the high frequency at which vehicles enter and exit the road, and the fact that vehicles may be moving at widely varying speeds, the topology is continuously changing. Therefore, centralized scheduling of transmissions to avoid collisions and global routing of packets is either technically infeasible or prohibitively expensive. We propose instead a class of uncoordinated protocols, based on randomized channel access and network coding. The key idea behind the coding is for the vehicles to transmit random combinations of all the packets that they have received, instead of simply forwarding packets. This scheme does not require link level feedback, and thus vehicles do not need to track the identities of their current neighbors.

We first consider a minimally coordinated protocol, where the vehicles on a road are partitioned into spatial blocks. The block structure is used to funnel waves of data down the road, while the vehicles within each block randomly contend with each other for the channel. We show that when the vehicles use network coding in this scheme, the end-to-end throughput is constant, as long as the number of blocks in the network does not grow exponentially in the vehicle density. Network coding allows for the reliable transport of data over many hops at the same rate at which data could be sent over a single hop.

Then we consider a completely uncoordinated protocol, which does not even require the assignment of vehicles to spatial blocks. We begin by providing a general algorithm for computing the throughput of an arbitrary network using such a protocol. The main technical contribution is to account for the fact that intermediate nodes may temporarily not have any new packets to transmit to their neighbors, due to the random channel access. We prove that the throughput of this wireless network is equal to the throughput of an equivalent wired network, despite the randomized medium access strategy. This result has application in a variety of other contexts, where it is often assumed for tractability that relays always have data when they use the channel.

We then apply this result to the problem of finding the throughput in an uncoordinated vehicular ad hoc network. In a congested highway, where the connectivity graph is homogeneous, a constant throughput can be provided to receivers that are located at an arbitrary distance from the source. In essence, every vehicle can be thought of as a digital repeater, despite the packet losses due to collisions.

In this thesis we study the data exchange problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side- information. Assuming that the file is broken into packets, the side-information considered is in the form of linear combinations of the file packets. Given that the collective information of all the users is sufficient to allow recovery of the entire file, the goal is for each user to gain access to the file while minimizing some communication cost. We assume that users can communicate over a noiseless broadcast channel, and that the communication cost is a sum of each user's cost function over the number of bits it transmits. For instance, the communication cost could simply be the total number of bits that needs to be transmitted. In the most general case studied in this thesis, each user can have any arbitrary convex cost function. We provide a polynomial time deterministic algorithm (in the number of users and packets) that finds an optimal communication scheme that minimizes the communication cost. To further lower the complexity, we also propose a simple randomized algorithm inspired by our deterministic algorithm which is based on a random linear network coding scheme. In the later chapters we consider a general form of side-information, where each user observes independent realizations of some joint random process. For such scenario, we provide a polynomial-time algorithm (in the number of users and packets) that finds an optimal communication rate allocations for all the users. Next, we study two extensions to the original data exchange problem. First, we consider the problem where not all users in the system are interested in obtaining the file, but they are willing to help users who are. Also, we explore the problem where each user can communicate only to its immediate neighbors through a wireline network. For both the problems, we provide a polynomial time algorithm that is inspired by the original data exchange problem.

When it is desired to transmit redundant data over an insecure and bandwidth-constrained channel, it is customary to first compress the redundant data and then encrypt it for security reasons. In this paper, we investigate the novelty of reversing the order of these steps, i.e. first encrypting and then compressing. Although counter-intuitive, we show surprisingly that through the use of coding with side information principles, this reversal in order is indeed possible. In fact, for lossless compression, we show that the theoretical compression gain is unchanged by performing encryption before compression. We show that the cryptographic security of the reversed system is directly related to the strength of the key generator.