Higher rank antipodality

• URL: http://arxiv.org/abs/2307.16857v3
• Date: Mon, 03 Feb 2025 15:28:22 GMT
• Title: Higher rank antipodality
• Authors: Márton Naszódi, Zsombor Szilágyi, Mihály Weiner,
• Abstract summary: Motivated by general probability theory, we say that the set $S$ in $mathbbRd$ is emphantipodal of rank $k$. We show that this problem can be connected to a classical question in computer science on finding perfect hashes.
• Score: 2.7309692684728617
• License:
• Abstract: Motivated by general probability theory, we say that the set $S$ in $\mathbb{R}^d$ is \emph{antipodal of rank $k$}, if for any $k+1$ elements $q_1,\ldots q_{k+1}\in S$, there is an affine map from $\mathrm{conv}(S)$ to the $k$-dimensional simplex $\Delta_k$ that maps $q_1,\ldots q_{k+1}$ bijectively onto the $k+1$ vertices of $\Delta_k$. For $k=1$, it coincides with the well-studied notion of (pairwise) antipodality introduced by Klee. We consider the following natural generalization of Klee's problem on antipodal sets: What is the maximum size of an antipodal set of rank $k$ in $\mathbb{R}^d$? We present a geometric characterization of antipodal sets of rank $k$ and adapting the argument of Danzer and Gr\"unbaum originally developed for the $k=1$ case, we prove an upper bound which is exponential in the dimension. We show that this problem can be connected to a classical question in computer science on finding perfect hashes, and it provides a lower bound on the maximum size, which is also exponential in the dimension. By connecting rank-$k$ antipodality to $k$-neighborly polytopes, we obtain another upper bound when $k>d/2$.

Related papers

• A Variant of the Bravyi-Terhal Bound for Arbitrary Boundary Conditions [10.560637835517094]
  We consider a quotient $mathbbZD/Lambda$ of $mathbbZD$ of cardinality $n$ on a $D$-dimensional lattice quotient. We prove that if all stabilizer generators act on qubits whose indices lie within a ball of radius $rho$, the minimum distance $d$ of the code satisfies $d leq msqrtgamma_D(sqrtD + 4rho)nfracD-1D$ whenever $n1/D
  arXiv  Detail & Related papers  (2025-02-07T15:18:40Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• Monogamy of entanglement between cones [68.8204255655161]
  We show that monogamy is not only a feature of quantum theory, but that it characterizes the minimal tensor product of general pairs of convex cones. Our proof makes use of a new characterization of products of simplices up to affine equivalence.
  arXiv  Detail & Related papers  (2022-06-23T16:23:59Z)
• Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
  This topic is an important direction in the modern statistical theory of kernel-based methods. We discuss a number of consequences of our bounds and show that they are substantially tighter than bounds for general kernels.
  arXiv  Detail & Related papers  (2022-04-09T16:45:22Z)
• Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
  This paper studies the problem of matching two complete graphs with edge weights correlated through latent geometries. We derive an approximate maximum likelihood estimator, which provably achieves, with high probability, perfect recovery of $pi*$. As a side discovery, we show that the celebrated spectral algorithm of [Ume88] emerges as a further approximation to the maximum likelihood in the geometric model.
  arXiv  Detail & Related papers  (2022-02-22T04:14:45Z)
• Mutually unbiased bases: polynomial optimization and symmetry [1.024113475677323]
  A set of $k$ orthonormal bases of $mathbb Cd$ is called mutually unbiased $|langle e,frangle |2 = 1/d$ whenever $e$ and $f$ are basis vectors in distinct bases. We exploit this symmetry (analytically) to reduce the size of the semidefinite programs making them tractable.
  arXiv  Detail & Related papers  (2021-11-10T14:14:53Z)
• Determining when a truncated generalised Reed-Solomon code is Hermitian self-orthogonal [0.7614628596146599]
  We prove that there is a Hermitian self-orthogonal $k$-dimensional truncated generalised Reed-Solomon code of length $n$ over $mathbb F_q2$. We also provide examples of Hermitian self-orthogonal $k$-dimensional Reed-Solomon codes of length $q2+1$ over $mathbb F_q2$, for $k=q-1$ and $q$ an odd power of two.
  arXiv  Detail & Related papers  (2021-06-18T15:16:44Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.