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

I am a graduate student at NYU.


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
May
17
answered What is known about this TSP variant?
May
12
comment Milestones in counting complexity
@MarzioDeBiasi: That should be an answer!
May
9
reviewed Approve Are there any topics in theoretical CS that are more about pure math?
May
1
reviewed Reject Is there a generalization of the GO game that is known to be Turing complete?
Apr
29
comment Is there a generalization of the GO game that is known to be Turing complete?
Sorry, I don't understand this at all. What you're describing still has a finite number of states, so it can't be Turing complete. More importantly, what do "divinatory elements" and "religious dimensions" have to do with anything?
Apr
29
comment Is there a generalization of the GO game that is known to be Turing complete?
Your link only shows what look like "trading cards" without any discussion of Go that I can see. I think this is an advertisement for your patent and not an answer to the question.
Apr
28
reviewed Approve List of number theoretic or algebraic problems in various complexity classes
Apr
28
reviewed Approve What would signify hierarchy collapse to first level?
Apr
23
reviewed Reject Implemented code to compute pathwidth (= Node search number, vertex separation number, interval thickness)
Apr
23
revised Complexity for single-linkage clustering with max norm
edited title
Apr
12
revised Applications of TCS to classical mathematics?
added 1 character in body