Semidefinite programming is a fundamental tool in optimization and theoretical computer science.
Reading the bibliography…
Maximization of a linear function of variables subject to linear inequalities
George B Dantzig · 1947
Earlier work this paper cites.
Inter-reciprocity applied to electrical networks
Jan Lourens Bordewijk · 1957
Earlier work this paper cites.
Reducibility among combinatorial problems
Richard M Karp · 1972
Earlier work this paper cites.
Evaluation of the information complexity of mathematical programming problems
David B Yudin and Arkadi S Nemirovski · 1976
Earlier work this paper cites.
Cut-off method with space extension in convex programming problems
Naum Z Shor · 1977
Earlier work this paper cites.
On the shannon capacity of a graph
László Lovász · 1979
Earlier work this paper cites.
Polynomial algorithms in linear programming
Leonid G Khachiyan · 1980
Earlier work this paper cites.
A data structure for dynamic trees
Daniel D Sleator and Robert Endre Tarjan · 1981
Earlier work this paper cites.
A new implementation of sparse gaussian elimination
Robert Schreiber · 1982
Earlier work this paper cites.
Extensions of lipschitz mappings into a hilbert space
William B Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · 1984
Earlier work this paper cites.
The method of inscribed ellipsoids
Leonid G Khachiyan, Sergei Pavlovich Tarasov, and I. I. Erlikh · 1988
Earlier work this paper cites.
A polynomial-time algorithm, based on newton’s method, for linear programming
James Renegar · 1988
Earlier work this paper cites.
Making data structures persistent
James R Driscoll, Neil Sarnak, Daniel D Sleator, and Robert E Tarjan · 1989
Earlier work this paper cites.
Self-concordant functions and polynomial time methods in convex programming. preprint, central economic & mathematical institute, ussr acad
Yurii Nesterov and Arkadi Nemirovski · 1989
Earlier work this paper cites.
A new algorithm for minimizing convex functions over convex sets
Pravin M Vaidya · 1989
Earlier work this paper cites.
Optimization, approximation, and complexity classes
Christos H Papadimitriou and Mihalis Yannakakis · 1991
Earlier work this paper cites.
Conic formulation of a convex programming problem and duality
Yurii Nesterov and Arkadi Nemirovski · 1992
Earlier work this paper cites.
Computer solution of sparse linear systems
Alan George, Joseph Liu, and Esmond Ng · 1994
Earlier work this paper cites.
Approximate graph coloring by semidefinite programming
David Karger, Rajeev Motwani, and Madhu Sudan · 1994
Earlier work this paper cites.
Interior-point polynomial algorithms in convex programming
Yurii Nesterov and Arkadi Nemirovski · 1994
Earlier work this paper cites.
Approximating treewidth, pathwidth, frontsize, and shortest elimination tree
Hans L Bodlaender, John R Gilbert, Hjálmtyr Hafsteinsson, and Ton Kloks · 1995
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Michel X Goemans and David P Williamson · 1995
Cited alongside, same era.
Improved approximation algorithms for maxk-cut and max bisection
Alan Frieze and Mark Jerrum · 1997
Cited alongside, same era.
Modifying a sparse cholesky factorization
Timothy A Davis and William W Hager · 1999
Cited alongside, same era.
The volumetric barrier for semidefinite programming
Kurt M Anstreicher · 2000
Cited alongside, same era.
On the complexity of k-sat
Russell Impagliazzo and Ramamohan Paturi · 2001
Cited alongside, same era.
Solving convex programs by random walks
Dimitris Bertsimas and Santosh Vempala · 2002
Cited alongside, same era.
Properties of a cutting plane method for semidefinite programming
Kartik Krishnan and John E Mitchell · 2003
Cited alongside, same era.
Introductory lectures on convex optimization: A basic course
Yurii Nesterov · 2003
Cited alongside, same era.
A combinatorial, primal-dual approach to semidefinite programs
Sanjeev Arora and Satyen Kale · 2007
Cited alongside, same era.
Fast linear algebra is stable
James Demmel, Ioana Dumitriu, and Olga Holtz · 2007
Cited alongside, same era.
Optimal inapproximability results for max-cut and other 2-variable csps?
Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2007
Cited alongside, same era.
Expander flows, geometric embeddings and graph partitioning
Sanjeev Arora, Satish Rao, and Umesh Vazirani · 2009
Cited alongside, same era.
Follow the compressed leader: faster online learning of eigenvectors and faster mmwu
Zeyuan Allen-Zhu and Yuanzhi Li · 2017
Later among the works it cites.
Semidefinite relaxations for certifying robustness to adversarial examples
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang · 2018
Later among the works it cites.
Sparse semidefinite programs with near-linear time complexity
Richard Y Zhang and Javad Lavaei · 2018
Later among the works it cites.
A rank-1 sketch for matrix multiplicative weights
Yair Carmon, John C. Duchi, Aaron Sidford, and Kevin Tian · 2019
Later among the works it cites.
Solving linear programs in the current matrix multiplication time
Michael B Cohen, Yin Tat Lee, and Zhao Song · 2019
Later among the works it cites.
Semialgebraic Proofs and Efficient Algorithm Design
Noah Fleming, Pravesh Kothari, and Toniann Pitassi · 2019
Later among the works it cites.
Solving empirical risk minimization in the current matrix multiplication time
Yin Tat Lee, Zhao Song, and Qiuyi Zhang · 2019
Later among the works it cites.
Scalable semidefinite programming, 2019
Alp Yurtsever, Joel A. Tropp, Olivier Fercoq, Madeleine Udell, and Volkan Cevher · 2019
Later among the works it cites.
Solving tall dense linear programs in nearly linear time
Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song · 2020
Later among the works it cites.
A faster interior point method for semidefinite programming
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song · 2020
Later among the works it cites.
An improved cutting plane method for convex optimization, convex-concave games and its applications
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong · 2020
Later among the works it cites.
An O ~ ( m / ϵ 3.5 ) \widetilde{O}(m/\epsilon^{3.5}) -cost algorithm for semidefinite programs with diagonal constraints
Yin Tat Lee and Swati Padmanabhan · 2020
Later among the works it cites.
Fast algorithm for solving structured convex programs
Guanghao Ye · 2020
Later among the works it cites.
A refined laser method and faster matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2021
Later among the works it cites.
Terminal embeddings in sublinear time
Yeshwanth Cherapanamjeri and Jelani Nelson · 2021
Later among the works it cites.
A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
Sally Dong, Yin Tat Lee, and Guanghao Ye · 2021
Later among the works it cites.
Universal barrier is n-self-concordant
Yin Tat Lee and Man-Chung Yue · 2021
Later among the works it cites.
Oblivious sketching-based central path method for solving linear programming
Zhao Song and Zheng Yu · 2021
Later among the works it cites.
Deterministic decremental sssp and approximate min-cost flow in almost-linear time
Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak · 2022
Closest in time.
Symmetric sparse boolean matrix factorization and applications
Sitan Chen, Zhao Song, Runzhou Tao, and Ruizhe Zhang · 2022
Closest in time.
Solving sdp faster: A robust ipm framework and efficient implementation
Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang · 2022
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…