As humans, we use language with ease and speed, solving the complex computational problem of processing form and meaning seemingly without effort. This dissertation studies how the properties of language enable us to achieve this, by investigating what is computationally difficult about language, and what is easy. We first investigate the principle of least effort, formalize it using contemporary machine learning methods, and argue that it can account for prominent typological patterns in word order. We then study the interplay of memory and surprisal in language processing, drawing on information-theoretic techniques to show that the order of words and morphemes efficiently trades off these aspects of complexity. Third, we investigate what makes language comprehension difficult for machines, proposing and validating a complexity metric that predicts the success of machine learning algorithms. Taken together, this dissertation introduces formal and computational techniques to precisely quantify the complexity of processing language, and to understand its implications for the structure of human language. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://bibliotheek.ehb.be:2222/en-US/products/dissertations/individuals.shtml.]