For any positive integer $q\geq 2$ and any real number $\delta\in(0,1)$, let $\alpha_q(n,\delta n)$ denote the maximum size of a subset of $\mathbb{Z}_q^n$ with minimum Hamming distance at least $\delta n$, where $\mathbb{Z}_q=\{0,1,\dotsc,q-1\}$ and $n\in\mathbb{N}$. The asymptotic rate function is defined by $ R_q(\delta) = \limsup_{n\rightarrow\infty}\frac{1}{n}\log_q\alpha_q(n,\delta n). $ The famous $q$-ary asymptotic Gilbert-Varshamov bound, obtained in the 1950s, states that \[ R_q(\delta) \geq 1 - \delta\log_q(q-1)-\delta\log_q\frac{1}{\delta}-(1-\delta)\log_q\frac{1}{1-\delta} \stackrel{\mathrm{def}}{=}R_\mathrm{GV}(\delta,q) \] for all positive integers $q\geq 2$ and $0<\delta<1-q^{-1}$. In the case that $q$ is an even power of a prime with $q\geq 49$, the $q$-ary Gilbert-Varshamov bound was firstly improved by using algebraic geometry codes in the works of Tsfasman, Vladut, and Zink and of Ihara in the 1980s. The further investigation in algebraic geometry codes has shown that the $q$-ary Gilbert-Varshamov bound can also be improved in the case that $q$ is an odd power of a prime but not a prime with $q > 125$. However, it remains a long-standing open problem whether the $q$-ary Gilbert-Varshamov bound would be tight for those infinitely many integers $q$ which is a prime, except for Fermat primes not less than 257, and which is a generic positive integer not being a prime power. In this paper, we prove that the $q$-ary Gilbert-Varshamov bound can be improved for all but finitely many positive integers $q\geq 2$. It is shown that $ R_q(1/2) > R_\mathrm{GV}(1/2,q) $ for all integers $q > \exp(29)$. Furthermore, we show that the growth of the rate function $R_q(\delta)$ for $\delta\in(0,1)$ fixed and $q$ growing large has a nontrivial lower bound. These new lower bounds are achieved by using codes from geometry of numbers introduced by Lenstra in the 1980s.
相關內容
We prove that Sherali-Adams with polynomially bounded coefficients requires proofs of size $n^{\Omega(d)}$ to rule out the existence of an $n^{\Theta(1)}$-clique in Erd\H{o}s-R\'{e}nyi random graphs whose maximum clique is of size $d\leq 2\log n$. This lower bound is tight up to the multiplicative constant in the exponent. We obtain this result by introducing a technique inspired by pseudo-calibration which may be of independent interest. The technique involves defining a measure on monomials that precisely captures the contribution of a monomial to a refutation. This measure intuitively captures progress and should have further applications in proof complexity.
Every Boolean bent function $f$ can be written either as a concatenation $f=f_1||f_2$ of two complementary semi-bent functions $f_1,f_2$; or as a concatenation $f=f_1||f_2||f_3||f_4$ of four Boolean functions $f_1,f_2,f_3,f_4$, all of which are simultaneously bent, semi-bent, or 5-valued spectra-functions. In this context, it is essential to ask: When does a bent concatenation $f$ (not) belong to the completed Maiorana-McFarland class $\mathcal{M}^\#$? In this article, we answer this question completely by providing a full characterization of the structure of $\mathcal{M}$-subspaces for the concatenation of the form $f=f_1||f_2$ and $f=f_1||f_2||f_3||f_4$, which allows us to specify the necessary and sufficient conditions so that $f$ is outside $\mathcal{M}^\#$. Based on these conditions, we propose several explicit design methods of specifying bent functions outside $\mathcal{M}^\#$ in the special case when $f=g||h||g||(h+1)$, where $g$ and $h$ are bent functions.
We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node $u$ of degree $d(u)$ is assigned a palette of $d(u)+1$ colors, and the goal is to find a proper coloring using these color palettes. The (degree+1)-list coloring problem is a natural generalization of the classical $(\Delta+1)$-coloring and $(\Delta+1)$-list coloring problems, both being benchmark problems extensively studied in distributed and parallel computing. In this paper we settle the complexity of the (degree+1)-list coloring problem in the Congested Clique model by showing that it can be solved deterministically in a constant number of rounds.
The Cayley distance between two permutations $\pi, \sigma \in S_n$ is the minimum number of \textit{transpositions} required to obtain the permutation $\sigma$ from $\pi$. When we only allow adjacent transpositions, the minimum number of such transpositions to obtain $\sigma$ from $\pi$ is referred to the Kendall $\tau$-distance. A set $C$ of permutation words of length $n$ is called a $t$-Cayley permutation code if every pair of distinct permutations in $C$ has Cayley distance greater than $t$. A $t$-Kendall permutation code is defined similarly. Let $C(n,t)$ and $K(n,t)$ be the maximum size of a $t$-Cayley and a $t$-Kendall permutation code of length $n$, respectively. In this paper, we improve the Gilbert-Varshamov bound asymptotically by a factor $\log(n)$, namely \[ C(n,t) \geq \Omega_t\left(\frac{n!\log n}{n^{2t}}\right) \text{ and } K(n,t) \geq \Omega_t\left(\frac{n! \log n}{n^t}\right).\] Our proof is based on graph theory techniques.
Given functions $f$ and $g$ defined on the subset lattice of order $n$, their min-sum subset convolution, defined for all $S \subseteq [n]$ as \[ (f \star g)(S) = \min_{T \subseteq S}\:\big(f(T) + g(S \setminus T)\big), \] lies at the heart of several NP-hard optimization problems, such as minimum-cost $k$-coloring, the prize-collecting Steiner tree, and many others in computational biology. Despite its importance, its na\"ive $O(3^n)$-time evaluation remains the fastest known, the other alternative being an $\tilde O(2^n M)$-time algorithm for instances where the input functions have a bounded integer range $\{-M, \ldots, M\}$. We study for the first time the $(1 + \varepsilon)$-approximate min-sum subset convolution and present both a weakly- and strongly-polynomial approximation algorithm, running in time $\tilde O(2^n \log M / \varepsilon)$ and $\tilde O(2^\frac{3n}{2} / \sqrt{\varepsilon})$, respectively. To demonstrate the applicability of our work, we present the first exponential-time $(1 + \varepsilon)$-approximation schemes for the above optimization problems. Our algorithms lie at the intersection of two lines of research that have been so far considered separately: $\textit{sequence}$ and $\textit{subset}$ convolutions in semi-rings. We also extend the recent framework of Bringmann, K\"unnemann, and W\k{e}grzycki [STOC 2019] to the context of subset convolutions.
At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an $n^{O(d)}$-delay algorithm listing all minimal transversals of an $n$-vertex hypergraph of degeneracy $d$. Recently at IWOCA 2019, Conte, Kant\'e, Marino, and Uno asked whether this XP-delay algorithm parameterized by $d$ could be made FPT-delay for a weaker notion of degeneracy, or even parameterized by the maximum degree $\Delta$, i.e., whether it can be turned into an algorithm with delay $f(\Delta)\cdot n^{O(1)}$ for some computable function $f$. Moreover, and as a first step toward answering that question, they note that they could not achieve these time bounds even for the particular case of minimal dominating sets enumeration. In this paper, using ordered generation, we show that an FPT-delay algorithm can be devised for minimal transversals enumeration parameterized by the degeneracy and dimension, giving a positive and more general answer to the latter question.
Given a simple weighted directed graph $G = (V, E, \omega)$ on $n$ vertices as well as two designated terminals $s, t\in V$, our goal is to compute the shortest path from $s$ to $t$ avoiding any pair of presumably failed edges $f_1, f_2\in E$, which is a natural generalization of the classical replacement path problem which considers single edge failures only. This dual failure replacement paths problem was recently studied by Vassilevska Williams, Woldeghebriel and Xu [FOCS 2022] who designed a cubic time algorithm for general weighted digraphs which is conditionally optimal; in the same paper, for unweighted graphs where $\omega \equiv 1$, the authors presented an algebraic algorithm with runtime $\tilde{O}(n^{2.9146})$, as well as a conditional lower bound of $n^{8/3-o(1)}$ against combinatorial algorithms. However, it was unknown in their work whether fast matrix multiplication is necessary for a subcubic runtime in unweighted digraphs. As our primary result, we present the first truly subcubic combinatorial algorithm for dual failure replacement paths in unweighted digraphs. Our runtime is $\tilde{O}(n^{3-1/18})$. Besides, we also study algebraic algorithms for digraphs with small integer edge weights from $\{-M, -M+1, \cdots, M-1, M\}$. As our secondary result, we obtained a runtime of $\tilde{O}(Mn^{2.8716})$, which is faster than the previous bound of $\tilde{O}(M^{2/3}n^{2.9144} + Mn^{2.8716})$ from [Vassilevska Williams, Woldeghebriela and Xu, 2022].
We present an $O(1)$-round fully-scalable deterministic massively parallel algorithm for computing the min-plus matrix multiplication of unit-Monge matrices. We use this to derive a $O(\log n)$-round fully-scalable massively parallel algorithm for solving the exact longest increasing subsequence (LIS) problem. For a fully-scalable MPC regime, this result substantially improves the previously known algorithm of $O(\log^4 n)$-round complexity, and matches the best algorithm for computing the $(1+\epsilon)$-approximation of LIS.
Are asymptotic confidence sequences and anytime $p$-values uniformly valid for a nontrivial class of distributions $\mathcal{P}$? We give a positive answer to this question by deriving distribution-uniform anytime-valid inference procedures. Historically, anytime-valid methods -- including confidence sequences, anytime $p$-values, and sequential hypothesis tests that enable inference at stopping times -- have been justified nonasymptotically. Nevertheless, asymptotic procedures such as those based on the central limit theorem occupy an important part of statistical toolbox due to their simplicity, universality, and weak assumptions. While recent work has derived asymptotic analogues of anytime-valid methods with the aforementioned benefits, these were not shown to be $\mathcal{P}$-uniform, meaning that their asymptotics are not uniformly valid in a class of distributions $\mathcal{P}$. Indeed, the anytime-valid inference literature currently has no central limit theory to draw from that is both uniform in $\mathcal{P}$ and in the sample size $n$. This paper fills that gap by deriving a novel $\mathcal{P}$-uniform strong Gaussian approximation theorem. We apply some of these results to obtain an anytime-valid test of conditional independence without the Model-X assumption, as well as a $\mathcal{P}$-uniform law of the iterated logarithm.
We consider an observed subcritical Galton Watson process $\{Y_n,\ n\in \mathbb{Z} \}$ with correlated stationary immigration process $\{\epsilon_n,\ n\in \mathbb{Z} \}$. Two situations are presented. The first one is when $\mbox{Cov}(\epsilon_0,\epsilon_k)=0$ for $k$ larger than some $k_0$: a consistent estimator for the reproduction and mean immigration rates is given, and a central limit theorem is proved. The second one is when $\{\epsilon_n,\ n\in \mathbb{Z} \}$ has general correlation structure: under mixing assumptions, we exhibit an estimator for the the logarithm of the reproduction rate and we prove that it converges in quadratic mean with explicit speed. In addition, when the mixing coefficients decrease fast enough, we provide and prove a two terms expansion for the estimator. Numerical illustrations are provided.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191