More Like this

1. Sparse representation of vectors in lattices and semigroups

   https://doi.org/10.1007/s10107-021-01657-8  

   Aliev, Iskander; Averkov, Gennadiy; De_Loera, Jesús_A; Oertel, Timm (May 2021, Mathematical Programming)

   Abstract We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the$$\ell _0$$ ${\ell }_0$-norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$ ${\ell }_0$-norm of solutions to systems$$A\varvec{x}=\varvec{b}$$ $Ax=b$, where$$A\in \mathbb {Z}^{m\times n}$$ $A\in Z^{m\times n}$,$${\varvec{b}}\in \mathbb {Z}^m$$ $b\in Z^m$and$$\varvec{x}$$ $x$is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\ell _0$$ ${\ell }_0$-norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over$$\mathbb {R}$$ $R$, to other subdomains such as$$\mathbb {Z}$$ $Z$. We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables. 

   more » « less
2. Weak and strong solutions for a fluid‐poroelastic‐structure interaction via a semigroup approach

   https://doi.org/10.1002/mma.10533  

   Avalos, George; Gurvich, Elena; Webster, Justin_T (October 2024, Mathematical Methods in the Applied Sciences)

   A filtration system comprising a Biot poroelastic solid coupled to an incompressible Stokes free‐flow is considered in 3D. Across the flat 2D interface, the Beavers‐Joseph‐Saffman coupling conditions are taken. In the inertial, linear, and non‐degenerate case, the hyperbolic‐parabolic coupled problem is posed through a dynamics operator on a chosen energy space, adapted from Stokes‐Lamé coupled dynamics. A semigroup approach is utilized to circumvent issues associated to mismatched trace regularities at the interface. The generation of a strongly continuous semigroup for the dynamics operator is obtained via a non‐standard maximality argument. The latter employs a mixed‐variational formulation in order to invoke the Babuška‐Brezzi theorem. The Lumer‐Philips theorem then yields semigroup generation, and thereby, strong and generalized solutions are obtained. For the linear dynamics, density obtains the existence of weak solutions; we extend to the case where the Biot compressibility of constituents degenerates. Thus, for the inertial linear Biot‐Stokes filtration system, we provide a clear elucidation of strong solutions and a construction of weak solutions, as well as their regularity through associated estimates. 

   more » « less
3. Uniform bounds of families of analytic semigroups and Lyapunov Linear Stability of planar fronts

   https://doi.org/10.1002/mana.202300273  

   Latushkin, Yuri; Pogan, Alin (July 2024, Mathematische Nachrichten)

   Abstract We study families of analytic semigroups, acting on a Banach space, and depending on a parameter, and give sufficient conditions for existence of uniform with respect to the parameter norm bounds using spectral properties of the respective semigroup generators. In particular, we use estimates of the resolvent operators of the generators along vertical segments to estimate the growth/decay rate of the norm for the family of analytic semigroups. These results are applied to prove the Lyapunov linear stability of planar traveling waves of systems of reaction–diffusion equations, and the bidomain equation, important in electrophysiology. 

   more » « less
4. On Bounded Distance Decoding with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem

   https://doi.org/10.1007/978-3-030-77870-5_19  

   Albrecht, Martin R; Heninger, Nadia (January 2021, EUROCRYPT 2021: Advances in Cryptology – EUROCRYPT 2021)

   Lattice-based algorithms in cryptanalysis often search for a target vector satisfying integer linear constraints as a shortest or closest vector in some lattice. In this work, we observe that these formulations may discard non-linear information from the underlying application that can be used to distinguish the target vector even when it is far from being uniquely close or short. We formalize lattice problems augmented with a predicate distinguishing a target vector and give algorithms for solving instances of these problems. We apply our techniques to lattice-based approaches for solving the Hidden Number Problem, a popular technique for recovering secret DSA or ECDSA keys in side-channel attacks, and demonstrate that our algorithms succeed in recovering the signing key for instances that were previously believed to be unsolvable using lattice approaches. We carried out extensive experiments using our estimation and solving framework, which we also make available with this work. 

   more » « less
5. Self-Regularity of Non-Negative Output Weightsfor Overparameterized Two-Layer Neural Networks

   Gamarnik, David; Kızıldağ, Eren C.; Zadik, Ilias (January 2021, International Symposium on Information Theory)

   null (Ed.)

   We consider the problem of finding a two-layer neural network with sigmoid, rectified linear unit (ReLU), or binary step activation functions that "fits" a training data set as accurately as possible as quantified by the training error; and study the following question: \emph{does a low training error guarantee that the norm of the output layer (outer norm) itself is small?} We answer affirmatively this question for the case of non-negative output weights. Using a simple covering number argument, we establish that under quite mild distributional assumptions on the input/label pairs; any such network achieving a small training error on polynomially many data necessarily has a well-controlled outer norm. Notably, our results (a) have a polynomial (in d) sample complexity, (b) are independent of the number of hidden units (which can potentially be very high), (c) are oblivious to the training algorithm; and (d) require quite mild assumptions on the data (in particular the input vector X∈ℝd need not have independent coordinates). We then leverage our bounds to establish generalization guarantees for such networks through \emph{fat-shattering dimension}, a scale-sensitive measure of the complexity class that the network architectures we investigate belong to. Notably, our generalization bounds also have good sample complexity (polynomials in d with a low degree), and are in fact near-linear for some important cases of interest. 

   more » « less