15,607 reputation
462115
bio website stanford.edu/~rrwill
location California
age
visits member for 3 years, 8 months
seen yesterday

algorithms/complexity extremist


Mar
4
reviewed Approve suggested edit on Status on circuit lower bounds for polylog-bounded depth circuits
Feb
28
comment logic in the presence of doubt, uncertainty, lies
The question is very open-ended, but I like Harry Frankfurt and I like the idea of trying to formalize what he's doing. (This almost sounds like a question that Manuel Blum would ask!) Still I think it is generally difficult to give appropriate answers in this kind of forum. Someone might point you to existing literature on uncertainty in logic, but it's unlikely we will be able to help you formalize bullsh*t.
Feb
15
comment Lower bound for determinant and permanent
That's interesting.... recently (eccc.hpi-web.de/report/2013/026) a $2^{O(n^{1/2}\log n})$ upper bound has been proved over the complex numbers. So there is somehow a huge difference in characteristic zero and finite fields...
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