Mathematical Tools and Efficient Algorithms (Richard Peng)

Brief Introduction

This course will discuss efficient algorithms built upon probability, functional analysis, and number theory. The four lectures will focus on:

  1. Randomized graph algorithms
  2. Linear systems solvers and iterative methods.
  3. Matrix concentration and its applications.
  4. Number theoretic algorithms.


2018-07-24 ~ 2018-08-02   


Richard Peng, Georgia Institute of Technology


Room 101, No.4 Teaching Building, Shanghai University of Finance & Economics

Application and Registration

No registration fee.


  1. Randomized graph algorithms / 图论随机算法

   Parallel shortest paths / 最短路径的并行算法

   Spanners and graph decompositions / 支撑图和图的分割

   L_0 estimators / 基数估计


  1. Linear system solvers and iterative methods / 线性方程和迭代算法

  Iterative refinement / 迭代算法

  Graph sparsification / 图的稀疏化

  Sparsified Cholesky / 非完全高斯消元


  1. Matrix concentration and its applications / 矩阵大数定理和其应用

  Graph sparsification via matrix concentration / 图稀疏化的证明

  Input sparsity time algorithms / 稀疏化与算法的结合

  Sparsification based data structures / 基于稀疏化的数据结构


  1. Number theoretic algorithms / 算法数论

  Primality testing / 质数判断

  RSA / 公钥密码

  Dixon’s algorithm / 更快的因子分解算法

Contact Us

Huili Liang

Directions to ITCS

View Direction Page