16,756 reputation
566122
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 3 months
seen yesterday

algorithms/complexity extremist


Mar
18
comment On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$
@Kaveh We certainly know that UNIFORM $TC^0$ is different from $P^{\#P}$ -- cf. Allender's circuit lower bounds for the Permanent. (Uniform $TC^0$ is the version that is relevant to the present discussion.) But yes, even separating $NP$ from uniform-$TC^0$ is open.
Mar
7
awarded  Nice Answer
Mar
6
answered Can one return to a TCS research job after an excursion to a non-research industry job?
Mar
4
reviewed Approve suggested edit on Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?
Mar
4
reviewed Approve suggested edit on How can we derive this lower bound of a special cut in a graph?
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}$