16,292 reputation
564122
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 2 months
seen 51 mins ago

algorithms/complexity extremist


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
Dec
19
awarded  Nice Answer
Dec
4
comment Computational Model in SETH
Not quite. I fixed the quantifiers.
Dec
4
revised Computational Model in SETH
whoops on SETH
Dec
4
reviewed Reject suggested edit on Implemented code to compute pathwidth (= Node search number, vertex separation number, interval thickness)
Dec
4
reviewed Approve suggested edit on Major unsolved problems in theoretical computer science?