More Like this

1. Stability of structure-aware Taylor methods for tents

   https://doi.org/10.1090/mcom/3811  

   Gopalakrishnan, Jay; Sun, Zheng (May 2023, Mathematics of Computation)

   Structure-aware Taylor (SAT) methods are a class of timestepping schemes designed for propagating linear hyperbolic solutions within a tent-shaped spacetime region. Tents are useful to design explicit time marching schemes on unstructured advancing fronts with built-in locally variable timestepping for arbitrary spatial and temporal discretization orders. The main result of this paper is that an s s -stage SAT timestepping within a tent is weakly stable under the time step constraint Δ t ≤ C h 1 + 1 / s \Delta t \leq Ch^{1+1/s} , where Δ t \Delta t is the time step size and h h is the spatial mesh size. Improved stability properties are also presented for high-order SAT time discretizations coupled with low-order spatial polynomials. A numerical verification of the sharpness of proven estimates is also included. 

   more » « less
2. Locality-Sensitive Bucketing Functions for the Edit Distance

   https://doi.org/10.4230/LIPIcs.WABI.2022.22  

   Chen, Ke; Shao, Mingfu (August 2022, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022))

   Boucher, Christina; Rahmann, Sven (Ed.)

   Many bioinformatics applications involve bucketing a set of sequences where each sequence is allowed to be assigned into multiple buckets. To achieve both high sensitivity and precision, bucketing methods are desired to assign similar sequences into the same bucket while assigning dissimilar sequences into distinct buckets. Existing k-mer-based bucketing methods have been efficient in processing sequencing data with low error rate, but encounter much reduced sensitivity on data with high error rate. Locality-sensitive hashing (LSH) schemes are able to mitigate this issue through tolerating the edits in similar sequences, but state-of-the-art methods still have large gaps. Here we generalize the LSH function by allowing it to hash one sequence into multiple buckets. Formally, a bucketing function, which maps a sequence (of fixed length) into a subset of buckets, is defined to be (d₁, d₂)-sensitive if any two sequences within an edit distance of d₁ are mapped into at least one shared bucket, and any two sequences with distance at least d₂ are mapped into disjoint subsets of buckets. We construct locality-sensitive bucketing (LSB) functions with a variety of values of (d₁,d₂) and analyze their efficiency with respect to the total number of buckets needed as well as the number of buckets that a specific sequence is mapped to. We also prove lower bounds of these two parameters in different settings and show that some of our constructed LSB functions are optimal. These results provide theoretical foundations for their practical use in analyzing sequences with high error rate while also providing insights for the hardness of designing ungapped LSH functions. 

   more » « less
3. On the reduction in accuracy of finite difference schemes on manifolds without boundary

   https://doi.org/10.1093/imanum/drad048  

   Hamfeldt, Brittany Froese; Turnquist, Axel G_R (July 2023, IMA Journal of Numerical Analysis)

   Abstract We investigate error bounds for numerical solutions of divergence structure linear elliptic partial differential equations (PDEs) on compact manifolds without boundary. Our focus is on a class of monotone finite difference approximations, which provide a strong form of stability that guarantees the existence of a bounded solution. In many settings including the Dirichlet problem, it is easy to show that the resulting solution error is proportional to the formal consistency error of the scheme. We make the surprising observation that this need not be true for PDEs posed on compact manifolds without boundary. We propose a particular class of approximation schemes built around an underlying monotone scheme with consistency error $$O(h^{\alpha })$$. By carefully constructing barrier functions, we prove that the solution error is bounded by $$O(h^{\alpha /(d+1)})$$ in dimension $$d$$. We also provide a specific example where this predicted convergence rate is observed numerically. Using these error bounds, we further design a family of provably convergent approximations to the solution gradient. 

   more » « less
4. Locality-sensitive bucketing functions for the edit distance

   https://doi.org/10.1186/s13015-023-00234-2  

   Chen, Ke; Shao, Mingfu (July 2023, Algorithms for Molecular Biology)

   Abstract BackgroundMany bioinformatics applications involve bucketing a set of sequences where each sequence is allowed to be assigned into multiple buckets. To achieve both high sensitivity and precision, bucketing methods are desired to assign similar sequences into the same bucket while assigning dissimilar sequences into distinct buckets. Existingk-mer-based bucketing methods have been efficient in processing sequencing data with low error rates, but encounter much reduced sensitivity on data with high error rates. Locality-sensitive hashing (LSH) schemes are able to mitigate this issue through tolerating the edits in similar sequences, but state-of-the-art methods still have large gaps. ResultsIn this paper, we generalize the LSH function by allowing it to hash one sequence into multiple buckets. Formally, a bucketing function, which maps a sequence (of fixed length) into a subset of buckets, is defined to be$$(d_1, d_2)$$ $(d_1,d_2)$-sensitive if any two sequences within an edit distance of$$d_1$$ $d_1$are mapped into at least one shared bucket, and any two sequences with distance at least$$d_2$$ $d_2$are mapped into disjoint subsets of buckets. We construct locality-sensitive bucketing (LSB) functions with a variety of values of$$(d_1,d_2)$$ $(d_1,d_2)$and analyze their efficiency with respect to the total number of buckets needed as well as the number of buckets that a specific sequence is mapped to. We also prove lower bounds of these two parameters in different settings and show that some of our constructed LSB functions are optimal. ConclusionThese results lay the theoretical foundations for their practical use in analyzing sequences with high error rates while also providing insights for the hardness of designing ungapped LSH functions. 

   more » « less
5. Arithmetic Sketching

   Boneh, Dan; Boyle, Elette; Corrigan-Gibbs, Henry; Gilboa, Niv; Ishai, Yuval (January 2023, IACR International Cryptology Conference (CRYPTO))

   This paper introduces arithmetic sketching, an abstraction of a primitive that several previous works use to achieve lightweight, low-communication zero-knowledge verification of secret-shared vectors. An arithmetic sketching scheme for a language L ⊆ F^n consists of (1) a randomized linear function compressing a long input x to a short “sketch,” and (2) a small arithmetic circuit that accepts the sketch if and only if x ∈ L, up to some small error. If the language L has an arithmetic sketching scheme with short sketches, then it is possible to test membership in L using an arithmetic circuit with few multiplication gates. Since multiplications are the dominant cost in protocols for computation on secret-shared, encrypted, and committed data, arithmetic sketching schemes give rise to lightweight protocols in each of these settings. Beyond the formalization of arithmetic sketching, our contributions are: – A general framework for constructing arithmetic sketching schemes from algebraic varieties. This framework unifies schemes from prior work and gives rise to schemes for useful new languages and with improved soundness error. – The first arithmetic sketching schemes for languages of sparse vectors: vectors with bounded Hamming weight, bounded L1 norm, and vectors whose few non-zero values satisfy a given predicate. – A method for “compiling” any arithmetic sketching scheme for a language L into a low-communication malicious-secure multi-server protocol for securely testing that a client-provided secret-shared vector is in L. We also prove the first nontrivial lower bounds showing limits on the sketch size for certain languages (e.g., vectors of Hamming-weight one) and proving the non-existence of arithmetic sketching schemes for others (e.g., the language of all vectors that contain a specific value). 

   more » « less