Abstract: As AI systems increasingly interact with complex, high-dimensional data — from graphs to natural language — ensuring their reliability becomes both more critical and more challenging. In this talk, I explore the emerging foundations of reliable AI in complex domains, where structured and unstructured data collide. I will first highlight the intrinsic fragility of Graph Neural Networks and Large Language Models, discussing vulnerabilities arising from adversarial attacks and data memorization. Moving from diagnosis to solutions, I will present recent advances on robustness certification, reliable conformal prediction, and efficient strategies for adversarial training that aim to repair trust after deployment. Throughout the talk, I will draw connections between robustness, uncertainty, and privacy, showing how these elements are not isolated challenges, but components of a broader agenda: learning to trust complexity.