ADVANCED ALGORITHMS

COMPSCI/ISYE/MATH 728

Introduces optimization problems over integers, and surveys the theory behind the algorithms used in state-of-the-art methods for solving such problems. Special attention is given to the polyhedral formulations of these problems, and to their algebraic and geometric properties. Applicability of Integer Optimization is highlighted with applications in combinatorial optimization. Key topics include: formulations, relaxations, polyhedral theory, cutting planes, decomposition, enumeration. Students are strongly encouraged to have knowledge of Linear Programming (e.g.,MATH/​COMP SCI/​I SY E/​STAT  525), including algorithms, duality and polyhedral theory.

COMPSCI 577

Basic paradigms for the design and analysis of efficient algorithms: greed, divide-and-conquer, dynamic programming, reductions, and the use of randomness. Computational intractability including typical NP-complete problems and ways to deal with them.

COMPSCI/ISYE 526

Review of linear programming. Polynomial time methods for linear programming. Quadratic programs and linear complementarity problems and related solution techniques. Solution sets and their continuity properties. Error bounds for linear inequalities and programs. Parallel algorithms for linear and quadratic programs.

COMPSCI 880

Advanced topics in algorithms, complexity, and cryptography. The exact topic varies.

MATH 718

Random solvers have been playing increasingly crucial roles in the modern computational tasks. The recent breakthroughs in applied and computational linear algebra that incorporate techniques of randomization have proven to be of great importance in modern applied math, computational sciences and data science, such as inverse problems, machine learning and scientific computing. The guiding principle is that one may greatly reduce computational and storage expenses at the cost of a small probability of failure. Systematic study of these modern methods of randomized linear algebra solvers will be provided, presenting mathematical backgrounds, algorithms, and concrete applications. Core theoretical topics include randomized Kaczmarz and its generalization to stochastic gradient descent, randomized singular value decomposition, random sketching, matrix completion, and compressive sensing, and corresponding applications.