Reputation
19,958
Next privilege 20,000 Rep.
Access 'trusted user' tools
Badges
5 79 143
Newest
 Enlightened
Impact
~252k people reached

May
11
comment Big gaps between RAM and Turing machine complexity
Shaull's comment is only true for nondeterministic machines and in the two-tape TM setting, as far as I know. Citation, Shaull?
Apr
21
awarded  Guru
Apr
18
comment Alternative proofs of Schwartz–Zippel lemma
Another version of this observation with fewer assumptions and a weaker error bound appears and is applied in a restricted form (just stated for $Z_m$) in a paper with Virginia, Josh Wang, and Huacheng Yu in SODA'15: "Finding four node subgraphs in triangle time"...
Apr
5
comment Complexity of the search version of 2-SAT assuming $\mathsf{L = NL}$
This is nice! Is there a reference?
Mar
26
reviewed Close Resources for Church's paper “An Unsolvable Problem of Elementary Number Theory”?
Mar
26
reviewed Leave Open Efficient generation of Tournament Graphs
Mar
26
reviewed Close Deciding satisfiability and non-validity
Mar
26
reviewed Close Results about computability power or limitations of shared read/write registers
Mar
26
reviewed Close Deciding whether a context-free language is regular
Mar
26
reviewed Close How can I prove that Hamming distance is upper bound for Levenshtein distance?
Mar
26
reviewed Leave Open Establishing causality under conditions of certainty
Mar
26
reviewed Close Definition of convex optimization problem by Stephen Boyd and Lieven Vandenberghe
Mar
26
reviewed Leave Open What's the Impact if proven NP/co-NP=PSPACE on settling P=NP? The future directions it opens to settle/attack P=NP? Remaining classes left outside?
Mar
16
comment Time complexity of counting triangles in planar graphs
You can count triangles in general graphs by taking the adjacency matrix $A$ and computing $tr(A^3)/6$. This takes $n^{\omega}$ time, where $\omega < 2.373$ is the matrix multiplication exponent.
Mar
13
awarded  Nice Answer
Mar
12
answered Additive combinatorics applications in algorithm design
Mar
10
revised Problems not known to be PSPACE-complete
added 10 characters in body
Mar
10
answered Problems not known to be PSPACE-complete
Mar
9
awarded  Nice Answer
Mar
8
answered The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem