Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
We introduce a high-dimensional cubical complex, for any dimension t>0, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (case t=2), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively. We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codes $h_1,\ldots,h_t$ as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex. For t=4 our construction gives a new family of "almost-good" quantum LTCs -- with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex.
相關內容
We present and analyze a simple numerical method that diagonalizes a complex normal matrix A by diagonalizing the Hermitian matrix obtained from a random linear combination of the Hermitian and skew-Hermitian parts of A.
We provide a novel dimension-free uniform concentration bound for the empirical risk function of constrained logistic regression. Our bound yields a milder sufficient condition for a uniform law of large numbers than conditions derived by the Rademacher complexity argument and McDiarmid's inequality. The derivation is based on the PAC-Bayes approach with second-order expansion and Rademacher-complexity-based bounds for the residual term of the expansion.
We develop a monotone, two-scale discretization for a class of integrodifferential operators of order $2s$, $s \in (0,1)$. We apply it to develop numerical schemes, and convergence rates, for linear and obstacle problems governed by such operators. As applications of the monotonicity, we provide error estimates for free boundaries and a convergent numerical scheme for a concave fully nonlinear, nonlocal, problem.
For boundary value problem of an elliptic equation with variable coefficients describing the physical field distribution in inhomogeneous media, the Levi function can represent the solution in terms of volume and surface potentials, with the drawback that the volume potential involving in the solution expression requires heavy computational costs as well as the solvability of the integral equations with respect to the density pair. We introduce an modified integral expression for the solution to an elliptic equation in divergence form under the Levi function framework. The well-posedness of the linear integral system with respect to the density functions to be determined is rigorously proved. Based on the singularity decomposition for the Levi function, we propose two schemes to deal with the volume integrals so that the density functions can be solved efficiently. One method is an adaptive discretization scheme (ADS) for computing the integrals with continuous integrands, leading to the uniform accuracy of the integrals in the whole domain, and consequently the efficient computations for the density functions. The other method is the dual reciprocity method (DRM) which is a meshless approach converting the volume integrals into boundary integrals equivalently by expressing the volume density as the combination of the radial basis functions determined by the interior grids. The proposed schemes are justified numerically to be of satisfactory computation costs. Numerical examples in 2-dimensional and 3-dimensional cases are presented to show the validity of the proposed schemes.
This work is concerned with the construction and analysis of structure-preserving Galerkin methods for computing the dynamics of rotating Bose-Einstein condensate (BEC) based on the Gross-Pitaevskii equation with angular momentum rotation. Due to the presence of the rotation term, constructing finite element methods (FEMs) that preserve both mass and energy remains an unresolved issue, particularly in the context of nonconforming FEMs. Furthermore, in comparison to existing works, we provide a comprehensive convergence analysis, offering a thorough demonstration of the methods' optimal and high-order convergence properties. Finally, extensive numerical results are presented to check the theoretical analysis of the structure-preserving numerical method for rotating BEC, and the quantized vortex lattice's behavior is scrutinized through a series of numerical tests.
This paper focuses on the numerical scheme for delay-type stochastic McKean-Vlasov equations (DSMVEs) driven by fractional Brownian motion with Hurst parameter $H\in (0,1/2)\cup (1/2,1)$. The existence and uniqueness of the solutions to such DSMVEs whose drift coefficients contain polynomial delay terms are proved by exploting the Banach fixed point theorem. Then the propagation of chaos between interacting particle system and non-interacting system in $\mathcal{L}^p$ sense is shown. We find that even if the delay term satisfies the polynomial growth condition, the unmodified classical Euler-Maruyama scheme still can approximate the corresponding interacting particle system without the particle corruption. The convergence rates are revealed for $H\in (0,1/2)\cup (1/2,1)$. Finally, as an example that closely fits the original equation, a stochastic opinion dynamics model with both extrinsic memory and intrinsic memory is simulated to illustrate the plausibility of the theoretical result.
This paper proposes two innovative vector transport operators, leveraging the Cayley transform, for the generalized Stiefel manifold embedded with a non-standard metric. Specifically, it introduces the differentiated retraction and an approximation of the Cayley transform to the differentiated matrix exponential. These vector transports are demonstrated to satisfy the Ring-Wirth non-expansive condition under non-standard metrics, and one of them is also isometric. Building upon the novel vector transport operators, we extend the modified Polak-Ribi$\grave{e}$re-Polyak (PRP) conjugate gradient method to the generalized Stiefel manifold. Under a non-monotone line search condition, we prove our algorithm globally converges to a stationary point. The efficiency of the proposed vector transport operators is empirically validated through numerical experiments involving generalized eigenvalue problems and canonical correlation analysis.
We present BadGD, a unified theoretical framework that exposes the vulnerabilities of gradient descent algorithms through strategic backdoor attacks. Backdoor attacks involve embedding malicious triggers into a training dataset to disrupt the model's learning process. Our framework introduces three novel constructs: Max RiskWarp Trigger, Max GradWarp Trigger, and Max GradDistWarp Trigger, each designed to exploit specific aspects of gradient descent by distorting empirical risk, deterministic gradients, and stochastic gradients respectively. We rigorously define clean and backdoored datasets and provide mathematical formulations for assessing the distortions caused by these malicious backdoor triggers. By measuring the impact of these triggers on the model training procedure, our framework bridges existing empirical findings with theoretical insights, demonstrating how a malicious party can exploit gradient descent hyperparameters to maximize attack effectiveness. In particular, we show that these exploitations can significantly alter the loss landscape and gradient calculations, leading to compromised model integrity and performance. This research underscores the severe threats posed by such data-centric attacks and highlights the urgent need for robust defenses in machine learning. BadGD sets a new standard for understanding and mitigating adversarial manipulations, ensuring the reliability and security of AI systems.
We present a novel method for training score-based generative models which uses nonlinear noising dynamics to improve learning of structured distributions. Generalizing to a nonlinear drift allows for additional structure to be incorporated into the dynamics, thus making the training better adapted to the data, e.g., in the case of multimodality or (approximate) symmetries. Such structure can be obtained from the data by an inexpensive preprocessing step. The nonlinear dynamics introduces new challenges into training which we address in two ways: 1) we develop a new nonlinear denoising score matching (NDSM) method, 2) we introduce neural control variates in order to reduce the variance of the NDSM training objective. We demonstrate the effectiveness of this method on several examples: a) a collection of low-dimensional examples, motivated by clustering in latent space, b) high-dimensional images, addressing issues with mode collapse, small training sets, and approximate symmetries, the latter being a challenge for methods based on equivariant neural networks, which require exact symmetries.
This research conducts a thorough reevaluation of seismic fragility curves by utilizing ordinal regression models, moving away from the commonly used log-normal distribution function known for its simplicity. It explores the nuanced differences and interrelations among various ordinal regression approaches, including Cumulative, Sequential, and Adjacent Category models, alongside their enhanced versions that incorporate category-specific effects and variance heterogeneity. The study applies these methodologies to empirical bridge damage data from the 2008 Wenchuan earthquake, using both frequentist and Bayesian inference methods, and conducts model diagnostics using surrogate residuals. The analysis covers eleven models, from basic to those with heteroscedastic extensions and category-specific effects. Through rigorous leave-one-out cross-validation, the Sequential model with category-specific effects emerges as the most effective. The findings underscore a notable divergence in damage probability predictions between this model and conventional Cumulative probit models, advocating for a substantial transition towards more adaptable fragility curve modeling techniques that enhance the precision of seismic risk assessments. In conclusion, this research not only readdresses the challenge of fitting seismic fragility curves but also advances methodological standards and expands the scope of seismic fragility analysis. It advocates for ongoing innovation and critical reevaluation of conventional methods to advance the predictive accuracy and applicability of seismic fragility models within the performance-based earthquake engineering domain.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191