2,859 reputation
21739
bio website cims.nyu.edu/~hbennett
location New York, NY, USA
age
visits member for 4 years, 11 months
seen 4 hours ago

I am a graduate student at NYU.


Aug
11
comment What is the simplest known solver for a np-complete problem?
1. It depends on how you encode the problem. 2. This looks more like SAT solver code golf.
Aug
5
reviewed Approve Is this covering problem NP-hard?
Aug
1
reviewed Reject Approximate matching in table of integer vectors
Aug
1
reviewed Reject What greedy algorithm satisfies greedy choice property but does not have optimal substructure?
Jul
31
reviewed Approve Problems in BQP but conjectured to be outside P
Jul
29
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?