A cutting plane approach to upper bounds on the kissing number

Upper bounds for the kissing number can be written as a semidefinite program (SDP) through the Delsarte-Goethals-Seidel method for spherical codes. This thesis solves the resulting SDP with a cutting plane approach, in which a sequence of linear programs (LPs) is solved with the addition of linear constraints every round. We study the...

Convergence of the mixing method: An iterative algorithm for solving diagonally constrained semidefinite programs

This thesis explores the convergence of the mixing method, an iter- ative algorithm for solving diagonally constrained semidefinite programs. In this paper we first give an exposition of the convergence proof for the mixing method based on the proof by Wang, Chang, and Kolter , where we restructure some parts of the proof and provide extra de-...

Geometry and Reconstruction of Bipartite Quantum Correlations

The first part of this thesis provides a mathematical description for bipartite quantum correlations, aiming to analyze the geometry of several sets of correlations. We explain why quantum entanglement can be used to simulate shared randomness: C_loc(Γ) ⊆ C_q^d(Γ) for a sufficiently large d. The known bound for this...

Quantum Coin Flipping: and Circuit Design Problems in Distributed Quantum Computing

Quantum coin flipping is a cryptographic primitive in which two or more parties that do not trust each other want establish a fair coin flip. These parties are not physically near each other and use quantum communication channels to interact. A quality of protocols is measured by the best possible cheating strategy, which is the solution of a...

Kernel-function based algorithms for semidefinitie optimization

Recently, Y.Q. Bai, M. El Ghami and C. Roos [3] introduced a new class of so-called eligible kernel functions which are defined by some simple conditions. The authors designed primal-dual interiorpoint methods for linear optimization (LO) based on eligible kernel functions and simplified the analysis of these methods considerably. In this paper...

A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization

Interior-point methods for semidefinite optimization have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, the second author designed a primal-dual infeasible interior-point algorithm with the currently best iteration bound for linear optimization problems. Since the algorithm uses only full Newton...

New Primal-dual Interior-point Methods Based on Kernel Functions

Two important classes of polynomial-time interior-point method (IPMs) are small- and large-update methods, respectively. The theoretical complexity bound for large-update methods is a factor $\sqrt{n}$ worse than the bound for small-update methods, where $n$ denotes the number of (linear) inequalities in the problem. In practice the situation is...