Daniel Carter's generals Committee: Maria Chudnovsky (MC), Zeev Dvir (ZD), Jacob Shapiro (JS) Special topics: Graph theory and computational complexity May 9, 2024, 2pm in MC's office. I was extraordinarily nervous coming into this exam, worrying I was severely underprepared, particularly about real analysis. Coming into the school year my strongest subjects were the two special topics (naturally) and complex analysis, which was the standard topic course I took most recently and the only one I did not take during the pandemic. I studied my special topics pretty intensely, since I figured if I did well enough on those they would forgive poorer performance on the standard topics. Some statistics about my studying are given at the end. Additional important background is that I was an undergrad at Princeton as well, and MC was my senior thesis advisor. ZD, JS, and I all arrive around the same time, but MC was not in her office. We stand around awkwardly in the hallway until she arrives. When we enter they chat for a bit about who wants to start, and also who is going to ask about algebra. MC suggests JS starts and I didn't get the chance to protest. I would have wanted to start with graph theory because that was what I was most confident in, but it worked out fine this way. REAL ANALYSIS I never took a measure/integration theory course in undergrad, instead opting for Fourier analysis. I took functional analysis with JS the previous semester. When I met with JS to discuss what I should prepare, he was shocked I hadn't taken measure theory and wondered how I could have understood anything in functional analysis. He said that anything in all three Rudin books is fair game. This made me very nervous. A few days after meeting I emailed him asking that we limit it to Baby Rudin, a subset of chapters from Papa Rudin, and the first part of Grandpa Rudin (he did not respond); I studied that plus a subset of the course notes from functional analysis. We in fact did not talk about functional analysis at all, so I wasted a lot of time preparing for that, and in fact all of the real analysis questions were complete softballs. JS: Give a function on (0, 1) that is integrable but whose square is not integrable. I write down 1/x^1.5 but quickly correct it to 1/sqrt(x). JS: Give a convergent sequence of functions on (0, 1) whose integrals do not converge to the integral of the limit. I state a_n/x^(b_n) will work for cleverly chosen a_n, b_n; where the integral of each of them will be 1, but the functions converge to the zero function. JS asks for more details, so I compute the integral and determine what the relationship between a_n and b_n needs to be. JS: State and prove the monotone convergence theorem. (I do this.) What setting does this hold in? I change the dx I had written in the theorem statement to dmu and change "R -> R" to "X -> R". JS: What is X? (A measure space???) Yes, that's what I wanted to hear. Give an example of a nowhere-dense set with positive measure. The fat Cantor set works. Do you want me to define it? JS: No, that's fine. Prove that the limit of a uniformly convergent sequence of continuous functions on (0, 1) is continuous. I start writing an epsilon-delta proof. JS: No, try to prove it using the dominated convergence theorem. Actually, state and prove DCT first. I state DCT and Fatou. I then prove DCT from Fatou, but we both get confused in the middle of it because of where on the board I placed it, it looked like I was trying to prove Fatou. We sort it out and then I prove Fatou on another part of the board. I then return to the uniform convergence thing and say "I guess you can take g = sup f_n or something like that and apply DCT?" JS: Maybe, but it is easier than that in (0, 1). [I don't know what he is alluding to. I have only ever seen the uniform convergence thing proved with epsilon-delta.] Let's move on. Give an example of a sequence of continuous functions that converges but not to a continuous function. I give the standard example using a linear interpolation thing converging to a step function. JS: What is the Borel--Cantelli lemma? (I don't know.) Okay, nevermind. Give an example of a 2-dimensional function where {limit x -> inf of limit y -> inf,  limit y -> inf of limit x -> inf, and limit x=y -> inf} are distinct. I write down: 0 0 0 0 1 ... 0 0 0 1 2 ... 0 0 1 2 2 ... 0 1 2 2 2 ... 1 2 2 2 2 ... so the two iterated limits are 0 and 2 and the diagonal limit is 1. JS: What is the Fréchet derivative? (I don't know.) [He pronounced it roughly/ˈfrɛˌt͡ʃət/, so I really had no idea what he is talking about.] Okay, how is the derivative defined on R^n -> R functions? I start writing down the partial derivative. JS: No, the total derivative. (What?) Okay, what does it *mean* for a function to be differentiable? (I don't know what you're asking for.) You want it to be approximated by a linear function. Oh! I then remember what the total derivative is and write down the definition. While writing the numerator inside the limit I write "f(x + h) - Lh" and JS says "no, minus f(x)" and I say "Oh, I was writing them in the other order". JS: What does this imply about the thing you were writing before? The partial derivative exists by choosing h = scalar*e_k in the total derivative limit. JS: Write down the Taylor series of a function R^n -> R to order 2. I thought he said R^2, so I start writing it down with partial derivatives and x and y. JS: No, in n dimensions, and also use vector notation. (Vector notation?) Like use the gradient or multi-index notation. I write the first-order term using the gradient but then realize I don't know how to write the second-order term. I ask to switch to multi-index notation (JS: Sure, but convert back afterwards.) and write the second-order term. I convert back but don't remember what the Hessian is called (but I write its definition). JS tells me it is called the Hessian. JS starts to ask another question, but it had been half an hour and MC suggests we move on to complex analysis, or another topic. They ask what topic I want. I said that we were already going out of order so let's just do complex analysis. I then realize what JS meant several questions earlier and say "Oh! You meant Fréchet [pronouncing it the French way] derivative." [I had heard the term before, at least, even if I didn't know what it was.] JS apologizes for the confusion. COMPLEX ANALYSIS I studied mostly from Papa Rudin because JS said he likes Rudin's books. I think I like Stein--Shakarchi better, which is what we used in undergrad. JS: Prove that holomorphic functions are harmonic. I write down the Cauchy--Riemann equations using d_(z-bar) and write that f is holomorphic iff it satisfies the C-R equations. JS: That is not an iff statement. Wait, really? Well maybe you also need some technical condition or something... JS: No! Can you give a function that satisfies C-R but does not correspond to a holomorphic function? I get extremely confused about this. [Justifiably; satisfying C-R and being holomorphic *are* equivalent up to some technical conditions, just like I said...] JS: Okay, what does it *mean* for a function to be holomorphic? I write down the definition and emphasize that the z in the denominator is *not* |z|, unlike the total derivative. JS: Right, so it needs to be approximated by a *complex* linear function. Okay, why is |z|^2 not holomorphic? I say that if you approach from the imaginary direction and the real direction you get different results. JS: Well, sure, but I want you to use C-R. (What?) Compute the Jacobian of this function. I struggle to remember what the Jacobian is. I know it has something to do with derivatives so I take the partial derivatives with respect to x and y. I then remember and assemble the Jacobian. JS: Now write down the C-R equations. [I understood he meant "in terms of x and y, not z and z-bar".] (I do this.) Now what does the Jacobian look like for a function that satisfies C-R? I write c -s s c JS: Yes! So |z|^2 is not holomorphic because its Jacobian is not of that form. [Okay... but what does this have to do with the failure of the *converse* direction of holomorphic <=> C-R? This function is neither holomorphic nor satisfies C-R!] Now return to the question about harmonic functions. I write down that the Laplacian is equal to d_z d_(z-bar). For holomorphic functions, the latter is zero, so the Laplacian is also zero, so the function is harmonic. JS: Okay, sure... [Maybe this is not the argument he wanted to hear; I'm not sure.] Suppose I give you a real-valued harmonic function u on the complex plane. Is there another harmonic function v such that u + i*v is holomorphic? Yes, I think so. Let me do it on the disk, which is what I know. Take u restricted to the boundary of the disk and apply the Poisson kernel. I start writing down what this is but he cuts me off. JS: This is not what I am looking for. What is the "hammer" from real analysis that solves this problem? (What?) You can simply solve C-R, which is a PDE! Okay, sure... I have only ever seen the Poisson kernel method for doing this. JS: What conditions on the domain are needed for this to be possible? I think for a bit and guess that it has to be simply connected [since for simply connected regions you can conformally map to the disk and then use the Poisson kernel thing]. JS: That's correct. What is the definition of a simply connected region? I say that it is a region that can be contracted to a point. [This is equivalent for open sets in the plane, I think, but it definitely isn't what simply connected means in general.] JS: Uh... maybe. I was more thinking that it is a region without holes. Why do holes cause a problem? (I don't know...) Let's talk about the logarithm. What is the issue that arises when defining the logarithm over complex numbers? I say that you have to introduce a branch cut. (JS: Or you need to have a jump discontinuity.) I say you need to do this because e^(2 pi i) = 1 = e^0. I say the usual choice is to put the branch cut on the negative real line. JS: Yes, this is called the principal part. How do you compute the logarithm of a complex number? I write log |z| + i arg(z). [Thankfully I remembered the formula.] JS: Yes. He then asks something that I interpreted as "show that log isn't harmonic", but I don't remember exactly what he asked. [I guess he was trying to get me to show that log |z| has no harmonic conjugate, which I did not know.] Umm... like do you just want me to compute the Laplacian or something? JS: Nevermind, let's move on to something else. Suppose now that I have an L^1 function on the real line that analytically extends to a strip. What can I say about its Fourier transform? Well, it's L^1, so its Fourier transform vanishes at infinity... JS: The point is that we want to use regularity to imply faster decay. I say that the Fourier transform has to decay exponentially. (JS: Prove it.) Okay, well the Fourier transform of the derivative is (i x) times the Fourier transform... [I remember using this fact to derive the *converse* of the analytic <=> exponential decay thing, so I thought maybe you could go the other way around as well.] I stumble around a bit before JS interrupts me. JS: This is not the way to do it. Actually, first define the Fourier transform. I do this. I accidentally put (2 pi i) in the constant instead of (2 pi), getting it mixed up with the Cauchy integral formula. JS corrects this. I say I like the normalization with 1/(2 pi)^(1/2) because then the inverse transform has the same constant. JS says he has no preference so we can use your definition. JS: Let's say you want to compute the integral on the line shifted a little bit up or down. How would you do this? I draw a rectangle contour and say to use Cauchy's theorem. (JS: A small rectangle?) I say "and take the sides of the rectangle to infinity". JS: Right, so now should I shift the line up slightly or down slightly? (What?) Like, I want to prove exponential decay. Which direction should I shift the line? (What?) Okay, you need to shift the line according to the sign of xi. Oh! Yes of course; otherwise you get exponential *growth* instead of decay. JS: Right. What is this called? (What?) It's Riemann--Lebesgue. (Uh... okay.) Moving on, what did Goursat prove that Cauchy didn't? What? Goursat is weaker than Cauchy. It is just Cauchy's theorem but limited to triangles. JS: No. The significance of Goursat is that you don't need the derivative to be continuous. [I did not know this. My answer above is completely justified, however: in Stein--Shakarchi "Goursat's theorem" is literally just Cauchy's theorem limited to triangles.] What is the really nice formula that we use to calculate things about holomorphic functions? Cauchy's formula? I write it down. JS: How do you prove that a holomorphic function is smooth? I say something about defining an antiderivative. [I got this confused with how you prove Cauchy from triangle "Goursat".] JS: No, you just prove it using Cauchy's formula. What is the more general Cauchy formula? I modify the Cauchy formula written on the board to the version for derivatives. JS starts to ask another question but again MC interrupts and says we should move on to another subject. ALGEBRA None of the committee members mentioned anything about algebra when I met with them beforehand, so I didn't know who was asking algebra questions or what to prepare. I guessed (correctly) it would be ZD, so I studied a little bit about finite fields. I also studied a chunk of Artin (mostly group theory), but not very intensely. They ask if I want some water first and I say I'm fine. ZD: Can you name a finite field with an element of order 9? I get confused because 9 + 1 is not a prime power, so I say no. ZD says he is just asking for a single element of order 9, and I realize that p = 9n + 1 works. I say that the multiplicative group of a finite field is cyclic, so take a^n where a is the generator. ZD: Okay, what about a specific p that works? It took me about 10 seconds to compute 2*9 + 1 = 19... ZD asks if this works in general and I say yes because of Dirichlet. ZD: How do you construct the finite field F_(p^n)? Take an irreducible degree n polynomial p over F_p and do F_p[x]/p. I then realize that p means two different things there and replace the polynomials by f instead. ZD: How do you find such a polynomial? I claim that x^n + c works for some c unless p = 2. [In fact you need x^n + ax + b for some a, b; I misremembered.] ZD is skeptical but says it's not that important. ZD: What is Cauchy's theorem? I state and prove Cauchy's theorem. ZD: What is the trace of an element in a finite field? I vaguely remember what the trace is from algebraic number theory, so I guess it is going to be similar. [This is completely wrong; ZD was talking about something else.] I say something about viewing the elements of F_(p^n) as vectors and then the trace has something to do with viewing multiplication as a linear map in this vector space. ZD: Uh, not really. That sounds like something about Galois extensions. How much Galois theory do you know? (Not much.) Okay, do you know any representation theory? I said I know some facts about the character table but not how to prove them. ZD: Nevermind then. Let's do linear algebra. Suppose M and N have rank n - 1. What is the smallest possible rank of MN? I fumble around a bit before figuring out that this has rank at least n - 2. I say an argument involving nullspaces. (ZD: And in general?) I say that the corank of MN is going to be at most the sum of the coranks of M and N. ZD: What about the rank of a sum of two matrices, say with full rank and rank 1? After thinking for a bit I realize that this has rank at least n - 1 but struggle to explain why this is. I try to formulate it in terms of finding linearly dependent rows. ZD: A better way to do this is to know that the rank of a matrix is equal to the smallest number of rank 1 matrices that sum to the matrix. Oh, so then at most rank(N) of these summands are going to cancel... ZD: Yeah, something like that. Do you know about the tensor power of a matrix, or Kronecker power? I write down what the Kronecker product is. ZD: What is the rank of the kth tensor power of M? I say that rank is multiplicative under Kronecker product, and he is satisfied with that. ZD: Suppose I have a matrix over F_p with zeros on the diagonal and nonzeros everywhere else. What can you say about its rank? I don't know anything about this question, so I fumble around going back and forth between thinking it is low rank and full rank. ZD: How about just F_2 for now? I think it is full rank and give a really janky argument for this. In fact it is rank n - 1 and ZD corrects me. ZD: Okay, now F_3. (I don't get anywhere.) Think about the Kronecker product. What if you squared all the entries of the matrix? Then it is zero on the diagonal and one everywhere else, and that's similar to the F_2 case... So the answer is going to be like sqrt(n) roughly? ZD: Er... What is the relation between the matrix with squared entries and the Kronecker power? (Uh...) The former is a submatrix of the latter. Let's move on. What is a prime ideal? I say I should probably know what this is. [I didn't review anything about ring theory.] ZD is extremely disappointed. ZD: Do you know Hilbert's basis theorem? (No.) What about Hilbert's Nullstellensatz? I say I might remember the statement, but not the proof. I struggle for a while to formulate it. I say it is something to do with wanting f^n to be in an ideal, but I can't remember the hypothesis. ZD eventually gives up and tells me the statement. ZD: What is a simple group? I define something. Wait, that's the definition of a *solvable* group, not simple! Uh... ZD: Simple group has no nontrivial normal subgroup. What are some examples of simple groups? (C_p.) What about a nonabelian example? (A_n with n >= 5.) He ponders for a second if he wants to ask anything else. ZD: Alright, that's enough algebra. COMPUTATIONAL COMPLEXITY We agreed to talk about Arora--Barak chapters 1-8 and 11, i.e. standard topics plus PCP theorem. ZD: Define NP. I say the certificate definition but I am somewhat vague about the details. ZD: No, be more precise. I want to know the order of the quantifiers. Actually, define P first. (I do this.) Now NP. I modify the definition of P to now include the certificate, being very careful this time to get all the quantifiers right. ZD: Just making sure you know the fundamentals. What is a problem that is likely in NP but not P? I define SAT (very precisely). ZD: Why is this probably not in P? It is NP-complete, and we expect P is not NP. He didn't ask about how to prove NP-completeness. ZD: What if you modified it so that you add an extra "for all" after "exists" but before the boolean formula? Then it is called Sigma_2 SAT. ZD: Is this NP? Probably not, since it is Sigma_2^P-complete and the polynomial hierarchy is expected not to collapse. ZD: Is it NP if P = NP? Yes, because then the polynomial hierarchy collapses. ZD: Does that still happen if NP = \Sigma_2^P? Yes. Maybe this also implies P = NP? I'm not sure. [I was misremembering Karp--Lipton, which is completely different.] ZD: No, I don't think it implies P = NP. Can you give a PSPACE-complete problem? (I define TQBF.) What about a problem that is not in P, not depending on P vs. NP? I say such a problem exists by time hierarchy theorem. I state the time hierarchy theorem and use it to show P is not EXP. ZD: Okay, but what about a specific problem that is not in P that you can write on the board? I guess he is asking for a non-diagonalization problem, since you prove time hierarchy theorem by diagonalization. I can't think of any so I write down "the set of machines that halt." ZD: Well, okay, sure, but how about a computable example? I say I can only think of diagonalization constructions. ZD: Those work, as long as you can write one on the board. I write "the set of machines that halt in time 2^n" but think there might be a problem with that. [Indeed there is; I needed to include n in the input, not just the machine. ZD either doesn't catch this or doesn't care about such tiny details.] ZD: That works. What else did we say we were going to cover? (PCP theorem.) Okay, state the PCP theorem. I do. I then define PCP carefully. ZD: What is the significance of this theorem? It implies certain functions are hard to approximate. For example it implies 3SAT can't be (7/8 + epsilon)-approximated in polynomial time unless P = NP. ZD: What does "approximate" mean here? (I define this precisely.) Does this version of the theorem imply that? No, you need a stronger version. This one just proves (1 - epsilon) is hard. ZD: How do you show that? I give the argument that it implies constraint satisfaction problems are hard to (1/2)-approximate, then you can convert to 3SAT. But this conversion is going to lose some constant factor, so the "1/2" becomes "1 - epsilon". ZD: Out of curiosity, do you know how to prove PCP? I say that's not in chapter 11 of Arora--Barak so I didn't study it. I say, "It's pretty complicated. I know it has something to do with expander graphs." ZD was happy I knew anything at all about the proof. ZD: It's a cool proof. Okay, that's good for computational complexity. GRAPH THEORY I took three graph theory courses with MC when I was an undergrad. She gave me a subset of topics I should prepare from those classes, and I studied off of my old class notes. MC: What does it mean for a class to be chi-bounded? (I give the definition.) Is the class of all graphs chi-bounded? No, there are triangle-free graphs with arbitrarily large chromatic number. I describe the Mycielskian. MC: Prove that P_t-free graphs are chi-bounded. I write the bound (t-1)^omega. I set up the induction proof but can't figure out how to finish the inductive step. MC says we can move on, since this was a problem meant for me to gain confidence but it is clearly not doing that. MC: What is the Erdős--Hajnal conjecture? (I state it.) Pick a graph and prove Erdős--Hajnal for it. Well, it's awfully trivial if H = K_1... (MC laughs and asks for something less trivial.) I prove it for P_4 using the fact that P_4-free graphs are perfect. MC: What is a perfect graph? (I give the definition.) State the weak and strong perfect graph theorems. (I do this.) I think it is possible to prove P_4 has Erdős--Hajnal property without using perfect graphs. What else do you know about P_4-free graphs that might help? I say they are either disconnected, or disconnected in the complement, or a single vertex. I start trying to prove E-H using this fact, but MC and I stare at the board for 30 seconds before giving up on this endeavor. [I had actually tried briefly to prove this without perfect graphs while preparing for the generals but didn't manage to. My class notes have only the proof using perfect graphs.] MC: What is a star-cutset? (I define it.) Prove that minimal imperfect graphs do not have a star-cutset. (I do this.) MC: Let's switch gears. What is a tree decomposition? (I define it.) What about a path decomposition? (Replace the word "tree" with "path" in the definition.) Are there graphs with large pathwidth but small treewidth? Yes. I prove that binary trees have logarithmic pathwidth. MC: Prove that graphs have chromatic number at most treewidth + 1. I argue that you can greedily color the graph according to the tree decomposition. [I mistakenly say that you should do this bottom-up instead of top-down, but neither of us catch the mistake.] MC: You know, I had another general exam this morning and asked the same question and he gave the same proof, which is not the proof I had in mind, so I am going to challenge you. Prove that graphs are treewidth-degenerate. I say to choose a vertex that is in a leaf bag and nowhere else. This exists because otherwise you can remove the leaf bag entirely and improve the tree decomposition. MC: What are the minor-obstructions to small treewidth? (Grid graphs.) Actually, what is a minor? I give the definition using vertex/edge operations. MC: What is a model of a minor? (I give the definition.) What can you say about complete graph minors if you have lots of edges? I know there is a theorem involving "2^p". MC: Oh, okay, good, that's what I was going to ask about. State it and prove it. I state that graphs with (2^p)n edges have a K_p minor but warn that I might be off by a constant. I prove this. That was the end of the exam. It lasted about 2 hours: roughly 30 minutes each for real and complex analysis and 20 minutes each for the other three topics. I stepped out for a few minutes and then they came out to the hallway and congratulated me. JS left immediately. ZD said "You should really know what a prime ideal is" before leaving. Overall, I think analysis went better than I expected and algebra went much worse, though looking back I think this was completely predictable given how much I studied each subject (below). I prepared a ton of things that they didn't ask about, especially the special topics. I guess MC knows me very well by now and didn't feel the need to test me that hard. I studied mainly in two phases: 1. During first part of the spring semester, I reread all of my relevant class notes, most of the relevant books, and past general exams. 2. In the two weeks leading up to the exam, I compiled a gigantic document of theorem statements and proof sketches, first writing from memory and then from the notes/books to fill in gaps; this contained: - 65 theorems in graph theory (class notes), - 51 theorems in computational complexity (Arora--Barak), - 49 theorems in real analysis (including Fourier and functional analysis) (Papa and Grandpa Rudin and Stein--Shakarchi I), - 31 theorems in complex analysis (Papa Rudin and Stein--Shakarchi II), - 20 theorems in algebra (Artin). In hindsight I obviously should have studied more algebra.