Search for: All records

This paper presents a fully discrete numerical scheme for one-dimensional nonlocal wave equations and provides a rigorous theoretical analysis. To facilitate the spatial discretization, we introduce an auxiliary variable analogous to the gradient field in local discontinuous Galerkin (DG) methods for classical partial differential equations (PDEs) and reformulate the equation into a system of equations. The proposed scheme then uses a DG method for spatial discretization and the Crank-Nicolson method for time integration. We prove optimal L2 error convergence for both the solution and the auxiliary variable under a special class of radial kernels at the semi-discrete level. In addition, for general kernels, we demonstrate the asymptotic compatibility of the scheme, ensuring that it recovers the classical DG approximation of the local wave equation in the zero-horizon limit. Furthermore, we prove that the fully discrete scheme preserves the energy of the nonlocal wave equation. A series of numerical experiments are presented to validate the theoretical findings. 

The approximate discrete Radon transform (ADRT) is a hierarchical multiscale approximation of the Radon transform. In this paper, we factor the ADRT into a product of linear transforms that resemble convolutions and derive an explicit spectral decomposition of each factor. We further show that this implies—for data lying in the range of the ADRT—that the transform of an N x N image can be formally inverted with complexity O(N^2 log^2 N). We numerically test the accuracy of the inverse on images of moderate size and find that it is competitive with existing iterative algorithms in this special regime. 

Abstract The implicit boundary integral method (IBIM) provides a framework to construct quadrature rules on regular lattices for integrals over irregular domain boundaries. This work provides a systematic error analysis for IBIMs on uniform Cartesian grids for boundaries with different degrees of regularity. First, it is shown that the quadrature error gains an additional order of$$\frac{d-1}{2}$$ $\frac{d-1}{2}$ from the curvature for a strongly convex smooth boundary due to the “randomness” in the signed distances. This gain is discounted for degenerated convex surfaces. Then the extension of error estimate to general boundaries under some special circumstances is considered, including how quadrature error depends on the boundary’s local geometry relative to the underlying grid. Bounds on the variance of the quadrature error under random shifts and rotations of the lattices are also derived. 

Broadcast is a fundamental primitive that plays an important role in secure Multi-Party Computation (MPC) area. In this work, we revisit the broadcast with selective abort (hereafter, short for broadcast) proposed by Goldwasser and Lindell (DISC 2002; JoC 2005) and study the round complexity of broadcast under different setup assumptions. Our findings are summarized as follows: - We formally prove that 1-round broadcast is impossible under various widely-used setup assumptions (e.g., plain model, random oracle model, and common reference string model, etc.), even if we consider the static security and the stand-alone framework. More concretely, we formalize a notion called consistent oracle to capture these setups, and prove that our impossibility holds under the consistent oracle. Our impossibility holds in both honest majority setting and dishonest majority setting. - We show that 1-round broadcast protocol is possible in the Universal Composition (UC) framework, by assuming stateful trusted hardwares. Our protocol can be proven secure against all-but-one adaptive and malicious corruptions. We bypass our impossibility result since our stateful trusted hardwares do not satisfy the definition of consistent oracle. - We provide an application of 1-round broadcast: we construct the first 1-round multiple-verifier zero-knowledge (which is a special case of MPC) protocol, without assuming the broadcast hybrid world.