18,473 reputation
571133
bio website stanford.edu/~rrwill
location California
age
visits member for 5 years
seen 12 hours ago

algorithms/complexity extremist


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 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