meta user
network profile
| bio | website | stanford.edu/~rrwill |
|---|---|---|
| location | California | |
| age | ||
| visits | member for | 2 years, 10 months |
| seen | Jun 12 at 23:05 | |
| stats | profile views | 3,113 |
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.) |
|
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 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 :) |
|
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. |
|
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 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 8 |
comment |
Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$ Scott: I've no doubt that is also true! |
|
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! |
|
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 21 |
comment |
The computational complexity of matrix multiplication Just 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.) |
|
Nov 21 |
comment |
Complexity class associated with exhaustive search It'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] |
|
Jul 20 |
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.) |
|
Jun 16 |
comment |
A lottery that you can be convinced that it is fair The 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/… |
|
May 17 |
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. |
|
Apr 15 |
comment |
Proofs, Barriers and P vs NP I 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}}$.") |
|
Mar 22 |
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? |
