- Committee: Zeev Dvir (ZD), Manjul Bhargava (MB), Mihalis Dafermos (MD) - Special topics: Computational complexity, Algebraic number theory. - Note: Zeev told me he would cover Ch. 1-9 and 19-21 of Arora/Barak's computatioal complexity book (focus on derandomization.) - Analysis (MD) - Tell me about L^p spaces. Define L^p space. (He made sure I quotiented out by f=g a.e.) - What kind of space is it? Show that L^p is complete. (I take p=1, take a Cauchy sequence, take a subsequence, and got stuck.) What theorem applies? (I state Monotone and Dominated Convergence Theorems and use them.) What about general p? (I got stuck with where I should put powers of p. They let me go on this one.) - For which p is L^p a Banach space? What goes wrong when p<1? - What is the best L^p space? (p=2) What is it called? What is a Hilbert space? Show that L^p for p\ne 2 is not a L^p space. (I get stuck.) Can you derive an equation involving the norm? (MD leads me towards the parallelogram law. I reduce to showing in \R^2 that L^1 norm does not satisfy the parallelogram law. The random numbers I came up with just happen to fail, so I stare at this for a long time. "If it were true this would be a polynomial identity." They tell me to plug other numbers in. Eventually I get it, and we have a good laugh.) - Complex analysis (MD, MB) - Define a holomorphic/meromorphic function. - State Cauchy's Theorem. Sketch the proof. (I just sketch Goursat's theorem, and then mention the integral of 1/z is 2\pi i.) - What can you say about f' for f holomorphic? (f has derivatives of all orders, it's analytic.) - Classify singularities. Does Cauchy's theorem work for an essential singularity? (Yes.) - MB: Give a function that can be analytically continued. (Zeta function. I mention partial summation to define it for Re z>0, you can prove a functional equation to extend it.) What is the functional equation? - MB: Consider the gamma function, what are the poles? What is the gamma function? Analytically continue it. (I write down the integral definition and the product formula; that's good enough for them.) How do you know it has a pole at 0? (The integral diverges.) What is a functional equation for Gamma? - MB: What can you say about the zeros of the zeta function? (Conjecturally real part 1/2, also trivial zeros at negative integers.) How can you show it has zeros at negative integers? - MB: What are the implications of the Riemann hypothesis for computational complexity? (Can deterministically find a prime. I couldn't think of an algorithm this would be useful for off the top of my head.) - MB: Is there a polynomial time algorithm for polynomial factorization? (Nonstandard question - didn't get this. Manjul explains the LLL algorithm.) - MD: Give a conformal map from the pizza slice (45 degree sector) to the unit disc. What is the general theorem? - MD: Do you know the proof of the Riemann mapping theorem? (Yes.) In that proof you use a theorem involving compactness. State it. (I state Arzela-Ascolli.) - Algebra (MB) - Classify all groups of order 10. Don't use the Sylow Theorems! How do you know that G has an element of order 5? (I get stuck.) If it only had elements of order 2, what can you say about G? (It's abelian, and is a 2-group. Now I have an element of order 5 I finish the proof.) - Classify integral domains of order 10. (There aren't any.) Any finite integral domain is a field. Why? - Complexity theory (ZD) - Define P and BPP. - Define a pseudorandom generator.If you had a PRG (what parameters?) how could you show P=BPP? There exist PRG's, why does this not show BPP=P? (The PRG has to be uniformly generated, against nonuniform circuits) - Are there functions which require large circuits? (Yes, 2^n/n by information theoretic argument) - What reason do we have to believe P=BPP? (Hard functions imply PRG's.) State this as a theorem and sketch the proof. (Combinatorial designs, Nisan-Wigderson generator.) - Algebraic number theory (MB) - Is there a polynomial that doesn't factor in \Z but splits for every mod p for every p? (I say no, and attempt to prove this, but I was proving something different, that you can't have the polynomial split completely for every p. Manjul says there is an example, and leads me through finding one.) - What does the factorization of f mod p tell you about the Galois group of the splitting field? How do you show this? (There is an element with cycle structure given by degrees of factors. Reduce modulo p. Look at the Frobenius element.) What is the decomposition group? How does it map to the Galois group of the finite field? What is the Galois group of the finite field? - The easiest example is x^4+1. But you characterized all examples. For which n is there a polynomial of degree n that factors mod all p but not in Z? Why? (p not prime) How do you construct it for n not prime? (Didn't know this. Manjul: take the wreath products of S_m, S_n in S_{mn}.) - Is Z[\sqrt{-5}] an Euclidean domain? (I show it's not a PID, so not an Euclidean domain.) Is it the ring of integers in its fraction field? What's an element that factors in 2 ways? What about Z[\sqrt 5]? What are the discriminants? What primes ramify in the field extensions? - What is a formula for the discriminant? (I mumble about norm of f'. Manjul wants an expression in terms of roots. I say \prod_{i\ne j} (\alpha_i-\alpha_j).) That expression isn't right. Why not? (The sign's wrong. I stumble to find the right power of (-1).) It should be \prod_{i