查看更多关于哥德尔奖, 滕尚华的内容。

9条留言 -> 跳到留言表格

• At 2008.05.30 01:45, Think said:

  Rolf Nevanlinna Prize也是很牛的么，呵呵。RAZBOROV两个都得了。。。
  ICALP这个会议还挺有特色的，我比较喜欢。

  [Reply]
• At 2008.05.30 13:00, Yuhan Zhang said:

  记得Smale证过类似的结果。如果线性规划的参数矩阵满足一定分布（好像是独立正态分布），那么线性规划规模趋于无穷时，单纯型法需要的步数的期望值是多项式级的（好像是这么个结果，我有可能记错了）。

  [Reply]
  • At 2008.05.31 04:03, zhiqiang said:
    你说的正exactly是滕老师他们的工作。Smale不是数学家么，怎么也做起算法了，你是不是记错了？

    [Reply]
• At 2008.05.31 04:47, ryan said:
  那个题目很有趣:)

  [Reply]
• At 2008.05.31 17:19, AI said:

  Smale当然做过LP的复杂性问题

  Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time 这篇文章里面还引用两篇，分别是文献24和25

  24 S. Smale. The problem of the average speed of the simplex method. In Proceedings of the 11th International Symposium on Mathematical Programming, pages 530-539, August 1982.
  25 S. Smale. On the average number of steps in the simplex method of linear programming. Mathematical Programming, 27:241-262, 1983.

  [Reply]
  • At 2008.06.01 19:23, zhiqiang said:
    你说的对，我看了Smale的publication lists，他有大量关于复杂性方面的文章，比如最近还有一篇“Algebraic Settings for the Problem "P=NP"”。这是我以前不知道的。看来数学家有向理论计算机方向流动的趋势，比如最近还有terry tao也是如此。

    至于你说的这两篇文章，我只稍微看了一下摘要（狗屁清华居然无法直接下全文），文章里面应该只是分析了avarage complexity，这和腾老师的smoothed analysis还是不太一样的。你说的“如果线性规划的参数矩阵满足一定分布（好像是独立正态分布），那么线性规划规模趋于无穷时，单纯型法需要的步数的期望值是多项式级的”是滕尚华老师他们的工作。

    [Reply]
    • At 2008.06.01 20:52, AI said:

      呵呵，咱一个学校的

      另外，“如果线性规划的参数矩阵……”这句话不是我说的，呵呵

      此外，决定跟着一起来分肉了

      [Reply]
      • At 2008.06.01 22:27, zhiqiang said:
        sorry，没注意留言者名字

        你是哪位？要做smoothed analysis的话，滕尚华老师现在就在清华，你可以跟他讨论讨论。

        [Reply]
        • At 2008.06.02 21:03, AI said:

          多谢您提醒，不过目前还不准备去打搅滕老师

          [Reply]

zhiqiang(change) will say:

昵称 (Required)
邮件 (Required, not published)
网址

  B | I | U | D | 添加链接 | 插入引用 | 插入代码 | | 甲 | + | ?