Faster inverse maintenance for faster conic programming

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=cNOtHarr9Bk


Duration: 14:26
192 views
3

Shunhua Jiang (Columbia University)
https://simons.berkeley.edu/talks/shunhua-jiang-columbia-university-2023-09-08
Meet the Fellows Welcome Event Fall 2023

Conic optimization includes some of the most well-known convex optimization problems, all of which require the variables to be inside a specific convex cone. Many recent progress in conic programming comes from improving the cost per iteration by designing faster dynamic data structures. In this talk I will cover some recent results of faster algorithms for linear programming (LP), semidefinite programming (SDP), and sum-of-squares (SOS) optimization using faster inverse maintenance data structures, where each data structure exploits the special structures of the optimization problem itself.



Other Videos By Simons Institute for the Theory of Computing


2023-09-08Sampling and Approximately Counting CNF Formula Solutions in the Local Lemma Regime
2023-09-08Massively Parallel Join Algorithms
2023-09-08Relational Programming
2023-09-08Title: Research Interests and Latest Works
2023-09-08What can the demand analyst learn from machine learning?
2023-09-08From Robustness to Privacy and Back
2023-09-08Decoding the Maze: New Frontiers in Achieving Nash Equilibrium in AI Architectures
2023-09-08Risk Convergence and Algorithmic Regularization of Discrete-Stepsize (Stochastic) Gradient Descent
2023-09-08Quantum Cryptography in Algorithmica
2023-09-08Noncommutative constraint satisfaction problems
2023-09-08Faster inverse maintenance for faster conic programming
2023-09-08Unifying strongly polynomial algorithms for subclasses of Linear Programs
2023-09-08Fast sparsification via convex optimization and chaining
2023-09-08Practical Graph Algorithms: Scalability and Privacy
2023-09-08Recent advances in vertex connectivity
2023-09-08Shortest paths, dynamic algorithms, and fine-grained complexity
2023-09-08Recent Trends in Minimum Cut Algorithms
2023-09-05Introduction to Data Structures and Optimization for Fast Algorithms
2023-09-01Optimization: Interior Point Methods Part 2
2023-09-01Optimization: Interior Point Methods Part 1
2023-09-01Matrix Data Structures


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Meet the Fellows Welcome Event Fall 2023
Shunhua Jiang