16,212 reputation
564121
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 2 months
seen 10 hours ago

algorithms/complexity extremist


Jan
31
comment Complexity Class NEXP$^\text{NP}$
Note that $NEXP^{NP}$ does have another name in the literature (based on the alternation characterization), namely $\Sigma_2 EXP$.
Jan
16
awarded  Good Answer
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