For an odd prime $p$, we say $f(X) \in {\mathbb F}_p[X]$ computes square roots in $\mathbb F_p$ if, for all nonzero perfect squares $a \in \mathbb F_p$, we have $f(a)^2 = a$. When $p \equiv 3 \mod 4$, it is well known that $f(X) = X^{(p+1)/4}$ computes square roots. This degree is surprisingly low (and in fact lowest possible), since we have specified $(p-1)/2$ evaluations (up to sign) of the polynomial $f(X)$. On the other hand, for $p \equiv 1 \mod 4$ there was previously no nontrivial bound known on the lowest degree of a polynomial computing square roots in $\mathbb F_p$; it could have been anywhere between $\frac{p}{4}$ and $\frac{p}{2}$. We show that for all $p \equiv 1 \mod 4$, the degree of a polynomial computing square roots has degree at least $p/3$. Our main new ingredient is a general lemma which may be of independent interest: powers of a low degree polynomial cannot have too many consecutive zero coefficients. The proof method also yields a robust version: any polynomial that computes square roots for 99\% of the squares also has degree almost $p/3$. In the other direction, we also show that for infinitely many $p \equiv 1 \mod 4$, the degree of a polynomial computing square roots can be $(\frac{1}{2} - \Omega(1))p$.
相關內容
We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph $G=(V,E)$ with edge weights $w:E \rightarrow \mathbb{R}$, two terminals $s$ and $t$ in $G$, find two internally vertex-disjoint paths between $s$ and $t$ with minimum total weight. As shown recently by Schlotter and Seb\H{o} (2022), this problem becomes NP-hard if edges can have negative weights, even if the weight function is conservative, there are no cycles in $G$ with negative total weight. We propose a polynomial-time algorithm that solves the Shortest Two Disjoint Paths problem for conservative weights in the case when the negative-weight edges form a constant number of trees in $G$.
We classify the Boolean degree $1$ functions of $k$-spaces in a vector space of dimension $n$ (also known as Cameron-Liebler classes) over the field with $q$ elements for $n \geq n_0(k, q)$, a problem going back to a work by Cameron and Liebler from 1982. This also implies that two-intersecting sets with respect to $k$-spaces do not exist for $n \geq n_0(k, q)$. Our main ingredient is the Ramsey theory for geometric lattices.
We describe the classification of orthogonal arrays OA$(2048,14,2,7)$, or, equivalently, completely regular $\{14;2\}$-codes in the $14$-cube ($30848$ equivalence classes). In particular, we find that there is exactly one almost-OA$(2048,14,2,7+1)$, up to equivalence. As derived objects, OA$(1024,13,2,6)$ ($202917$ classes) and completely regular $\{12,2;2,12\}$- and $\{14,12,2;2,12,14\}$-codes in the $13$- and $14$-cubes, respectively, are also classified. Keywords: binary orthogonal array, completely regular code, binary 1-perfect code.
We prove a new simple and explicit bound on the total variation distance between a measure $\pi\propto e^{-nf}$ on $\mathbb R^d$ and its Laplace approximation. The bound is proportional to $d/\sqrt n$, which has recently been shown to be the tight rate in terms of dimension dependence. Our bound holds under weak regularity conditions on $f$ and at least linear growth of $f$ at infinity. We then apply this bound to prove the first ever Bernstein-von Mises (BvM) theorems on the asymptotic normality of posterior distributions in the regime $n\gg d^2$. This improves on the tightest previously known condition, $n\gg d^3$. We establish the BvM for the following data-generating models: 1) exponential families, 2) arbitrary probability mass functions on $d+1$ states, and 3) logistic regression with Gaussian design. Our statements of the BvM are nonasymptotic, taking the form of explicit high-probability bounds. We also show in a general setting that the prior can have a stronger regularizing effect than previously known while still vanishing in the large sample limit.
An infinite sequence of sets $\left\{B_{n}\right\}_{n\in\mathbb{N}}$ is said to be a heterochromatic sequence from an infinite sequence of families $\left\{ \mathcal{F}_{n} \right\}_{n \in \mathbb{N}}$, if there exists a strictly increasing sequence of natural numbers $\left\{ i_{n}\right\}_{n \in \mathbb{N}}$ such that for all $n \in \mathbb{N}$ we have $B_{n} \in \mathcal{F}_{i_{n}}$. In this paper, we have proved that if for each $n\in\mathbb{N}$, $\mathcal{F}_n$ is a family of {\em nicely shaped} convex sets in $\mathbb{R}^d$ such that each heterochromatic sequence $\left\{B_{n}\right\}_{n\in\mathbb{N}}$ from $\left\{ \mathcal{F}_{n} \right\}_{n \in \mathbb{N}}$ contains at least $k+2$ sets that can be pierced by a single $k$-flat ($k$-dimensional affine space) then all but finitely many families in $\left\{\mathcal{F}_{n}\right\}_{n\in \mathbb{N}}$ can be pierced by finitely many $k$-flats. This result can be considered as a {\em countably colorful} generalization of the $(\aleph_0, k+2)$-theorem proved by Keller and Perles (Symposium on Computational Geometry 2022). We have also established the tightness of our result by proving a number of no-go theorems.
We consider the problem of low-rank rectangular matrix completion in the regime where the matrix $M$ of size $n\times m$ is "long", i.e., the aspect ratio $m/n$ diverges to infinity. Such matrices are of particular interest in the study of tensor completion, where they arise from the unfolding of a low-rank tensor. In the case where the sampling probability is $\frac{d}{\sqrt{mn}}$, we propose a new spectral algorithm for recovering the singular values and left singular vectors of the original matrix $M$ based on a variant of the standard non-backtracking operator of a suitably defined bipartite weighted random graph, which we call a non-backtracking wedge operator. When $d$ is above a Kesten-Stigum-type sampling threshold, our algorithm recovers a correlated version of the singular value decomposition of $M$ with quantifiable error bounds. This is the first result in the regime of bounded $d$ for weak recovery and the first for weak consistency when $d\to\infty$ arbitrarily slowly without any polylog factors. As an application, for low-rank orthogonal $k$-tensor completion, we efficiently achieve weak recovery with sample size $O(n^{k/2})$, and weak consistency with sample size $\omega(n^{k/2})$.
We describe a new algorithm for vertex cover with runtime $O^*(1.25284^k)$, where $k$ is the size of the desired solution and $O^*$ hides polynomial factors in the input size. This improves over previous runtime of $O^*(1.2738^k)$ due to Chen, Kanj, & Xia (2010) standing for more than a decade. The key to our algorithm is to use a potential function which simultaneously tracks $k$ as well as the optimal value $\lambda$ of the vertex cover LP relaxation. This approach also allows us to make use of prior algorithms for Maximum Independent Set in bounded-degree graphs and Above-Guarantee Vertex Cover. The main step in the algorithm is to branch on high-degree vertices, while ensuring that both $k$ and $\mu = k - \lambda$ are decreased at each step. There can be local obstructions in the graph that prevent $\mu$ from decreasing in this process; we develop a number of novel branching steps to handle these situations.
Let $G$ be a graph of order $n$. A classical upper bound for the domination number of a graph $G$ having no isolated vertices is $\lfloor\frac{n}{2}\rfloor$. However, for several families of graphs, we have $\gamma(G) \le \lfloor\sqrt{n}\rfloor$ which gives a substantially improved upper bound. In this paper, we give a condition necessary for a graph $G$ to have $\gamma(G) \le \lfloor\sqrt{n}\rfloor$, and some conditions sufficient for a graph $G$ to have $\gamma(G) \le \lfloor\sqrt{n}\rfloor$. We also present a characterization of all connected graphs $G$ of order $n$ with $\gamma(G) = \lfloor\sqrt{n}\rfloor$. Further, we prove that for a graph $G$ not satisfying $rad(G)=diam(G)=rad(\overline{G})=diam(\overline{G})=2$, deciding whether $\gamma(G) \le \lfloor\sqrt{n}\rfloor$ or $\gamma(\overline{G}) \le \lfloor\sqrt{n}\rfloor$ can be done in polynomial time. We conjecture that this decision problem can be solved in polynomial time for any graph $G$.
We study least-squares trace regression when the parameter is the sum of a $r$-low-rank matrix and a $s$-sparse matrix and a fraction $\epsilon$ of the labels is corrupted. For subgaussian distributions and feature-dependent noise, we highlight three needed design properties, each one derived from a different process inequality: a "product process inequality", "Chevet's inequality" and a "multiplier process inequality". These properties handle, simultaneously, additive decomposition, label contamination and design-noise interaction. They imply the near-optimality of a tractable estimator with respect to the effective dimensions $d_{eff,r}$ and $d_{eff,s}$ of the low-rank and sparse components, $\epsilon$ and the failure probability $\delta$. The near-optimal rate is $\mathsf{r}(n,d_{eff,r}) + \mathsf{r}(n,d_{eff,s}) + \sqrt{(1+\log(1/\delta))/n} + \epsilon\log(1/\epsilon)$, where $\mathsf{r}(n,d_{eff,r})+\mathsf{r}(n,d_{eff,s})$ is the optimal rate in average with no contamination. Our estimator is adaptive to $(s,r,\epsilon,\delta)$ and, for fixed absolute constant $c>0$, it attains the mentioned rate with probability $1-\delta$ uniformly over all $\delta\ge\exp(-cn)$. Without matrix decomposition, our analysis also entails optimal bounds for a robust estimator adapted to the noise variance. Our estimators are based on "sorted" versions of Huber's loss. We present simulations matching the theory. In particular, it reveals the superiority of "sorted" Huber's losses over the classical Huber's loss.
For a commutative ring $R,$ with non-zero zero divisors $Z^{\ast}(R)$. The zero divisor graph $\Gamma(R)$ is a simple graph with vertex set $Z^{\ast}(R)$, and two distinct vertices $x,y\in V(\Gamma(R))$ are adjacent if and only if $x\cdot y=0.$ In this note, provide counter examples to the eigenvalues, the energy and the second Zagreb index related to zero divisor graphs of rings obtained in [Johnson and Sankar, J. Appl. Math. Comp. (2023), \cite{johnson}]. We correct the eigenvalues (energy) and the Zagreb index result for the zero divisor graphs of ring $\mathbb{Z}_{p}[x]/\langle x^{4} \rangle.$ We show that for any prime $p$, $\Gamma(\mathbb{Z}_{p}[x]/\langle x^{4} \rangle)$ is non-hyperenergetic and for prime $p\geq 3$, $\Gamma(\mathbb{Z}_{p}[x]/\langle x^{4} \rangle)$ is hypoenergetic. We give a formulae for the topological indices of $\Gamma(\mathbb{Z}_{p}[x]/\langle x^{4} \rangle)$ and show that its Zagreb indices satisfy Hansen and Vuki$\check{c}$cevi\'c conjecture \cite{hansen}.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191