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.

Time

2018-07-24 ~ 2018-08-02   

Lecturers

Richard Peng, Georgia Institute of Technology

Venue

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

Application and Registration

Program

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

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

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

   L_0 estimators / 基数估计

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

  Iterative refinement / 迭代算法

  Graph sparsification / 图的稀疏化

  Sparsified Cholesky / 非完全高斯消元

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

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

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

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

4. Number theoretic algorithms / 算法数论

  Primality testing / 质数判断

  RSA / 公钥密码

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

Contact Us

Huili Liang

Directions to ITCS

View Direction Page