An important family of quantum codes is the quantum maximum-distance-separable (MDS) codes. In this paper, we construct some new classes of quantum MDS codes by generalized Reed-Solomon (GRS) codes and Hermitian construction. In addition, the length $n$ of most of the quantum MDS codes we constructed satisfies $n\equiv 0,1($mod$\,\frac{q\pm1}{2})$, which is different from previously known code lengths. At the same time, the quantum MDS codes we construct have large minimum distances that are greater than $q/2+1$.
相關內容
We give a poly-time algorithm for the $k$-edge-connected spanning subgraph ($k$-ECSS) problem that returns a solution of cost no greater than the cheapest $(k+10)$-ECSS on the same graph. Our approach enhances the iterative relaxation framework with a new ingredient, which we call ghost values, that allows for high sparsity in intermediate problems. Our guarantees improve upon the best-known approximation factor of $2$ for $k$-ECSS whenever the optimal value of $(k+10)$-ECSS is close to that of $k$-ECSS. This is a property that holds for the closely related problem $k$-edge-connected spanning multi-subgraph ($k$-ECSM), which is identical to $k$-ECSS except edges can be selected multiple times at the same cost. As a consequence, we obtain a $\left(1+O\left(\frac{1}{k}\right)\right)$-approximation algorithm for $k$-ECSM, which resolves a conjecture of Pritchard and improves upon a recent $\left(1+O\left(\frac{1}{\sqrt{k}}\right)\right)$-approximation algorithm of Karlin, Klein, Oveis Gharan, and Zhang. Moreover, we present a matching lower bound for $k$-ECSM, showing that our approximation ratio is tight up to the constant factor in $O\left(\frac{1}{k}\right)$, unless $P=NP$.
Because $\Sigma^p_2$- and $\Sigma^p_3$-hardness proofs are usually tedious and difficult, not so many complete problems for these classes are known. This is especially true in the areas of min-max regret robust optimization, network interdiction, most vital vertex problems, blocker problems, and two-stage adjustable robust optimization problems. Even though these areas are well-researched for over two decades and one would naturally expect many (if not most) of the problems occurring in these areas to be complete for the above classes, almost no completeness results exist in the literature. We address this lack of knowledge by introducing over 70 new $\Sigma^p_2$-complete and $\Sigma^p_3$-complete problems. We achieve this result by proving a new meta-theorem, which shows $\Sigma^p_2$- and $\Sigma^p_3$-completeness simultaneously for a huge class of problems. The majority of all earlier publications on $\Sigma^p_2$- and $\Sigma^p_3$-completeness in said areas are special cases of our meta-theorem. Our precise result is the following: We introduce a large list of problems for which the meta-theorem is applicable (including clique, vertex cover, knapsack, TSP, facility location and many more). For every problem on this list, we show: The interdiction/minimum cost blocker/most vital nodes problem (with element costs) is $\Sigma^p_2$-complete. The min-max-regret problem with interval uncertainty is $\Sigma^p_2$-complete. The two-stage adjustable robust optimization problem with discrete budgeted uncertainty is $\Sigma^p_3$-complete. In summary, our work reveals the interesting insight that a large amount of NP-complete problems have the property that their min-max versions are 'automatically' $\Sigma^p_2$-complete.
How to achieve the tradeoff between privacy and utility is one of fundamental problems in private data analysis.In this paper, we give a rigourous differential privacy analysis of networks in the appearance of covariates via a generalized $\beta$-model, which has an $n$-dimensional degree parameter $\beta$ and a $p$-dimensional homophily parameter $\gamma$.Under $(k_n, \epsilon_n)$-edge differential privacy, we use the popular Laplace mechanism to release the network statistics.The method of moments is used to estimate the unknown model parameters. We establish the conditions guaranteeing consistency of the differentially private estimators $\widehat{\beta}$ and $\widehat{\gamma}$ as the number of nodes $n$ goes to infinity, which reveal an interesting tradeoff between a privacy parameter and model parameters. The consistency is shown by applying a two-stage Newton's method to obtain the upper bound of the error between $(\widehat{\beta},\widehat{\gamma})$ and its true value $(\beta, \gamma)$ in terms of the $\ell_\infty$ distance, which has a convergence rate of rough order $1/n^{1/2}$ for $\widehat{\beta}$ and $1/n$ for $\widehat{\gamma}$, respectively. Further, we derive the asymptotic normalities of $\widehat{\beta}$ and $\widehat{\gamma}$, whose asymptotic variances are the same as those of the non-private estimators under some conditions. Our paper sheds light on how to explore asymptotic theory under differential privacy in a principled manner; these principled methods should be applicable to a class of network models with covariates beyond the generalized $\beta$-model. Numerical studies and a real data analysis demonstrate our theoretical findings.
In this study, we consider the numerical solution of the Neumann initial boundary value problem for the wave equation in 2D domains. Employing the Laguerre transform with respect to the temporal variable, we effectively transform this problem into a series of Neumann elliptic problems. The development of a fundamental sequence for these elliptic equations provides us with the means to introduce modified double layer potentials. Consequently, we are able to derive a sequence of boundary hypersingular integral equations as a result of this transformation. To discretize the system of equations, we apply the Maue transform and implement the Nystr\"om method with trigonometric quadrature techniques. To demonstrate the practical utility of our approach, we provide numerical examples.
Asynchronous Byzantine Atomic Broadcast (ABAB) promises simplicity in implementation as well as increased performance and robustness in comparison to partially synchronous approaches. We adapt the recently proposed DAG-Rider approach to achieve ABAB with $n\geq 2f+1$ processes, of which $f$ are faulty, with only a constant increase in message size. We leverage a small Trusted Execution Environment (TEE) that provides a unique sequential identifier generator (USIG) to implement Reliable Broadcast with $n>f$ processes and show that the quorum-critical proofs still hold when adapting the quorum size to $\lfloor \frac{n}{2} \rfloor + 1$. This first USIG-based ABAB preserves the simplicity of DAG-Rider and serves as starting point for further research on TEE-based ABAB.
We study the high-order local discontinuous Galerkin (LDG) method for the $p$-Laplace equation. We reformulate our spatial discretization as an equivalent convex minimization problem and use a preconditioned gradient descent method as the nonlinear solver. For the first time, a weighted preconditioner that provides $hk$-independent convergence is applied in the LDG setting. For polynomial order $k \geqslant 1$, we rigorously establish the solvability of our scheme and provide a priori error estimates in a mesh-dependent energy norm. Our error estimates are under a different and non-equivalent distance from existing LDG results. For arbitrarily high-order polynomials under the assumption that the exact solution has enough regularity, the error estimates demonstrate the potential for high-order accuracy. Our numerical results exhibit the desired convergence speed facilitated by the preconditioner, and we observe best convergence rates in gradient variables in alignment with linear LDG, and optimal rates in the primal variable when $1 < p \leqslant 2$.
In this paper we introduce a multilevel Picard approximation algorithm for general semilinear parabolic PDEs with gradient-dependent nonlinearities whose coefficient functions do not need to be constant. We also provide a full convergence and complexity analysis of our algorithm. To obtain our main results, we consider a particular stochastic fixed-point equation (SFPE) motivated by the Feynman-Kac representation and the Bismut-Elworthy-Li formula. We show that the PDE under consideration has a unique viscosity solution which coincides with the first component of the unique solution of the stochastic fixed-point equation. Moreover, the gradient of the unique viscosity solution of the PDE exists and coincides with the second component of the unique solution of the stochastic fixed-point equation.
In arXiv:1811.04313, a definition of determinant is formalized in the bounded arithmetic $VNC^{2}$. Following the presentation of [Gathen, 1993], we can formalize a definition of matrix rank in the same bounded arithmetic. In this article, we define a bounded arithmetic $LAPPD$, and show that $LAPPD$ seems to be a natural arithmetic theory formalizing the treatment of rank function following Mulmuley's algorithm. Furthermore, we give a formalization of rank in $VNC^{2}$ by interpreting $LAPPD$ by $VNC^{2}$.
Big data is ubiquitous in practices, and it has also led to heavy computation burden. To reduce the calculation cost and ensure the effectiveness of parameter estimators, an optimal subset sampling method is proposed to estimate the parameters in marginal models with massive longitudinal data. The optimal subsampling probabilities are derived, and the corresponding asymptotic properties are established to ensure the consistency and asymptotic normality of the estimator. Extensive simulation studies are carried out to evaluate the performance of the proposed method for continuous, binary and count data and with four different working correlation matrices. A depression data is used to illustrate the proposed method.
This paper develops a general asymptotic theory of local polynomial (LP) regression for spatial data observed at irregularly spaced locations in a sampling region $R_n \subset \mathbb{R}^d$. We adopt a stochastic sampling design that can generate irregularly spaced sampling sites in a flexible manner including both pure increasing and mixed increasing domain frameworks. We first introduce a nonparametric regression model for spatial data defined on $\mathbb{R}^d$ and then establish the asymptotic normality of LP estimators with general order $p \geq 1$. We also propose methods for constructing confidence intervals and establishing uniform convergence rates of LP estimators. Our dependence structure conditions on the underlying processes cover a wide class of random fields such as L\'evy-driven continuous autoregressive moving average random fields. As an application of our main results, we discuss a two-sample testing problem for mean functions and their partial derivatives.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191