16,916 reputation
567123
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 5 months
seen yesterday

algorithms/complexity extremist


Aug
3
reviewed Close What can we say about all cycles in graphs (connected undirected graph)
Jul
7
awarded  Custodian
May
21
awarded  Custodian
May
12
comment Arguments for/against Kolmogorov's conjecture about the circuit complexity of P
Roadblocks? I don't think anyone has found the road :) Since most people believe that $P$ doesn't have $O(n^k)$ size circuits, for every fixed $k$, probably few people have even looked for the road.
May
12
awarded  Nice Answer
May
12
answered Arguments for/against Kolmogorov's conjecture about the circuit complexity of P
May
12
comment Good text on introduction to circuit complexity
Eventually, eventually :)
May
8
awarded  Good Answer
Apr
30
awarded  Electorate
Apr
18
comment Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?
This is also presently on the cs354 problem set... :-/ ... I explicitly instructed students not to ask the internet, so "Lorraine" better hope they are not taking my class.
Apr
18
comment Exponential gap on neural network layers
Well, I'm speaking about circuits composed of linear threshold functions of constant depth. That isn't more general than $TC^0$ of constant depth, however you need a greater constant depth to simulate linear threshold functions with $TC^0$. See Goldmann, Hastad, Razborov citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.1336
Apr
17
answered Exponential gap on neural network layers
Apr
16
comment Approximating $\textrm{AC}^{0}$ by sparse polynomials
Yes, such sparse polynomials would resolve many open problems... :)
Mar
9
awarded  Nice Answer
Mar
9
awarded  Nice Answer
Feb
24
awarded  Nice Answer
Feb
22
answered What would be the consequences of PH=PSPACE?
Feb
19
awarded  Enlightened
Feb
19
awarded  Nice Answer
Feb
18
awarded  Good Answer