16,162 reputation
564119
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 1 month
seen 2 days ago

algorithms/complexity extremist


Jan
11
awarded  Enlightened
Jan
11
awarded  Nice Answer
Jan
10
comment DFA intersection in subquadratic space?
I just saw this answer... I don't see why the algorithm runs in polytime and $O(\log^2 n)$ space simultaneously. Yes, $NL \subseteq P \cap DSPACE[\log^2 n]$, but it is not known if $NL \subseteq TISP[n^{O(1)}, \log^2 n]$ -- that is, we can get an algorithm running in polytime, and we can get another algorithm running in $O(\log^2 n)$ space, but I do not know how to solve $NL$ problems in polytime and $O(\log^2 n)$ space with a single algorithm.
Jan
9
awarded  Enlightened
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