Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 6 of 6 for “"Smoothed analysis"”.
-
Smoothed analysis of Gaussian elimination
We present a smoothed analysis of Gaussian elimination, both with partial pivoting and without pivoting. Let A be any matrix and let A be a slight random perturbation of A. We prove that it is unlikely that A has large condition number. Using this result, we prove it is unlikely that A has large …
-
Search and optimization with randomness in computational economics: equilibria, pricing, and decisions
… into two categories: First, we address the smoothed analysis of Nash equilibrium computation. Second, we address two pricing problems in mechanism design, and solve two economically motivated stochastic optimization problems. Computing Nash equilibria is a central question in the …
-
A geometric theory of outliers and perturbation
… Shang-Hua Teng. This result forms part of the smoothed analysis project initiated by Spielman and Teng to better explain mathematically the observed performance of algorithms.
-
Probabilistic Models and Algorithmic Analysis of Network Problems
… Tree (MST) in particular. We propose the Smoothed Analysis, where the key is to randomly and slightly alter the input, and show new asymptotic bounds. For the MST problem, we also design an algorithm that almost matches the lower bound. In the second problem, we study influence spreading …
-
Quantitative invertibility of random matrices : a combinatorial perspective
… connection with the strong circular law, and the smoothed analysis of the condition number, and our results extend and improve upon theirs in a couple of ways. As opposed to all previous works obtaining such bounds with error rate better than n-1, our proof makes no use either of the inverse …
-
Smoothed Online Learning: Theory and Applications
… constrained in a natural way motivated by the smoothed analysis of algorithms. The first part covers the statistical rates achievable by an arbitrary algorithm without regard to efficiency, covering both the fully adversarial setting and the constrained setting in which improved rates are …