Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userElementary proofs of Kempe universality
83
0
0.0
(
0
)
Authors
S. C. Power
Ask ChatGPT about the research
No Arabic abstract
An elementary proof is given to show that a parametrised algebraic curve in the plane may be traced out, in the sense of A. B. Kempe, by a finite pinned linkage. Additionally it is shown that any parametrised continuous curve gamma: [0,1] to R^2 may be traced out by an infinite linkage where the valencies of the joints is uniformly bounded. We also discuss related Kempe universality theorems and give a novel correction of Kempes original argument.
rate research
Read More
In this short note we prove two elegant generalized continued fraction formulae $$e= 2+cfrac{1}{1+cfrac{1}{2+cfrac{2}{3+cfrac{3}{4+ddots}}}}$$ and $$e= 3+cfrac{-1}{4+cfrac{-2}{5+cfrac{-3}{6+cfrac{-4}{7+ddots}}}}$$ using elementary methods. The first formula is well-known, and the second one is newly-discovered in arXiv:1907.00205 [cs.LG]. We then explore the possibility of automatic verification of such formulae using computer algebra systems (CASs).
In this paper we provide several emph{metric universality} results. We exhibit for certain classes $cC$ of metric spaces, families of metric spaces $(M_i, d_i)_{iin I}$ which have the property that a metric space $(X,d_X)$ in $cC$ is coarsely, resp. Lipschitzly, universal for all spaces in $cC$ if the collection of spaces $(M_i,d_i)_{iin I}$ equi-coarsely, respectively equi-Lipschitzly, embeds into $(X,d_X)$. Such families are built as certain Schreier-type metric subsets of $co$. We deduce a metric analog to Bourgains theorem, which generalized Szlenks theorem, and prove that a space which is coarsely universal for all separable reflexive asymptotic-$c_0$ Banach spaces is coarsely universal for all separable metric spaces. One of our coarse universality results is valid under Martins Axiom and the negation of the Continuum Hypothesis. We discuss the strength of the universality statements that can be obtained without these additional set theoretic assumptions. In the second part of the paper, we study universality properties of Kaltons interlacing graphs. In particular, we prove that every finite metric space embeds almost isometrically in some interlacing graph of large enough diameter.
We study the (Ahlfors regular) conformal dimension of the boundary at infinity of Gromov hyperbolic groups which split over elementary subgroups. If such a group is not virtually free, we show that the conformal dimension is equal to the maximal value of the conformal dimension of the vertex groups, or 1, whichever is greater, and we characterise when the conformal dimension is attained. As a consequence, we are able to characterise which Gromov hyperbolic groups (without $2$-torsion) have conformal dimension 1, answering a question of Bonk and Kleiner.
Let $G$ be a finite $d$-regular graph with a proper edge coloring. An edge Kempe switch is a new proper edge coloring of $G$ obtained by switching the two colors along some bi-chromatic cycle. We prove that any other edge coloring can be obtained by performing finitely many edge Kempe switches, provided that $G$ is replaced with a suitable finite covering graph. The required covering degree is bounded above by a constant depending only on $d$.
A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparable resources cannot. Providing a proof of quantumness is the first step towards constructing a useful quantum computer. There are currently three approaches for exhibiting proofs of quantumness: (i) Inverting a classically-hard one-way function (e.g. using Shors algorithm). This seems technologically out of reach. (ii) Sampling from a classically-hard-to-sample distribution (e.g. BosonSampling). This may be within reach of near-term experiments, but for all such tasks known verification requires exponential time. (iii) Interactive protocols based on cryptographic assumptions. The use of a trapdoor scheme allows for efficient verification, and implementation seems to require much less resources than (i), yet still more than (ii). In this work we propose a significant simplification to approach (iii) by employing the random oracle heuristic. (We note that we do not apply the Fiat-Shamir paradigm.) We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function. In contrast to earlier proposals we do not need an adaptive hard-core bit property. This allows the use of smaller security parameters and more diverse computational assumptions (such as Ring Learning with Errors), significantly reducing the quantum computational effort required for a successful demonstration.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
