2,620 reputation
21638
bio website cims.nyu.edu/~hbennett
location New York, NY, USA
age
visits member for 4 years, 6 months
seen 1 hour ago

I am a graduate student at NYU.


12h
reviewed Approve Are there sparsifiers that approximate vertices rather than edges?
Mar
25
revised Fun with inverse Ackermann
Fixed minor latex typo.
Mar
17
comment VC-dimension of triangles in 2D space
@Daniel: Shattering means that you have to be able to separate all +/- labellings of the same set of points, I think.
Mar
12
reviewed Approve Deciding whether a context-free language is regular
Mar
11
comment Why study type theory?
What is "type theory per se"?
Mar
11
revised Is the Cheeger constant $\mathsf{NP}$-hard?
edited tags
Mar
9
comment Deterministic Randomness Extractors
My comment was based on the previous edit. I thought you were trying to emphasize that the min-entropy is very close to $n$ (off by an additive constant), which is stronger than just saying it's $\Omega(n)$ (although the latter is true and still certainly makes your point).
Mar
9
comment Deterministic Randomness Extractors
I think you mean "will have min-entropy $\geq n - 1$".
Mar
3
reviewed Approve What is the difference between propositions and judgments?
Mar
2
comment Spectral Gap in Expander Graphs
The whole purpose of the spectral gap is as a measure of how connected the graph is, so it's weird to think that removing edges wouldn't affect it. Imagine starting with the complete graph (which has spectral gap 1), and deleting edges until you have another connected, regular graph (which must have spectral gap <1).
Mar
2
comment Spectral Gap in Expander Graphs
No? What makes you think this might be true?
Feb
23
revised How exactly does lambda calculus capture the intuitive notion of computability?
edited body
Feb
22
comment Algorithm to determine if given algorithm runs in polynomial time
@SashoNikolov: Good point! Thank you!
Feb
22
comment Algorithm to determine if given algorithm runs in polynomial time
@SashoNikolov: I think Rice's theorem does apply. The formal statement of Rice's theorem says that it's undecidable to determine whether the language a TM computes is in C for any non-trivial complexity class C. Here non-trivial means that there exists a TM deciding a language in C, and a TM deciding a language not in C. Clearly this holds when C = P.
Feb
19
reviewed Reject Gröbner bases in TCS?
Feb
13
comment Probabilistic and quantum analog of $FP$ and $FNP$?
Well, usually decision problems are simpler and capture the complexity properties that we want to study. Also, your question has an easy answer for decision problems: BPP and MA are the probabilistic analogs of P and NP respectively, while BQP and QMA are the quantum analogs of P and NP respectively. I don't see why you care about sticking an "F" in front of any of these classes.
Feb
13
comment Probabilistic and quantum analog of $FP$ and $FNP$?
What's the motivation for considering the functional variants of these classes?
Feb
4
reviewed Reject Major unsolved problems in theoretical computer science?
Jan
29
reviewed Approve What is the Algorithm to find all the possible chordal graphs which can be formed by a given 'n' number of vertices
Jan
22
comment Real representation versus communication complexity
Yes, I agree. I thought it was worth noting that we can say something in the $\mathbb{F}_2$ case even though it doesn't answer your question.