Inexpensive and ubiquitous access to data on massive scales is having a profound and transformative impact on most scientific disciplines. In particular, data-driven computational models bring insights into complex phenomena ranging from genetic mutations to urban traffic patterns, social dynamics, ecological changes, etc. In fact, data are available in such an abundance today that the critical bottleneck has shifted to "analytics": algorithms that can make sense of these data.

Apart from the obvious difficulties brought by the massive volumes of these data, a major challenge in data analytics is the inevitable presence of uncertainty. Most natural and social systems are highly unpredictable, and man-made systems are often fallible: devices fail and bonds break unexpectedly, and a myriad of confounding variables can only be accounted for through statistical means. Apart from such inherent randomness, measurement and recording tools are rarely perfect: be it a GPS trace, a LiDAR scan, a medical image, or a biological recording, the data we obtain are often entangled with noise, error, and uncertainty, and a stochastic framework is the only meaningful way to process it.

In computer science and mathematical optimization, a number of models and approaches have been considered to account for, and analyze the effect of uncertainty: random graphs, stochastic geometry, Bayesian analysis, and multi-stage stochastic optimization being some prominent examples. Most of the classical random models focus on asymptotic results on random point sets or random graphs, while much of the current research on stochastic optimization is focused on two-stage models, where one trades the current uncertainty with future price inflation. In short, most of these models and techniques are either too abstract or too application-specific, and there remains a need for basic, general models and algorithms that can be adapted to a broader class of applications.

In this dissertation, we revisit several classical problems under an uncertainty-aware lens, i.e., with the assumption that the input data is only probabilistically available to the algorithm. We study how the stochasticity of input data affects the complexity of basic combinatorial and geometric structures such as minimum spanning trees, nearest neighbors, and traveling salesman tours, proposing several hardness results and approximation algorithms for such problems. Besides developing a fundamental theory, we also discuss some real-world applications that benefit from this theory.