Combining Semilattices and Semimodules

• URL: http://arxiv.org/abs/2012.14778v3
• Date: Sun, 24 Jan 2021 16:47:41 GMT
• Title: Combining Semilattices and Semimodules
• Authors: Filippo Bonchi and Alessio Santamaria
• Abstract summary: We show that the composition of $mathcal P$ with $mathcal S$ by means of such $delta$ yields almost the monad of convex subsets previously introduced by Jacobs. We provide a handy characterisation of the canonical weak lifting of $mathcal P$ to $mathbbEM(mathcal S)$ as well as an algebraic theory for the resulting composed monad.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We describe the canonical weak distributive law $\delta \colon \mathcal S \mathcal P \to \mathcal P \mathcal S$ of the powerset monad $\mathcal P$ over the $S$-left-semimodule monad $\mathcal S$, for a class of semirings $S$. We show that the composition of $\mathcal P$ with $\mathcal S$ by means of such $\delta$ yields almost the monad of convex subsets previously introduced by Jacobs: the only difference consists in the absence in Jacobs's monad of the empty convex set. We provide a handy characterisation of the canonical weak lifting of $\mathcal P$ to $\mathbb{EM}(\mathcal S)$ as well as an algebraic theory for the resulting composed monad. Finally, we restrict the composed monad to finitely generated convex subsets and we show that it is presented by an algebraic theory combining semimodules and semilattices with bottom, which are the algebras for the finite powerset monad $\mathcal P_f$.

Related papers

• Relative volume of comparable pairs under semigroup majorization [0.0]
  We review recent results and conjectures in the case of emphmajorization relation. We prove new exact finite-$n$ results in the case of emphUT-majorization relation.
  arXiv  Detail & Related papers  (2024-10-30T16:48:59Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Increasing subsequences, matrix loci, and Viennot shadows [0.0]
  We show that the quotient $mathbbF[mathbfx_n times n]/I_n$ admits a standard monomial basis. We also calculate the structure of $mathbbF[mathbfx_n times n]/I_n$ as a graded $mathfrakS_n times mathfrakS_n$-module.
  arXiv  Detail & Related papers  (2023-06-14T19:48:01Z)
• There Are No Post-Quantum Weakly Pseudo-Free Families in Any Nontrivial Variety of Expanded Groups [0.0]
  We show that there are no post-quantum weakly pseudo-free families in $mathfrak V$, even in the worst-case setting and/or the black-box model. Also, we define and study some types of weak pseudo-freeness for families of computational and black-box $Omega$-algebras.
  arXiv  Detail & Related papers  (2023-02-21T17:55:42Z)
• Monogamy of entanglement between cones [68.8204255655161]
  We show that monogamy is not only a feature of quantum theory, but that it characterizes the minimal tensor product of general pairs of convex cones. Our proof makes use of a new characterization of products of simplices up to affine equivalence.
  arXiv  Detail & Related papers  (2022-06-23T16:23:59Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Topological phases of unitary dynamics: Classification in Clifford category [0.0]
  A quantum cellular automaton (QCA) or a causal unitary is by definition an automorphism of local operator algebra. A Clifford QCA is one that maps any Pauli operator to a finite tensor product of Pauli operators.
  arXiv  Detail & Related papers  (2022-05-18T18:00:38Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  The observables associated with a quantum system $S$ form a non-commutative algebra $mathcal A_S$. It is assumed that a density matrix $rho$ can be determined from the expectation values of observables. Abelian algebras do not have inner automorphisms, so the measurement apparatus can determine mean values of observables.
  arXiv  Detail & Related papers  (2021-12-14T16:29:53Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.