Search results for "Computation Theory & Mathematics"
showing 10 items of 332 documents
Special arrangements of lines: Codimension 2 ACM varieties in P 1 × P 1 × P 1
2019
In this paper, we investigate special arrangements of lines in multiprojective spaces. In particular, we characterize codimension 2 arithmetically Cohen–Macaulay (ACM) varieties in [Formula: see text], called varieties of lines. We also describe their ACM property from a combinatorial algebra point of view.
Pełczyński space is isomorphic to the Lipschitz free space over a compact set
2019
International audience
All congruences below stability-preserving fair testing or CFFD
2020
AbstractIn process algebras, a congruence is an equivalence that remains valid when any subsystem is replaced by an equivalent one. Whether or not an equivalence is a congruence depends on the set of operators used in building systems from subsystems. Numerous congruences have been found, differing from each other in fine details, major ideas, or both, and none of them is good for all situations. The world of congruences seems thus chaotic, which is unpleasant, because the notion of congruence is at the heart of process algebras. This study continues attempts to clarify the big picture by proving that in certain sub-areas, there are no other congruences than those that are already known or …
Congruence-based proofs of the recognizability theorems for free many-sorted algebras
2020
Abstract We generalize several recognizability theorems for free single-sorted algebras to free many-sorted algebras and provide, in a uniform way and without using either regular tree grammars or tree automata, purely algebraic proofs of them based on congruences.
Sobolev Extension on Lp-quasidisks
2021
AbstractIn this paper, we study the Sobolev extension property of Lp-quasidisks which are the generalizations of classical quasidisks. After that, we also find some applications of this property.
On shortening u-cycles and u-words for permutations
2017
Abstract This paper initiates the study of shortening universal cycles (u-cycles) and universal words (u-words) for permutations either by using incomparable elements, or by using non-deterministic symbols. The latter approach is similar in nature to the recent relevant studies for the de Bruijn sequences. A particular result we obtain in this paper is that u-words for n -permutations exist of lengths n ! + ( 1 − k ) ( n − 1 ) for k = 0 , 1 , … , ( n − 2 ) ! .
Gray coding cubic planar maps
2016
International audience; The idea of (combinatorial) Gray codes is to list objects in question in such a way that two successive objects differ in some pre-specified small way. In this paper, we utilize beta-description trees to cyclicly Gray code three classes of cubic planar maps, namely, bicubic planar maps, 3-connected cubic planar maps, and cubic non-separable planar maps. (C) 2015 Elsevier B.V. All rights reserved.
Quadratically Tight Relations for Randomized Query Complexity
2020
In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R0(f): C(f) ≤R0(f) ≤C(f)2. In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R0(f): EC(f) ≤R0(f) = O(EC(f)2). For R(f), we prove that EC2/3 ≤R(f). We then prove that EC(f) ≤C(f) ≤EC(f)2 and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R0(f). The measure is also related to the fractional…
Distributed construction of quantum fingerprints
2003
Quantum fingerprints are useful quantum encodings introduced by Buhrman, Cleve, Watrous, and de Wolf (Physical Review Letters, Volume 87, Number 16, Article 167902, 2001; quant-ph/0102001) in obtaining an efficient quantum communication protocol. We design a protocol for constructing the fingerprint in a distributed scenario. As an application, this protocol gives rise to a communication protocol more efficient than the best known classical protocol for a communication problem.
Recent Developments in Quantum Algorithms and Complexity
2014
We survey several recent developments in quantum algorithms and complexity: Reichardt’s characterization of quantum query algorithms via span programs [15]; New bounds on the number of queries that are necessary for simulating a quantum algorithm that makes a very small number of queries [2]; Exact quantum algorithms with superlinear advantage over the best classical algorithm [4].