16,012 reputation
564118
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years
seen 8 hours ago

algorithms/complexity extremist


Jan
9
awarded  Nice Answer
Jan
8
awarded  Good Answer
Jan
8
comment Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$
Scott: I've no doubt that is also true!
Jan
8
awarded  Enlightened
Jan
7
awarded  Nice Answer
Jan
7
answered Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$
Jan
6
awarded  Good Answer
Jan
6
comment Constructivity in Natural Proof and Geometric Complexity
Josh: my meager understanding is that Mulmuley's results of the form "permanent does not have polysize circuits implies polynomial-time obstructions for permanent" also require an additional derandomization hypothesis, say for PIT. (But it is an interesting question: is such a derandomization hypothesis even required, if we are already assuming the permanent doesn't have small circuits?) Thanks for the pointer to your thesis!
Jan
6
awarded  Nice Answer
Jan
4
answered Constructivity in Natural Proof and Geometric Complexity
Dec
16
awarded  Nice Answer
Dec
5
comment Lower bounds for 3SUM with a free cache
I don't understand the question. Is the cache supposed to be read-only information chosen prior to the input (i.e., "non-uniform advice")? Or can one both read and write to these $n^{\delta}$ bits, at literally no cost? Using "almost-linear" hashing, you can reduce 3SUM on $n$ numbers to $O(t^2)$ instances of 3SUM on $O(n/t)$ numbers. So if you can really access this $n^{\delta}$ space for free, then by setting $t$ so that $(n/t)\log n \approx n^{\delta}$ you get a $n^{2-\varepsilon}$ 3SUM algorithm, as the $O(t^2)$ instances would take about $O(n/t)$ time each.
Dec
1
comment Eliminating clauses from a CNF formula based on their unsatisfying truth assignments being covered by some other clause
I presume by "$C'$ is covered by some other clause $C$" you mean this: "$C \Rightarrow C'$ is a tautology." If that's the case, then why doesn't the obvious greedy algorithm work? (For each pair of clauses $C$, $C'$, remove $C'$ if $C$ implies $C'$. Repeat until no such pair exists.)
Nov
22
awarded  Nice Answer
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