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.