I am transferring into the "Applied Mathematics and Statistics" PhD. program at the Johns Hopkins university. I started off as a graduate student in physics at UIUC where I worked on these projects, http://arxiv.org/abs/1512.01226, http://arxiv.org/abs/1307.7714

Since summer 2014, I started pursuing complexity theory and I am interested in theory of Ramanujan expanders, spectral graph theory, polytope extension complexity, Lasserre hierarchy and matrix norm sketching. I am particularly interested in questions in complexity theory which have an interface with physics.

Apr
28
awarded Yearling
Apr
28
awarded Yearling
Apr
28
asked The decay rate of the spectrum of the Gaussian kernel on compact manifolds
Apr
28
comment Getting a Hermite polynomial expansion of Gaussian with given variance.
WoW! So not just on compact sets but on the entire plane!?
Apr
28
comment Getting a Hermite polynomial expansion of Gaussian with given variance.
Wow! So this is much stronger than just L^2 convergence!? Its not just that the square of the difference between partial sums of the series and the kernel when integrated over all space tends to 0? Its like "for all" pairs of points this converges uniformly on compact sets?
Apr
28
comment Getting a Hermite polynomial expansion of Gaussian with given variance.
And is this a pointwise convergence (uniform on compact sets?) or is this a convergence in the sense of L^2 norm (which is like a convergence on average) ?
Apr
28
comment Getting a Hermite polynomial expansion of Gaussian with given variance.
Thanks! Let me look up that reference! This is particularly confusing because the upper bound on the Hermite polynomials is exponentially diverging and hence I have no intuition for its convergence!
Apr
26
comment Getting a Hermite polynomial expansion of Gaussian with given variance.
Could you kindly explain how does one prove that the Mehler kernel expansion converges?
Apr
15
comment About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube
I wasn't being conscious of this difference. I would think of $\{-1,1\}^n$ as a hypercube. Why isn't it? Does it make a fundamental different to ask the question on this vs say asking the question on the Boolean hypercube $\{0,1\}^n$?
Apr
14
comment About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube
Okay! Any thoughts about my curiosity as to whether or not every NP-complete question can be written as an unconstrained polynomial optimization over the hypercube?
Apr
13
comment About the interpretation of the SOS hardness results of the planted Max-Clique problem
Is it possible that one can adversarialy choose graphs with cliques of size greater then sqrt{n} to feed to the SOS for planted Max-Clique such that SOS is fooled? (...just because by sampling over G(n,1/2) this sqrt{n} bound is hard to improve doesn't rule out that there is a way to shoot up the bound by some clever adversarial choice which doesn't use randomization..)
Apr
13
comment About the interpretation of the SOS hardness results of the planted Max-Clique problem
If one knows that with high probability (even just non-zero probability) the hard graphs exist then isn't it immediately obvious that one can always pick those hard graphs adversarially to trip SOS? (...ofcourse I guess what is open is to see if the $\sqrt{n}$ can be improved to the UGC bound of Max-Clique for 4 or higher degree SOS..)
Apr
13
comment About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube
@SashoNikolov Thanks for the reference! So you mean to say that if a decision question has this Max-CUT like form as that of an unconstrained optimization of a polynomial over the hypercube then this will be preserved under L-reductions? Is that the point?
Apr
12
comment Positivstellensatz and sum of squares method
As in I haven't seen any recent course lecture notes or reviews which discuss this proof. No SOS hardness paper I have seen ever reviews this proof.
Apr
12
comment About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube
@Boson Thanks for the reference! Let me have a look!
Apr
12
comment About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube
@RickyDemer Could you please expand on your comment? Are you saying that being expressible in unary is iff with being writable as optimization of a polynomial over the hypercube? (And you are saying that this $FP^{\vert \vert FNP }$ is a class of such questions?)
Apr
12
comment Positivstellensatz and sum of squares method
@EmilJeĊ™ábek Do you know of a reference for the proof of this real Nullstellensatz? I haven't been able to locate any modern presentation of it except for the 1964 and 1974 papers referenced in the notes linked above!
Apr
11
revised About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube
deleted 24 characters in body
Apr
11
asked About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube
Apr
9
comment About complexity of recovering or learning Bayesian networks
@Kaveh Just wondering, aren't you referring to the NP-hardness of "inference" that is the question of finding the marginal of some vertex given the joint distribution? (like say what is discussed here, arxiv.org/ftp/arxiv/papers/1206/1206.3240.pdf ?) But isn't this question wholly different from what I am asking?
1 2 3 4 5