Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSemidefinite programming bounds for the average kissing number
189
0
0.0
(
0
)
Added by
Fernando M\\'ario De Oliveira Filho
Publication date
2020
fields
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The average kissing number of $mathbb{R}^n$ is the supremum of the average degrees of contact graphs of packings of finitely many balls (of any radii) in $mathbb{R}^n$. We provide an upper bound for the average kissing number based on semidefinite programming that improves previous bounds in dimensions $3, ldots, 9$. A very simple upper bound for the average kissing number is twice the kissing number; in dimensions $6, ldots, 9$ our new bound is the first to improve on this simple upper bound.
rate research
Read More
This paper investigates the behaviour of the kissing number $kappa(n, r)$ of congruent radius $r > 0$ spheres in $mathbb{S}^n$, for $ngeq 2$. Such a quantity depends on the radius $r$, and we plot the approximate graph of $kappa(n, r)$ with relatively high accuracy by using new upper and lower bounds that are produced via semidefinite programming and by using spherical codes, respectively.
This paper provides upper and lower bounds on the kissing number of congruent radius $r > 0$ spheres in $mathbb{H}^n$, for $ngeq 2$. For that purpose, the kissing number is replaced by the kissing function $kappa(n, r)$ which depends on the radius $r$. After we obtain some theoretical lower and upper bounds for $kappa(n, r)$, we study their asymptotic behaviour and show, in particular, that $lim_{rto infty} frac{log kappa(n,r)}{r} = n-1$. Finally, we compare them with the numeric upper bounds obtained by solving a suitable semidefinite program.
In this paper we give an algorithm to round the floating point output of a semidefinite programming solver to a solution over the rationals or a quadratic extension of the rationals. We apply this to get sharp bounds for packing problems, and we use these sharp bounds to prove that certain optimal packing configurations are unique up to rotations. In particular, we show that the configuration coming from the $mathsf{E}_8$ root lattice is the unique optimal code with minimal angular distance $pi/3$ on the hemisphere in $mathbb R^8$, and we prove that the three-point bound for the $(3, 8, vartheta)$-spherical code, where $vartheta$ is such that $cos vartheta = (2sqrt{2}-1)/7$, is sharp by rounding to $mathbb Q[sqrt{2}]$. We also use our machinery to compute sharp upper bounds on the number of spheres that can be packed into a larger sphere.
In this note, we give a short solution of the kissing number problem in dimension three.
Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, algorithmic rounding, and adversarial deep learning. This paper presents a faster interior point method to solve generic SDPs with variable size $n times n$ and $m$ constraints in time begin{align*} widetilde{O}(sqrt{n}( mn^2 + m^omega + n^omega) log(1 / epsilon) ), end{align*} where $omega$ is the exponent of matrix multiplication and $epsilon$ is the relative accuracy. In the predominant case of $m geq n$, our runtime outperforms that of the previous fastest SDP solver, which is based on the cutting plane method of Jiang, Lee, Song, and Wong [JLSW20]. Our algorithms runtime can be naturally interpreted as follows: $widetilde{O}(sqrt{n} log (1/epsilon))$ is the number of iterations needed for our interior point method, $mn^2$ is the input size, and $m^omega + n^omega$ is the time to invert the Hessian and slack matrix in each iteration. These constitute natural barriers to further improving the runtime of interior point methods for solving generic SDPs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
