16,831 reputation
566122
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 4 months
seen 5 mins ago

algorithms/complexity extremist


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
Jan
24
awarded  Constituent
Jan
14
awarded  Caucus
Jan
6
awarded  Citizen Patrol
Dec
23
answered Testing boolean vectors orthogonality with fast query-time