Fetching the paper…

Reading the bibliography…

A Parallel Approximation Algorithm for Positive Semidefinite Programming · Around

2011

A Parallel Approximation Algorithm for Positive Semidefinite Programming

Jain, Rahul, Yao, Penghui

Original
PDF
Post on X

Understand

Positive semidefinite programs are an important subclass of semidefinite programs in which all matrices involved in the specification of the problem are positive semidefinite and all scalars involved are non-negative.

We present a parallel algorithm, which given an instance of a positive semidefinite program of size N and an approximation factor eps > 0, runs in (parallel) time poly(1/eps) \cdot polylog(N), using poly(N) processors, and outputs a value which is within multiplicative factor of (1 + eps) to the optimal.
Our result generalizes analogous result of Luby and Nisan [1993] for positive linear programs and our algorithm is inspired by their algorithm.

Built on

A parallel approximation algorithm for positive linear programming
Michael Luby and Noam Nisan · 1993
Earlier work this paper cites.
Matrix Analysis
Rajendra Bhatia · 1996
Earlier work this paper cites.
Quantum speed-up of markov chain based algorithms
Mario Szegedy · 2004
Earlier work this paper cites.
Fast algorithms for approximate semidefinite programming using the multiplicative weights update method
S. Arora, E. Hazan, and S. Kale · 2005
Earlier work this paper cites.
Quantum Arthur—Merlin games
Chris Marriott and John Watrous · 2005
Earlier work this paper cites.

Similar

Witness-preserving QMA amplification, quantum computation lecture notes
Oded Regev · 2006
Cited alongside, same era.
Any AND-OR formula of size n n can be evaluated in time n 1 / 2 + o ⁡ ( 1 ) n^{1/2+o(1)} on a quantum computer
Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Spalek, and Shengyu Zhang · 2007
Cited alongside, same era.
A combinatorial, primal-dual approach to semidefinite programs
S. Arora and S. Kale · 2007
Cited alongside, same era.
Efficient algorithms using the multiplicative weights update method
S. Kale · 2007
Cited alongside, same era.
Essai sur la géométrie à n n dimensions
Camille Jordan
Cited in the paper.

Then

Two-message quantum interactive proofs are in PSPACE
Rahul Jain, Sarvagya Upadhyay, and John Watrous · 2009
Later among the works it cites.
Parallel approximation of non-interactive zero-sum quantum games
Rahul Jain and John Watrous · 2009
Later among the works it cites.
Fast amplification of QMA
Daniel Nagaj, Pawel Wocjan, and Yong Zhang · 2009
Later among the works it cites.
QIP = PSPACE
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous · 2010
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…