אירועים קרובים
14ביולי
בשעה 12:00
בניין 37 חדר ישיבות 201
AI Institutes Seminar - Prof. Mark Rudelson
Dear all,
We are delighted to have a special talk by Prof. Mark Rudelson, who has made great foundational contributions to the fields of probability theory and geometric analysis.
The talk details are as follows.
Speaker: Prof. Mark Rudelson
Affiliation: Department of Mathematics, University of Michigan
Host: Prof. Aryeh Kontorovich
Title: Low Complexity Smoothed Analysis
Abstract:
Perturbing a deterministic n-dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms. The idea of adding the noise to a given deterministic matrix was introduced by Spielman and Teng in 2004. This noise reduces the condition number of the input matrix to O(n), and with it the complexity of many matrix algorithms. Moreover, it is oblivious to the input as it does not require any prior knowledge of the matrix besides a crude bound on its norm.
However, when deployed algorithmically, this method is expensive due to the cost of generating and storing n^2 Gaussian random variables. We will describe a random matrix construction which requires generating O(n) independent random variables and reduces the condition number of any deterministic matrix to O(n), thus matching Gaussian perturbations. Using so few independent variables requires generating a random matrix with dependent entries thus making the condition number analysis more involved.
Joint work with Shabarish Cenakkod, Michal Derezinski, and Xiaoyu Dong.
29ביולי
בשעה 16:00
Zoom - קישור למפגשים יישלחו לנרשמים ולנרשמות לאירוע
08באוקטובר
בשעה 09:30
בקמפוס האוניברסיטה
כנס ארצי במדעי המחשב והשקת האיגוד הישראלי למדעי המחשב
אוניברסיטת בן־גוריון בנגב | 8 באוקטובר 2026
