- 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