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 present a $p$-adic algorithm to recover the lexicographic Gr\"obner basis $\mathcal G$ of an ideal in $\mathbb Q[x,y]$ with a generating set in $\mathbb Z[x,y]$, with a complexity that is less than cubic in terms of the dimension of $\mathbb Q[x,y]/\langle \mathcal G \rangle$ and softly linear in the height of its coefficients. We observe that previous results of Lazard's that use Hermite normal forms to compute Gr\"obner bases for ideals with two generators can be generalized to a set of $t\in \mathbb N^+$ generators. We use this result to obtain a bound on the height of the coefficients of $\mathcal G$, and to control the probability of choosing a \textit{good} prime $p$ to build the $p$-adic expansion of $\mathcal G$.
We consider the problem of approximating a function from $L^2$ by an element of a given $m$-dimensional space $V_m$, associated with some feature map $\varphi$, using evaluations of the function at random points $x_1,\dots,x_n$. After recalling some results on optimal weighted least-squares using independent and identically distributed points, we consider weighted least-squares using projection determinantal point processes (DPP) or volume sampling. These distributions introduce dependence between the points that promotes diversity in the selected features $\varphi(x_i)$. We first provide a generalized version of volume-rescaled sampling yielding quasi-optimality results in expectation with a number of samples $n = O(m\log(m))$, that means that the expected $L^2$ error is bounded by a constant times the best approximation error in $L^2$. Also, further assuming that the function is in some normed vector space $H$ continuously embedded in $L^2$, we further prove that the approximation is almost surely bounded by the best approximation error measured in the $H$-norm. This includes the cases of functions from $L^\infty$ or reproducing kernel Hilbert spaces. Finally, we present an alternative strategy consisting in using independent repetitions of projection DPP (or volume sampling), yielding similar error bounds as with i.i.d. or volume sampling, but in practice with a much lower number of samples. Numerical experiments illustrate the performance of the different strategies.
We propose two approaches, based on Riemannian optimization, for computing a stochastic approximation of the $p$th root of a stochastic matrix $A$. In the first approach, the approximation is found in the Riemannian manifold of positive stochastic matrices. In the second approach, we introduce the Riemannian manifold of positive stochastic matrices sharing with $A$ the Perron eigenvector and we compute the approximation of the $p$th root of $A$ in such a manifold. This way, differently from the available methods based on constrained optimization, $A$ and its $p$th root approximation share the Perron eigenvector. Such a property is relevant, from a modelling point of view, in the embedding problem for Markov chains. The extended numerical experimentation shows that, in the first approach, the Riemannian optimization methods are generally faster and more accurate than the available methods based on constrained optimization. In the second approach, even though the stochastic approximation of the $p$th root is found in a smaller set, the approximation is generally more accurate than the one obtained by standard constrained optimization.
Combinatorial designs are closely related to linear codes. In recent year, there are a lot of $t$-designs constructed from certain linear codes. In this paper, we aim to construct $2$-designs from binary three-weight codes. For any binary three-weight code $\mathcal{C}$ with length $n$, let $A_{n}(\mathcal{C})$ be the number of codewords in $\mathcal{C}$ with Hamming weight $n$, then we show that $\mathcal{C}$ holds $2$-designs when $\mathcal{C}$ is projective and $A_{n}(\mathcal{C})=1$. Furthermore, by extending some certain binary projective two-weight codes and basing on the defining set method, we construct two classes of binary projective three-weight codes which are suitable for holding $2$-designs.
Online RL in Linearly $q^π$-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore
We consider online reinforcement learning (RL) in episodic Markov decision processes (MDPs) under the linear $q^\pi$-realizability assumption, where it is assumed that the action-values of all policies can be expressed as linear functions of state-action features. This class is known to be more general than linear MDPs, where the transition kernel and the reward function are assumed to be linear functions of the feature vectors. As our first contribution, we show that the difference between the two classes is the presence of states in linearly $q^\pi$-realizable MDPs where for any policy, all the actions have approximately equal values, and skipping over these states by following an arbitrarily fixed policy in those states transforms the problem to a linear MDP. Based on this observation, we derive a novel (computationally inefficient) learning algorithm for linearly $q^\pi$-realizable MDPs that simultaneously learns what states should be skipped over and runs another learning algorithm on the linear MDP hidden in the problem. The method returns an $\epsilon$-optimal policy after $\text{polylog}(H, d)/\epsilon^2$ interactions with the MDP, where $H$ is the time horizon and $d$ is the dimension of the feature vectors, giving the first polynomial-sample-complexity online RL algorithm for this setting. The results are proved for the misspecified case, where the sample complexity is shown to degrade gracefully with the misspecification error.
In the semi-streaming model for processing massive graphs, an algorithm makes multiple passes over the edges of a given $n$-vertex graph and is tasked with computing the solution to a problem using $O(n \cdot \text{polylog}(n))$ space. Semi-streaming algorithms for Maximal Independent Set (MIS) that run in $O(\log\log{n})$ passes have been known for almost a decade, however, the best lower bounds can only rule out single-pass algorithms. We close this large gap by proving that the current algorithms are optimal: Any semi-streaming algorithm for finding an MIS with constant probability of success requires $\Omega(\log\log{n})$ passes. This settles the complexity of this fundamental problem in the semi-streaming model, and constitutes one of the first optimal multi-pass lower bounds in this model. We establish our result by proving an optimal round vs communication tradeoff for the (multi-party) communication complexity of MIS. The key ingredient of this result is a new technique, called hierarchical embedding, for performing round elimination: we show how to pack many but small hard $(r-1)$-round instances of the problem into a single $r$-round instance, in a way that enforces any $r$-round protocol to effectively solve all these $(r-1)$-round instances also. These embeddings are obtained via a novel application of results from extremal graph theory -- in particular dense graphs with many disjoint unique shortest paths -- together with a newly designed graph product, and are analyzed via information-theoretic tools such as direct-sum and message compression arguments.
A linearly ordered (LO) $k$-colouring of a hypergraph is a colouring of its vertices with colours $1, \dots, k$ such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO $k$-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the `linearly ordered chromatic number' of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO $3$-colourable, and the case that it is not even LO $4$-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opr\v{s}al, Wrochna, and \v{Z}ivn\'y (2023).
A novel H3N3-2$_\sigma$ interpolation approximation for the Caputo fractional derivative of order $\alpha\in(1,2)$ is derived in this paper, which improves the popular L2C formula with (3-$\alpha$)-order accuracy. By an interpolation technique, the second-order accuracy of the truncation error is skillfully estimated. Based on this formula, a finite difference scheme with second-order accuracy both in time and in space is constructed for the initial-boundary value problem of the time fractional hyperbolic equation. It is well known that the coefficient properties of discrete fractional derivatives are fundamental to the numerical stability of time fractional differential models. We prove the related properties of the coefficients of the H3N3-2$_\sigma$ approximate formula. With these properties, the numerical stability and convergence of the difference scheme is derived immediately by the energy method in the sense of $H^1$-norm. Considering the weak regularity of the solution to the problem at the starting time, a finite difference scheme on the graded meshes based on H3N3-2$_\sigma$ formula is also presented. The numerical simulations are performed to show the effectiveness of the derived finite difference schemes, in which the fast algorithms are employed to speed up the numerical computation.
Consider a set $V$ of voters, represented by a multiset in a metric space $(X,d)$. The voters have to reach a decision -- a point in $X$. A choice $p\in X$ is called a $\beta$-plurality point for $V$, if for any other choice $q\in X$ it holds that $|\{v\in V\mid \beta\cdot d(p,v)\le d(q,v)\}|\ge\frac{|V|}{2}$. In other words, at least half of the voters ``prefer'' $p$ over $q$, when an extra factor of $\beta$ is taken in favor of $p$. For $\beta=1$, this is equivalent to Condorcet winner, which rarely exists. The concept of $\beta$-plurality was suggested by Aronov, de Berg, Gudmundsson, and Horton [TALG 2021] as a relaxation of the Condorcet criterion. Let $\beta^*_{(X,d)}=\sup\{\beta\mid \mbox{every finite multiset $V$ in $X$ admits a $\beta$-plurality point}\}$. The parameter $\beta^*$ determines the amount of relaxation required in order to reach a stable decision. Aronov et al. showed that for the Euclidean plane $\beta^*_{(\mathbb{R}^2,\|\cdot\|_2)}=\frac{\sqrt{3}}{2}$, and more generally, for $d$-dimensional Euclidean space, $\frac{1}{\sqrt{d}}\le \beta^*_{(\mathbb{R}^d,\|\cdot\|_2)}\le\frac{\sqrt{3}}{2}$. In this paper, we show that $0.557\le \beta^*_{(\mathbb{R}^d,\|\cdot\|_2)}$ for any dimension $d$ (notice that $\frac{1}{\sqrt{d}}<0.557$ for any $d\ge 4$). In addition, we prove that for every metric space $(X,d)$ it holds that $\sqrt{2}-1\le\beta^*_{(X,d)}$, and show that there exists a metric space for which $\beta^*_{(X,d)}\le \frac12$.
Given a Binary Decision Diagram $B$ of a Boolean function $\varphi$ in $n$ variables, it is well known that all $\varphi$-models can be enumerated in output polynomial time, and in a compressed way (using don't-care symbols). We show that all $N$ many $\varphi$-models of fixed Hamming-weight $k$ can be enumerated as well in time polynomial in $n$ and $|B|$ and $N$. Furthermore, using novel wildcards, again enables a compressed enumeration of these models.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191