2,619 reputation
21638
bio website cims.nyu.edu/~hbennett
location New York, NY, USA
age
visits member for 4 years, 3 months
seen yesterday

I am a graduate student at NYU.


Dec
15
reviewed Approve Algorithm for Max Network Flow with lower bounds and its complexity
Dec
12
comment Known algorithms for Graph isomorphism
I think the question is fine, and would be very interested to see a survey answer along the lines of this one: cstheory.stackexchange.com/questions/9241/… McKay's survey seems more focused on implementation issues, and less on algorithms per say.
Dec
10
revised Examples of uncommon problems with different asymptotic costs?
Fixed typo
Dec
9
reviewed Approve Heaps, Heap sort, and size of subtrees
Dec
6
revised How difficult is it to work on mathematics problems as a computer science graduate student?
Fixed typo
Nov
25
reviewed Approve Is the problem NP-C or polynomially solvable?
Nov
22
comment Can real-time deterministic multicounter automata recognize the marked palindrome language?
Would it be possible to link to something about multi-counter and real-time automata?
Nov
12
revised Complexity of intersection of regular languages as context-free grammars
Improved tags
Nov
10
comment $NP$-complete problem with quasi-polynomial bound on the number of solutions
Unless I've misunderstood what you've written, you're confusing the number of strings in a language of a given length with the number of witnesses showing that a string is in the language in both parts of your answer.
Nov
9
comment Conversion between k-SAT and XOR-SAT
In particular $x \lor y$ has no equivalent XOR-SAT formula.
Oct
22
comment Most memorable CS paper titles
Pretty much any title by Philip Wadler is memorable. My favorites are his thesis, "Listlessness is Better than Laziness," and a POPL paper with Jeremy Siek, "Threesomes, With and Without Blame."
Oct
21
reviewed Approve What's the correlation between treewidth and instance hardness for random 3-SAT?
Sep
28
revised The Stalin compiler brutally optimizes, but how?
Fixed grammar
Sep
28
reviewed Approve The Stalin compiler brutally optimizes, but how?
Sep
21
revised Is P equal to the intersection of all superpolynomial time classes?
Fixed spelling typo.
Sep
14
comment $NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$
@usul: complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npc2
Sep
10
reviewed Approve Questions on unification theory (and its application to DAG isomorphism )
Sep
8
awarded  Yearling
Sep
6
comment Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?
I think Scott's answer to your last question (particularly the middle paragraph) is great intuition for why that is. I was actually Googling for it as a reference for this question when I realized he had posted it as an answer to your previous question.
Sep
5
comment Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?
Why do you think NPI and NPC should be "symmetric"? Isn't this like your previous question here: cstheory.stackexchange.com/questions/20930/… ?