2,387 reputation
21536
bio website cims.nyu.edu/~hbennett
location New York, NY, USA
age
visits member for 3 years, 7 months
seen 4 hours ago

I am a graduate student at NYU.


1d
reviewed Approve suggested edit on Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$
Apr
12
reviewed Approve suggested edit on Convolution products in partial semigroups
Apr
11
reviewed Approve suggested edit on Paper about the upper bound of the number of inequalities to describe the Integer hull of a polyhedron
Apr
9
comment Has there been any research on $k$-SAT above the satisfiability threshold?
It's worth noting that $\alpha$ is a function of $k$.
Apr
6
comment graph isomorphism given a partial isomorphism
@JoshuaGrochow: Thanks, I didn't realize that both the name and abbreviation had changed over time.
Apr
5
comment graph isomorphism given a partial isomorphism
Yes, I was asking why it was abbreviated that way on the ACM page.
Apr
5
comment graph isomorphism given a partial isomorphism
Nice reference. Why is "Conference on Computational Complexity" abbreviated as COCO instead of CCC?
Apr
1
reviewed Approve suggested edit on How can I construct sorting network for $k$ numbers
Mar
29
reviewed Approve suggested edit on Convergence of iterated stochastic matrices
Mar
29
reviewed Approve suggested edit on What do you do when you cannot make progress on the problem you have been working on?
Mar
28
comment Computational complexity of pi
Is the question for algebraic numbers (e.g. $\sqrt{2}$) really analogous? We can compute the $n$th bit ($n$ given in binary) of an algebraic number via Newton's method in $O(n)$ iterations. On the other hand, I guess a single iteration may take $O(2^n)$ time just to write the output bits.
Mar
27
reviewed Approve suggested edit on Is there a non Turing-complete model of computation whose halting problem is undecidable?
Mar
12
awarded  Excavator
Mar
12
revised more on PH in PP?
Fixed spelling.
Mar
7
comment List of theorems stating that P does not equal NP if and only if
Are you sure? I hadn't heard of worst-case OWFs before, but from the notes here it looks like their existence is equivalent to $BPP \neq NP$.
Feb
28
reviewed Approve suggested edit on Complexity class separations without hierarchy theorems
Feb
23
reviewed Approve suggested edit on Algorithm to Bulk Delete nodes from a Treap
Feb
19
comment Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs
st-connectivity is an interesting example for analogous lower-level classes - L for the undirected case versus NL-complete for the directed case.
Feb
6
awarded  Nice Question
Jan
29
comment Justifying asymptotic worst-case analysis to scientists
They seem to define asymptotic and worst case analysis rather than focusing on justifying it, but maybe I missed something?