The main topic of this thesis is the study of the Minimum Circuit Size Problem (MCSP). MCSP is a decision problem: Given the truth table of a finite Boolean function and a size parameter 0 <= theta <= 2^n - 1 (in binary), is there a Boolean circuit C of size at most theta such that C computes f? MCSP is an important problem due to its unexpected connections to many other areas of complexity theory, such as learning, pseudorandomness, and average-case complexity. In a similar manner, Kolmogorov complexity poses the following question: Given a string x, what is the size of the smallest program that outputs x when run on the empty string? While Kolmogorov complexity cannot be computed, in general, there are resource-bounded versions of Kolmogorov complexity that are computable and have been very influential in complexity theory, just like MCSP is. In this work, we study MCSP and some of its Kolmogorov complexity counterparts, and answer the following two questions. 1. What is the complexity of MCSP? That is, how easy or difficult is it to compute MCSP? We prove MCSP lower bounds against several restricted models of computation. These, among others, include formulas, branching programs, constant-depth circuits, and one-tape Turing machines. Almost all of the above lower bounds are the first of their kind for MCSP, and almost match the state-of-the-art lower bounds against these models. 2. What are some interesting applications of MCSP? Here, we show that the average-case hardness of a conditional Kolmogorov complexity counterpart of MCSP is almost equivalent to the existence of one-way functions (OWFs). Along with the concurrent and independent work by Liu and Pass, this is one of the first natural NP-complete problems whose average-case hardness is shown to be (almost) equivalent to the existence of OWFs.