963 reputation
614
bio website robinkothari.com
location Cambridge, MA
age
visits member for 4 years, 4 months
seen Nov 8 at 17:38

I am a postdoc at MIT. My research interests include quantum algorithms and complexity theory.


Sep
24
awarded  Autobiographer
Jul
31
awarded  Yearling
Nov
1
comment How much does a quantum oracle to find a needle in a haystack really cost?
@skeptic: I don't understand. By assumption (this is part of the question), $f$ is a map that accepts database entries (binary strings) as input and outputs 0 or 1. $f(x)$ is 1 if and only if $x = w$, where $w$ is the string we are looking for.
Sep
19
awarded  Nice Answer
Jul
31
awarded  Yearling
Jun
25
awarded  Suffrage
Oct
27
accepted Can you maximize the spectral norm of a matrix in a semidefinite program?
Oct
27
comment Can you maximize the spectral norm of a matrix in a semidefinite program?
Right, that makes sense. Thanks.
Oct
24
comment Can you maximize the spectral norm of a matrix in a semidefinite program?
Thanks. But does that rule out the possibility that introducing new variables and changing variables will make it an SDP? For example, geometric programming (en.wikipedia.org/wiki/Geometric_programming) is in general non-convex, but a change of variables makes it convex.
Oct
24
asked Can you maximize the spectral norm of a matrix in a semidefinite program?
Aug
9
answered How can I get all the good items using quantum search algorithm?
Aug
9
answered How much does a quantum oracle to find a needle in a haystack really cost?
Jul
31
awarded  Yearling
Aug
1
awarded  Yearling
May
29
comment Can i achieve something better with the probabilistic turing machine in matter of space?
Are you asking if a non-deterministic machine with space f(n) can solve the same problems as a one-sided error randomized machine with space f(n)?
Dec
2
comment Is P=NP relevant to finding proofs of everyday mathematical propositions?
A very interesting observation: "people might like my proof better than the lexicographically first one"
Oct
31
answered Most memorable titles
Oct
6
answered Amplitude amplification as a quantum walk algorithm
Sep
28
answered What are some good examples of non-monotone graph properties?
Sep
28
comment What are some good examples of non-monotone graph properties?
Hamiltonicity is so very monotone.