16,202 reputation
564120
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 1 month
seen yesterday

algorithms/complexity extremist


May
30
comment Is there an explanation for the difficulty of proving quadratic lower bounds for interesting NP problems?
The question of quadratic time lower bounds is relevant when you restrict the algorithms to have very little (e.g., polylog) space, or when you look at one-tape Turing machines (which have very restricted access to memory). But when memory is unrestricted, and memory access is unrestricted, the "real" question is whether there are super-linear time lower bounds for interesting NP problems, in any random-access computational model. (Grandjean proved some super-linear lower bounds for multitape Turing machines, but they rely on the structure of one-dimensional tapes.)
May
23
awarded  Nice Answer
May
22
answered Books/Lecture Notes on Parametrized Complexity
May
20
awarded  Nice Answer
Apr
7
awarded  Popular Question
Apr
4
comment What is the fastest known simulation of BPP using Las Vegas algorithms?
Hi Arul, luckily Bill Gasarch asked me this question a while back, and put up the following webpage of links: cs.umd.edu/~gasarch/ryan/ryan.html
Apr
2
comment What is the fastest known simulation of BPP using Las Vegas algorithms?
Not stupid at all -- indeed, $BPP \subseteq NTIME(2^{n^c})$ for some $c$ is enough for $BPP \neq NEXP$, thanks for pointing that out. Subexponential time algorithms are necessary for the other consequences, though.
Apr
2
awarded  Nice Answer
Apr
1
comment What is the fastest known simulation of BPP using Las Vegas algorithms?
Thanks to Niel for taking the time to make my response legible :)
Apr
1
revised What is the fastest known simulation of BPP using Las Vegas algorithms?
added 43 characters in body
Apr
1
answered What is the fastest known simulation of BPP using Las Vegas algorithms?
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$.