The complexity of solving linear programs has interested researchers for half a century now. We show that an arbitrary linear program subject to a small random relative perturbation has good condition number with high probability, and hence is easy to solve. This is joint work with Avrim Blum, Daniel Spielman, and 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.

1. We show that any s-term DNF over n variables can be computed by a polynomial threshold function of order O (n^¹/³ log s). As an immediate consequence we obtain the fastest known DNF learning algorithm which runs in time 2 ^{Õ (n¹/³)}.
2. We give the first polynomial time algorithm to learn an intersection of a constant number of halfspaces under the uniform distribution to within any constant error parameter. As a corollary we can learn any neural network in which there a k bottom level gates (threshold functions) that the inputs feed into in time n^O(k²/²). We also give the first quasipolynomial time algorithm for learning any function of a constant number of halfspaces with polynomial bounded weights under any distribution.
3. We give an algorithm to learn constant-depth polynomial-size circuits augmented with majority gates under the uniform distribution using random examples only. For circuits which contain a polylogarithmic number of majority gates the algorithm runs in quasipolynomial time. Under a suitable cryptographic assumption we show that these are the most expressive circuits which will admit a non-trivial learning algorithm.

       I also show some stability results under more general circumstances. If the packets are inserted by any ergodic hidden Markov process with nominal loads less than one, and routed by any greedy protocol, I prove that the ring is ergodic.

       SVMs solve classification problems by learning from training examples. From the geometry, it is easy to formulate the finding of SVM classifiers as a linearly constrained Quadratic Programming (QP) problem. However, in practice its dual problem is actually computed. An important property of the dual QP problem is that its solution is sparse. The training examples that determine the SVM classifier are known as Support Vectors (SVs).

       Motivated by the geometric derivation of the primal QP problem, we investigate how the dual problem is related to the geometry. This investigation leads to a geometric interpretation of the scaling property of SVMs and an algorithm to further compress SVs. The randomness of the training examples connects the Hessian matrix of the dual QP problem to Wishart matrices. After deriving the distributions of the elements of the inverse Wishart matrix W_n^-1 (n,nI ), we give a conjecture about the summation of the elements of W_n^-1 (n,nI ). It becomes challenging to solve the dual QP problem when the training set is large. We develop a fast algorithm for solving this problem. Numerical experiments show that the MATLAB implementation of this projected Conjugate Gradient algorithm is competitive with benchmark C/C++ codes such as SVM ^light and SvmFu. Furthermore, we apply SVMs to time series data. In this application, SVMs are used to predict the movement of the stock market. Our results show that SVMs have the potential to outperform the geometric Brownian motion model of stock prices.