Colin Sandon January 24, 2014 2:00-3:00 Special Topics: Computational Complexity, Riemann Surfaces Committee: Robert Gunning, Zeev Dvir, Janos Kollar COMPUTATIONAL COMPLEXITY: Dvir: What are P and NP? (answers) Give an example of a problem in each. me: The problem of whether a given boolean expression is satisfied by a given assignment of variables, and the question of whether a given boolean expression can be satisfied by any assignment of variables. Dvir: What does it mean for a problem to be NP-complete? (answers) How would you prove that a problem is NP-complete? me: Originally, I would have to prove that all problems in NP can be reduced to a problem, such as 3SAT. Once I have that, I can just prove that 3SAT reduces to a problem to show that it is NP-complete. Dvir: Assume that you do not already have a known NP-complete problem to build from. me: Outlines how I would represent an arbitrary Turing machine's operation on a certificate as a circuit and convert the existence of a certificate that it would accept to the satisfiability of a boolean formula, but gets stuck trying to figure out how to convert an arbitrary boolean formula to a formula in 3CNF form. Dvir: Never mind; it's a minor detail. What is the PCP theorem? me: For every problem in NP and epsilon greater than zero, there is a polynomial time randomized algorithm that uses a polynomial-length certificate and queries a constant number of bits of the certificate, chosen nonadaptively, such that for every string in the language there is a certificate that it accepts with probability one, and for every string not in the language it rejects all certificates with probability at least 1/2. Dvir: What are the implications of this? me: Well, it means that unless P=NP, there is no 7/8+epsilon approximation algorithm for 3SAT, because if there was you could use it on the boolean formula encoding the algorithm's acceptance of the certificate to determine whether or not there is a certificate that it is likely to accept. Dvir: What is the 7/8 approximation algorithm for 3SAT? (answers) Do you know what it is called? me: no. Dvir: What other approximation algorithms do you know? me: Well, there is the 2-approximation algorithm for the problem of finding the minimum number of vertices on a graph that cover all edges that consists of repeatedly picking an edge that is not incident to any vertex that has already been chosen and adding both of its vertices to the set until there are no uncovered edges left. Dvir: How about the polynomial hierarchy? What is Sigma 2? me: The collection of languages that can be expressed as the set of strings S such that there exists a string X such that for all Strings Y T(S,X,Y) for some function T in P, or maybe the other way around; I am not sure. Dvir: What is a problem in Sigma 2? me: Gives Sigma-2 version of SAT. Dvir: What is PSPACE? (answers) Give an example of a problem in it. me: describes TQBF Dvir: Do you know what that is called? me: no. Dvir: What is the connection between the polynomial Hierarchy and PSPACE? me: The polynomial Hierarchy is contained in PSPACE. Dvir: What is a problem that is not in P? me: That is tricky. Well, EXP is not in P, so (gives EXP-complete version of Circuit-SAT). Dvir: How do you know that EXP is not in P? me: Outlines proof of the time hierarchy theorem, but gets stuck on the details of the diagonalization. Dvir: Good enough. What is AC0 (answers). Give a problem that is not in AC0. me: Computing the parity of the input. Any circuit in AC0 will become constant if enough of the input is fixed, since fixing enough of the inputs will alow one to reexpress each and of ors as an or of ands, which reduces the depth of the circuit by one. A circuit computing parity remains non constant as long as a single bit of input is still allowed to vary. Dvir: How do you fix the inputs? me: I do not know exactly. Dvir: Will fixing any sufficiently large portion of the inputs of an AC0 circuit render it constant. me: No, you could have an AC0 circuit that outputs one of its inputs and ignores the rest, in which case fixing all of the other inputs leaves it non constant. If you fix a large enough number of randomly selected input bits, it will become constant with high probability. Dvir: Right; that is the probabilistic method. What else did you study? me: Randomized algorithms, derandomization... Dvir: Okay, how does that work? me: Sketches out how one uses a worst-case hard function to construct a pseudorandom generator. RIEMANN SURFACES: Gunning: What is the dimensionality of the space of abelian differentials. me: 2g? Gunning: What? me: 2g? Gunning: It has g dimensions. How do you show that it has g dimensions. me: proves that H1 has 2g dimensions and is the direct sum of the spaces of holomorphic and antiholomorphic one-forms, and that complex conjugation is a bijection between these spaces. Gunning: What is the main theorem? me: for a given two-form p, there exists a function with laplacian p if and only if the integral of p is 0, and in this case all such functions differ by constants. Gunning: How do you know that the integral of d(f dz) is 0? me: It is an exterior derivative and the Riemann surface has no boundary, so it follows by Stokes' Theorem. Gunning: What is the Riemann-Roch theorem? me: Gives a version that assumes all points in the divisor have order one, and then generalizes when asked. Gunning: What is Abel's theorem? me: Gives a version that assumes all points have order plus or minus one, and then generalizes when asked. Gunning: How many holomorphic one forms are there on a Riemann surface of genus 1? me: one(up to multiplication by a constant) Gunning: what can you say about a compact Riemann surface of genus 1? me: Gives an argument for why any such surface must be conformal to the quotient of the complex plane by a lattice. Gunning: What about Riemann surfaces of other genuses? me: Their universal covering surfaces must be conformal to either the Riemann sphere, the complex plane, or the unit disk, so they must be conformal to the quotient of one of the above by some subgroup of its group of automorphisms. Gunning: What can you say about compact Riemann surfaces with a map between them? me: gives Riemann-Hurwitz formula. Gunning: Can there be a holomorphic map from a Riemann surface to a Riemann surface of higher genus? me: Reformats formula. No. Gunning: How about maps between Riemann surfaces of the same genus. me: Either the map is an isomorphism, the surfaces have genus one, or the surfaces have genus zero. Comments: I do not have all of the details of my exam right; for instance I know that I mentioned the traveling salesman decision problem as an example of an NP or NP-complete problem at some point, but do not remember when. I had talked to Gunning enough to know more or less what questions he would ask, which definitely helped. My committee also did not ask about the standard topics, based on Gunning's argument that I already went through them when I took my generals the first time.