oncomputable Spectral Set



For my Mama, whose \*-minimal index is computable (because it's finite).

Love the Ma.

It seems nothing short of a miracle that I now find myself in a position to graduate with a doctorate in mathematics. This thesis is the product of contributions from a few outstanding individuals that I've known (in the biblical sense) along my academic path. Without the personal connections that I am about to mention, there would indeed be no work here to acknowledge.

In the summer of 2004, I showed up on Lance Fortnow's doorstep in Chicago, poised to learn something about computer science. Not only did Lance *not* send me home (which would have been impossible anyway, since I didn't come from anywhere), he completely encouraged me to learn. Lance dedicated enormous time and energy to helping me achieve excellence in my research. Not only did he provide me with invaluable guidance and fill me with enthusiasm for my academic work, but in a formal sense, he allowed me to continue my studies by taking me on as a PhD student. When people read this PhD dissertation a hundred years from now, Lance Fortnow will undoubtedly be remembered for his outstanding research contributions to the field of theoretical computer science. But in 2107, this thesis will also remind readers that Lance is an exceptional mentor who showed exceeding kindness towards strangers. His efforts have made all the difference. Thanks for taking a chance on me.

I would like to thank the faculty, staff, and administration at University of Chicago and its Computer Science Department, as well as the affiliates of the Committee on Institutional Cooperation for providing me with all of the resources I needed to complete a research dissertation in mathematics during these past two years. Not only have these institutions provided me with access to an exceptional educational opportunities in theoretical computer science, but they also helped me to formally complete the degree requirements at my home institution. Even though I was never a degree student at University of Chicago, I've always felt like family.

Thanks to my mom and dad, who provided me with support when my home institution wasn't able to. In 2004, my parents gave me a place to live, a lot of tasty food, and a bit of encouragement when I really needed it.

Thanks to Professor William Ziemer and Chunlai Zhou, who together taught me the love of mathematical analysis early on in my graduate career. Chunlai, in particular, has been a most insightful study companion. His contagious commitment to learning surely contributed to my passing grades on the math qualifying exams during my first year of graduate school.

Inspiration for this project came from Marcus Schaefer, Robert Soare, and Joe Miller. Marcus Schaefer invented the tantalizing ${\mathrm{MIN}}^*$ problem, the catalyst for this entire work. Robert Soare not only invited me to his enlightening computability theory class this year, but he also shared some technical suggestions which gave me confidence to prove a couple of the hard theorems in this thesis. In 2003, I first experienced computability theory during Joe Miller's office hours for Recursion Theory. Although I had a scheduling conflict which prevented me from ever attending his lectures, I discovered the beautiful nature of computability theory outside of class time, thanks to the instructor's patience and enthusiasm.

Thanks to Kevin Zumbrun and Misty Cummings at Indiana University, whose efforts ultimately assembled the bureaucratic pieces of my academic career and allowed me to earn a doctorate in mathematics. For his contributions as a mentor, I'd also like to thank Larry Moss, who would have been on my dissertation committee had he not moved to Africa this year.

Finally, I would like to acknowledge my colleagues at University of Chicago, especially Parinya Chalermsook and Raghav Kulkarni, who introduced me to the field of computer science. And Gabriela Turcu, who went ice skating with me sometimes.

Goodnight, and g-d bless America.

{'source': 'arXiv_out/math0701904_extract_spectral'}