Reputation
20,223
Next privilege 25,000 Rep.
Access to site analytics
Badges
5 80 144
Newest
 Good Answer
Impact
~259k people reached

Jun
8
awarded  Nice Answer
May
30
comment Undecidable Single Programs
For any finite collection of halting instances, there is a machine that can decide that collection in linear time, since that collection can be seen as a regular language. Any yes instance of the halting problem has a finite proof that it indeed halts, namely its computation history.
May
27
answered Counting the number of K4
May
23
comment Additive combinatorics applications in algorithm design
I don't think we could use this to solve $3SAT$ faster than known algorithms -- $3SAT$ can already be solved in $1.308^n$ time.
May
12
awarded  Nice Answer
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 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