# Ryan Williams

less info
reputation
355105
bio website stanford.edu/~rrwill location California age member for 2 years, 10 months seen Jun 12 at 23:05 profile views 3,113

algorithms/complexity extremist

 May30 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.) Apr4 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 Apr2 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. Apr1 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 :) Mar18 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. Feb28 comment logic in the presence of doubt, uncertainty, liesThe 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. Feb15 comment Lower bound for determinant and permanentThat'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... Jan31 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$. Jan10 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. Jan8 comment Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$Scott: I've no doubt that is also true! Jan6 comment Constructivity in Natural Proof and Geometric ComplexityJosh: 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! Dec5 comment Lower bounds for 3SUM with a free cacheI 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. Dec1 comment Eliminating clauses from a CNF formula based on their unsatisfying truth assignments being covered by some other clauseI 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.) Nov21 comment The computational complexity of matrix multiplicationJust 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.) Nov21 comment Complexity class associated with exhaustive searchIt's a little vague but I like the question. I wrote a paper about it a long time ago. Maybe this will help the Anonymous questioner: stanford.edu/~rrwill/bfsearch-rev.ps [WARNING: It's likely that I disagree with almost all of the opinions stated there, it was written 10 years ago] Jul20 comment Is #P in NP and coNP, simultaneously?A "linear number of calls to both $NP$ and $coNP$" does not require that it's a $PSPACE$ machine. (Could mean that the simulation is only in $P^{NP}$, and $\# P$ is certainly not known to be in $P^{NP}$. Still, I can't follow much of what is said above.) Jun16 comment A lottery that you can be convinced that it is fairThe earliest reference I know is: M. Blum. Coin Flipping By Telephone. CRYPTO 1981: 11-15. Can be downloaded at dm.ing.unibs.it/giuzzi/corsi/Support/papers-cryptography/… May17 comment Boolean Circuit in a Black Box?Actually, the problems BBB and BBB-F above are not currently specified as a language or decision problem (the black box is not represented as a binary string of some kind, is it?), so they cannot be in NP or PSPACE. Apr15 comment Proofs, Barriers and P vs NPI just saw this now... actually, Scott and Avi give several "algebrizing" implications too. Their notion is certainly defined in such a way as to subsume relativization. (For the implication Lance cites, they would probably say that the algebrizing implication is "$P^{\tilde{A}} = NP^{\tilde{A}}$ implies $PH^{A} \subseteq P^{\tilde{A}}$.") Mar22 comment Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?It's not obvious to me why EXP=NEXP implies E=NE. If that were true, then any $2^{n^k}$-time algorithm for Succinct3SAT can be converted into a $2^{O(n)}$-time algorithm for Succinct3SAT. Maybe you got things reversed, and you meant to ask about the other implication?