2,858 reputation
21739
bio website cims.nyu.edu/~hbennett
location New York, NY, USA
age
visits member for 4 years, 10 months
seen 45 mins ago

I am a graduate student at NYU.


4h
reviewed Approve Problems in BQP but conjectured to be outside P
2d
comment If BQP contains NP, does this mean that P=NP?
@AhmedYounes: The second sentence of the abstract of the paper I linked to says "The paper shows that BQP contains NP." Are you saying that that's not correct?
Jul
24
reviewed Approve Was the reduction in Shor's algorithm originally discovered by Shor?
Jul
20
comment If BQP contains NP, does this mean that P=NP?
This question is a bit worrying given the sequence of recent Younes "NP in BQP" preprints: arxiv.org/abs/1507.05061.
Jul
16
comment Is the finite inverse semigroup isomorphism problem GI-complete?
"Are you really confused, or would you just like to hear my opinion on lattice theory?" Neither, actually. I thought someone in addition to me may have been familiar with that definition of lattice isomorphism and not this one, and that the link might help.
Jul
16
comment Is the finite inverse semigroup isomorphism problem GI-complete?
Somewhat confusingly, there's also this lattice isomorphism problem which is GI-hard but not known to be GI-complete: www2.mta.ac.il/~ishayhav/papers/latticeiso.pdf
Jul
10
reviewed Approve Select in union of sorted arrays: Already known?
Jul
10
reviewed Approve Exact formula for the number of spanning trees of a rectangle
Jul
8
comment “Any” Subset Sum. Is it hard?
@Peter, Radu: You're right. Unfortunately I read both the OP's post and the abstract carelessly.
Jul
8
comment “Any” Subset Sum. Is it hard?
I think that paper proves that PARTITION is NP-complete. There's a straightforward reduction to the OP's problem, but it's not the same because of the three sets and non-emptiness constraints.
Jul
8
reviewed Reviewed Is there a non Turing-complete model of computation whose halting problem is undecidable?
Jun
28
comment Does this problem related to subset sum have a name?
Yes, as Austin points out it's not even a decision problem. It could take exponential time just to enumerate all such subsets (for example, if $S_1 = S_2 = \{1, \ldots, n\}$).
Jun
24
comment the confusion about 'with high probability (w.h.p.)'
The Wikipedia definition you give, "with high probability" defined as $1 - o(1)$, probability that goes to 1 as n goes to infinity, is precise. The examples you give all meet this definition, but are more specific.
Jun
16
comment Why is CNF used for SAT and not DNF?
There are a few issues here. (1) I think by "unfalsifiability" you mean "tautology". (2) KNF should be CNF.
Jun
3
comment Is there algorithmic mathematical analysis?
As another resource, see Yap's paper "Theory of Real Computation according to EGC": cs.nyu.edu/exact/doc/realtheory.pdf
Jun
2
reviewed Approve Is there a pair of different lambda terms in the normal form that behave identically when applied to any input?
May
26
comment Counterintuitive results for undergraduates
The second of Sasho's links is a duplicate, no?
May
19
reviewed Approve Enumerating set combinations in an order that maximises the number of previously unseen subsets
May
19
awarded  Good Question
May
17
awarded  Nice Answer