# Anirbit

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 hypercubeI 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 hypercubeOkay! 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 problemIs 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 problemIf 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 methodAs 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 hypercubedeleted 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?