15,902 reputation
563118
bio website stanford.edu/~rrwill
location California
age
visits member for 3 years, 11 months
seen Jul 13 at 13:33

algorithms/complexity extremist


Sep
6
awarded  Nice Answer
Sep
1
awarded  Sportsmanship
Aug
31
answered Hardness of a subcase of Set Cover
Aug
24
reviewed Approve suggested edit on Fast treewidth algorithms
Aug
22
comment The size of output in circuit complexity
If you are being this strict, then why believe that $P$ is contained in $P/poly$? There are languages over $\{0,1,2\}$ (for example) in $P$ but these cannot be recognized by Boolean circuits, as Boolean circuits only accept $\{0,1\}$ inputs. My point is that in order to show $P \subset P/poly$, we already have to assume some binary encoding convention for inputs, so why not also assume a binary encoding convention for outputs?
Aug
22
revised Beigel-Tarui transformation of ACC cricuits
edited body
Aug
22
revised Beigel-Tarui transformation of ACC cricuits
edited body
Aug
22
answered Advanced techniques for determining complexity lower bounds
Aug
22
answered Beigel-Tarui transformation of ACC cricuits
Aug
22
reviewed Approve suggested edit on Online version of All pair shortest path when path weights are updated
Aug
17
awarded  Yearling
Jun
22
comment Evaluation of bounded-depth circuits
Andras' question is indeed important. I thought about this question a couple of years ago and believe I concluded that $k(d)=d+1$ for both $AC^0$ and $TC^0$, using the appropriate input representation (which is crucial).
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