15,547 reputation
462115
bio website stanford.edu/~rrwill
location California
age
visits member for 3 years, 8 months
seen 9 hours ago

algorithms/complexity extremist


Nov
21
comment The computational complexity of matrix multiplication
Just a note: it is known (as of November 2010) that rectangular matrix multiplication isn't necessary for solving ACC SAT. (Which is good, because rectangular matrix mult is "galactic" and complex.)
Nov
21
answered Complexity class associated with exhaustive search
Nov
21
comment Complexity class associated with exhaustive search
It's a little vague but I like the question. I wrote a paper about it a long time ago. Maybe this will help the Anonymous questioner: stanford.edu/~rrwill/bfsearch-rev.ps [WARNING: It's likely that I disagree with almost all of the opinions stated there, it was written 10 years ago]
Oct
6
reviewed Approve suggested edit on Examples of non-CSLs not created through diagonalization
Sep
27
awarded  Nice Answer
Sep
27
awarded  Necromancer
Sep
27
answered Implications of proof of abc conjecture for cs theory
Sep
21
awarded  Custodian
Sep
20
reviewed Approve suggested edit on Is there a proof that addition is faster than multiplication?
Sep
12
awarded  Enlightened
Sep
11
awarded  Nice Answer
Sep
10
awarded  Notable Question
Aug
17
awarded  Yearling
Aug
14
reviewed Approve suggested edit on Tree search guided by a probabilistic oracle
Jul
26
awarded  Enlightened
Jul
26
awarded  Nice Answer
Jul
20
comment Is #P in NP and coNP, simultaneously?
A "linear number of calls to both $NP$ and $coNP$" does not require that it's a $PSPACE$ machine. (Could mean that the simulation is only in $P^{NP}$, and $\# P$ is certainly not known to be in $P^{NP}$. Still, I can't follow much of what is said above.)
Jun
16
comment A lottery that you can be convinced that it is fair
The earliest reference I know is: M. Blum. Coin Flipping By Telephone. CRYPTO 1981: 11-15. Can be downloaded at dm.ing.unibs.it/giuzzi/corsi/Support/papers-cryptography/…
Jun
8
awarded  Constituent
Jun
8
awarded  Caucus