「計算機科学のノーベル賞」ことチューリング賞の2023年度受賞者が計算のランダム性の理解に貢献したアヴィ・ヴィグダーソン氏に決定 [すらいむ★]

**すらいむ ★** · 2024/04/12(金) 22:14:00.58

「計算機科学のノーベル賞」ことチューリング賞の2023年度受賞者が計算のランダム性の理解に貢献したアヴィ・ヴィグダーソン氏に決定

　計算機科学分野で優れた業績を残した人物に与えられるチューリング賞の2023年度受賞者に、イスラエル出身でプリンストン高等研究所の計算機科学者であるアヴィ・ヴィグダーソン氏が選ばれました。
　ヴィグダーソン氏は、「計算におけるランダム性の理解の再構築」および「理論コンピューターサイエンスにおける数十年にわたる知的リーダーシップ」が認められたとのことです。

　2023 Turing Award
　https://awards.acm.org/about/2023-turing

（以下略、続きはソースでご確認ください）

Gigazine 2024年04月11日 16時46分
https://gigazine.net/news/20240411-avi-wigderson-wins-turing-award/

**名無しのひみつ** · 2024/04/12(金) 22:43:28.17

こんな仕事がしたかった

**名無しのひみつ** · 2024/04/13(土) 01:40:35.90

（疑似）乱数やチャイティン複雑性やランダム化比較試験とか混合戦略とかお手軽な割に強力なランダムネス利用法は好き

**名無しのひみつ** · 2024/04/13(土) 13:23:01.07

モンテカルロ法

**名無しのひみつ** · 2024/04/13(土) 13:53:10.50

黒板に見たこともない記号を使ってスラスラと計算式を書く研究者にあこがれる

**名無しのひみつ** · 2024/04/13(土) 14:29:18.46

>>5
>>1は計算機科学だから
数学記号を使いまくる数論の研究者でなく
もっと実学寄りかなあ

**名無しのひみつ** · 2024/04/13(土) 14:52:02.07

やっぱtotoのランダムはランダムじゃねーじゃん
天文学的な確率のバクを出しやがって金返せ

**名無しのひみつ** · 2024/04/13(土) 18:54:50.94

◯◯分野のノーベル賞ってよく聞くけど、本家本元のノーベル賞受賞者って凄いんだよな。

**名無しのひみつ** · 2024/04/14(日) 04:21:51.93

記事中から引用
>「効率的な確率的アルゴリズムはすべて決定論的アルゴリズムに置き換えることが可能であり、効率的な計算のためにランダム性が必要ない」

の理論の応用で↓の手法が編み出されたのかな？

1ビットLLMの衝撃! 70Bで8.9倍高速　全ての推論を加算のみで!GPU不要になる可能性も
https://egg.5ch.net/test/read.cgi/scienceplus/1709129384/
log2(3)≒1.58

**名無しのひみつ** · 2024/04/14(日) 04:56:54.80

>>6
全然違う
この人はガチガチの数学者
計算論が専門
計算論は数学基礎論の一部で
代数学や幾何学が対象ではなく
計算が対象なだけ
計算論の創始者の一人はゲーデル
証明論で数式の複雑さと完全性や無矛盾性との関係を調べたから
計算と証明は並行関係がある

**名無しのひみつ** · 2024/04/14(日) 04:59:25.10

>>8
フィールズ賞、ゲーデル賞に比べたら
ノーベル賞は玉石混交だよ
二つよりはやや落ちるチューリング賞の方がましなくらい

**名無しのひみつ** · 2024/04/14(日) 05:13:35.24

コイツの言っていることは本末転倒

増健 · 2024/04/14(日) 06:48:45.46

「LGBT」だった罪で訴追されそうになって自殺したチューリング

**名無しのひみつ** · 2024/04/14(日) 19:05:51.12

＞「効率的な確率的アルゴリズムはすべて決定論的アルゴリズムに置き換えることが可能であり、
＞効率的な計算のためにランダム性が必要ない」

つまり、本当の数学の乱数列でなくて、決定論的に計算される疑似乱数列を使ってやっても
結果が変わらないようにできる。ということかな？

**名無しのひみつ** · 2024/04/14(日) 19:41:09.43

５億円位もらえるの？

**名無しのひみつ** · 2024/04/14(日) 19:43:27.92

最後は手計算

**名無しのひみつ** · 2024/04/15(月) 05:49:02.28

>>14
解析的に積分値を求められない場合
近傍サンプル点列に対して積分値を求めて平均を取る手法がある
サンプル点列をうまく設計すると計算量は少なく済む場合がある
その点列設計が多次元だと難しい場合は
モンテカルロ法が使われるわけだけど
乱数でも疑似乱数でもなく問題に対して解析的に良い性質の点列を使うのを準モンテカルロ法と言ってよく使われてる
ただしいつも見つけられるわけではないのだが
>>1によれば必ず可能

**名無しのひみつ** · 2024/04/15(月) 11:17:07.78

計算の複雑性クラスっていつのまにこんなに増えたんだ。もうついて行けない。
https://en.wikipedia.org/wiki/List_of_complexity_classes

**名無しのひみつ** · 2024/04/15(月) 11:18:42.78

未解決問題　P = BPP ？
BPP - 乱択アルゴリズムで多項式時間で解ける問題のクラス（解はおそらく正しい）
P - 多項式時間で解ける問題のクラス