Two Latin squares of order $n$ are $r$-orthogonal if, when superimposed, there are exactly $r$ distinct ordered pairs. The spectrum of all values of $r$ for Latin squares of order $n$ is known. A Latin square $A$ of order $n$ is $r$-self-orthogonal if $A$ and its transpose are $r$-orthogonal. The spectrum of all values of $r$ is known for all orders $n\ne 14$. We develop randomized algorithms for computing pairs of $r$-orthogonal Latin squares of order $n$ and algorithms for computing $r$-self-orthogonal Latin squares of order $n$.
相關內容
We explore new interactions between finite model theory and a number of classical streams of universal algebra and semigroup theory. A key result is an example of a finite algebra whose variety is not finitely axiomatisable in first order logic, but which has first order definable finite membership problem. This algebra witnesses the simultaneous failure of the {\L}os-Tarski Theorem, the SP-preservation theorem and Birkhoff's HSP-preservation theorem at the finite level as well as providing a negative solution to a first order formulation of the long-standing Eilenberg Sch\"utzenberger problem. The example also shows that a pseudovariety without any finite pseudo-identity basis may be finitely axiomatisable in first order logic. Other results include the undecidability of deciding first order definability of the pseudovariety of a finite algebra and a mapping from any fixed template constraint satisfaction problem to a first order equivalent variety membership problem, thereby providing examples of variety membership problems complete in each of the classes $\texttt{L}$, $\texttt{NL}$, $\texttt{Mod}_p(\texttt{L})$, $\texttt{P}$, and infinitely many others (depending on complexity-theoretic assumptions).
We consider the gradient descent flow widely used for the minimization of the $\mathcal{L}^2$ cost function in Deep Learning networks, and introduce two modified versions; one adapted for the overparametrized setting, and the other for the underparametrized setting. Both have a clear and natural invariant geometric meaning, taking into account the pullback vector bundle structure in the overparametrized, and the pushforward vector bundle structure in the underparametrized setting. In the overparametrized case, we prove that, provided that a rank condition holds, all orbits of the modified gradient descent drive the $\mathcal{L}^2$ cost to its global minimum at a uniform exponential convergence rate; one thereby obtains an a priori stopping time for any prescribed proximity to the global minimum. We point out relations of the latter to sub-Riemannian geometry.
We continue to investigate the $k$ nearest neighbour learning rule in separable metric spaces. Thanks to the results of C\'erou and Guyader (2006) and Preiss (1983), this rule is known to be universally consistent in every metric space $X$ that is sigma-finite dimensional in the sense of Nagata. Here we show that the rule is strongly universally consistent in such spaces in the absence of ties. Under the tie-breaking strategy applied by Devroye, Gy\"{o}rfi, Krzy\.{z}ak, and Lugosi (1994) in the Euclidean setting, we manage to show the strong universal consistency in non-Archimedian metric spaces (that is, those of Nagata dimension zero). Combining the theorem of C\'erou and Guyader with results of Assouad and Quentin de Gromard (2006), one deduces that the $k$-NN rule is universally consistent in metric spaces having finite dimension in the sense of de Groot. In particular, the $k$-NN rule is universally consistent in the Heisenberg group which is not sigma-finite dimensional in the sense of Nagata as follows from an example independently constructed by Kor\'anyi and Reimann (1995) and Sawyer and Wheeden (1992).
For a matrix $A$ which satisfies Crouzeix's conjecture, we construct several classes of matrices from $A$ for which the conjecture will also hold. We discover a new link between cyclicity and Crouzeix's conjecture, which shows that Crouzeix's Conjecture holds in full generality if and only if it holds for the differentiation operator on a class of analytic functions. We pose several open questions, which if proved, will prove Crouzeix's conjecture. We also begin an investigation into Crouzeix's conjecture for symmetric matrices and in the case of $3 \times 3$ matrices, we show Crouzeix's conjecture holds for symmetric matrices if and only if it holds for analytic truncated Toeplitz operators.
The minimum set cover (MSC) problem admits two classic algorithms: a greedy $\ln n$-approximation and a primal-dual $f$-approximation, where $n$ is the universe size and $f$ is the maximum frequency of an element. Both algorithms are simple and efficient, and remarkably -- one cannot improve these approximations under hardness results by more than a factor of $(1+\epsilon)$, for any constant $\epsilon > 0$. In their pioneering work, Gupta et al. [STOC'17] showed that the greedy algorithm can be dynamized to achieve $O(\log n)$-approximation with update time $O(f \log n)$. Building on this result, Hjuler et al. [STACS'18] dynamized the greedy minimum dominating set (MDS) algorithm, achieving a similar approximation with update time $O(\Delta \log n)$ (the analog of $O(f \log n)$), albeit for unweighted instances. The approximations of both algorithms, which are the state-of-the-art, exceed the static $\ln n$-approximation by a rather large constant factor. In sharp contrast, the current best dynamic primal-dual MSC algorithms achieve fast update times together with an approximation that exceeds the static $f$-approximation by a factor of (at most) $1+\epsilon$, for any $\epsilon > 0$. This paper aims to bridge the gap between the best approximation factor of the dynamic greedy MSC and MDS algorithms and the static $\ln n$ bound. We present dynamic algorithms for weighted greedy MSC and MDS with approximation $(1+\epsilon)\ln n$ for any $\epsilon > 0$, while achieving the same update time (ignoring dependencies on $\epsilon$) of the best previous algorithms (with approximation significantly larger than $\ln n$). Moreover, [...]
We incorporate strong negation in the theory of computable functionals TCF, a common extension of Plotkin's PCF and G\"{o}del's system $\mathbf{T}$, by defining simultaneously strong negation $A^{\mathbf{N}}$ of a formula $A$ and strong negation $P^{\mathbf{N}}$ of a predicate $P$ in TCF. As a special case of the latter, we get strong negation of an inductive and a coinductive predicate of TCF. We prove appropriate versions of the Ex falso quodlibet and of double negation elimination for strong negation in TCF. We introduce the so-called tight formulas of TCF i.e., formulas implied from the weak negation of their strong negation, and the relative tight formulas. We present various case-studies and examples, which reveal the naturality of our definition of strong negation in TCF and justify the use of TCF as a formal system for a large part of Bishop-style constructive mathematics.
Permutation polynomials with few terms (especially permutation binomials) attract many people due to their simple algebraic structure. Despite the great interests in the study of permutation binomials, a complete characterization of permutation binomials is still unknown. In this paper, we give a classification of permutation binomials of the form $x^i+ax$ over $\mathbb{F}_{2^n}$, where $n\leq 8$ by characterizing three new classes of permutation binomials. In particular one of them has relatively large index $\frac{q^2+q+1}{3}$ over $\mathbb{F}_{q^3}$.
Fractional calculus with respect to function $\psi$, also named as $\psi$-fractional calculus, generalizes the Hadamard and the Riemann-Liouville fractional calculi, which causes challenge in numerical treatment. In this paper we study spectral-type methods using mapped Jacobi functions (MJFs) as basis functions and obtain efficient algorithms to solve $\psi$-fractional differential equations. In particular, we setup the Petrov-Galerkin spectral method and spectral collocation method for initial and boundary value problems involving $\psi$-fractional derivatives. We develop basic approximation theory for the MJFs and conduct the error estimates of the derived methods. We also establish a recurrence relation to evaluate the collocation differentiation matrix for implementing the spectral collocation algorithm. Numerical examples confirm the theoretical results and demonstrate the effectiveness of the spectral and collocation methods.
Fitting's Heyting-valued modal logic and Heyting-valued logic have previously been examined from an algebraic perspective. Topological duality theorems have been developed in addition to algebraic axiomatizations with the completeness of Fitting's logic and modal logic. Recently, bitopological techniques have been used to study duality for Heyting-valued logic. But the development of duality for Heyting-valued modal logic noticeably lacks bitopology and biVietoris-coalgebra techniques. We are trying to bridge this gap in this paper. We establish a bitopological duality for algebras of Fitting's Heyting-valued modal logic. We build a bi-Vietoris functor on the category of Heyting-valued pairwise Boolean spaces, denoted by $PBS_{\mathcal{L}}$. In the end, we derive a dual equivalence between algebras of Fitting's Heyting-valued modal logic and categories of bi-Vietoris coalgebras. We thus conclude that, with respect to the coalgebras of a bi-Vietoris functor, Fitting's many-valued modal logic is sound and complete.
Permissive-Nominal Logic (PNL) extends first-order predicate logic with term-formers that can bind names in their arguments. It takes a semantics in (permissive-)nominal sets. In PNL, the forall-quantifier or lambda-binder are just term-formers satisfying axioms, and their denotation is functions on nominal atoms-abstraction. Then we have higher-order logic (HOL) and its models in ordinary (i.e. Zermelo-Fraenkel) sets; the denotation of forall or lambda is functions on full or partial function spaces. This raises the following question: how are these two models of binding connected? What translation is possible between PNL and HOL, and between nominal sets and functions? We exhibit a translation of PNL into HOL, and from models of PNL to certain models of HOL. It is natural, but also partial: we translate a restricted subsystem of full PNL to HOL. The extra part which does not translate is the symmetry properties of nominal sets with respect to permutations. To use a little nominal jargon: we can translate names and binding, but not their nominal equivariance properties. This seems reasonable since HOL -- and ordinary sets -- are not equivariant. Thus viewed through this translation, PNL and HOL and their models do different things, but they enjoy non-trivial and rich subsystems which are isomorphic.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191