16,212 reputation
564121
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 2 months
seen 16 hours ago

algorithms/complexity extremist


Oct
22
awarded  Enlightened
Oct
9
awarded  Nice Answer
Oct
9
revised Barriers to separating other complexity classes
added 11 characters in body
Oct
8
answered Barriers to separating other complexity classes
Oct
7
reviewed Approve suggested edit on “All-different hypergraph coloring” - known problem?
Sep
29
reviewed Approve suggested edit on Ladner's Theroem Proof
Sep
27
reviewed Approve suggested edit on Geometric Interpretation of Computation
Sep
21
revised References for TCS proof techniques
Fixed the URL
Sep
13
reviewed Approve suggested edit on Questions about computing matrix rigidity
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