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

I am a graduate student at NYU.


1d
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
19
comment DESIGN A FUNCTION OF THE H FAMILY THAT SOLVES THE NP-COMPLETE SUM SUBSET PROBLEM IN O(n)
My mistake. Sometimes I try to comment with something useful even if the question has problems.
Nov
17
comment Are all cryptography problems reducible to factoring?
en.wikipedia.org/wiki/Post-quantum_cryptography
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.
Nov
7
comment A truly random secret-Santa generator
See here: cstheory.stackexchange.com/questions/14682/…
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 suggested edit on 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 suggested edit on 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 suggested edit on 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/… ?
Aug
21
comment What are some good introductory books on type theory?
Yes, TAPL is the book. There's also Pierce's "Advanced Topics in Types and Programming Languages" as a follow-up.
Aug
19
comment What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?
Isn't this covered by Tsuyoshi and Noam's comments above?
Aug
6
comment Another algorithm for stable matching?
This seems a little vague without specifying what properties you would hope an additional algorithm to have.