skip to main content

Title: A (mostly) symbolic system for monotonic inference with unscoped Episodic Logical Forms
We implement the formalization of natural logic-like monotonic inference using Unscoped Episodic Logical Forms (ULFs) by Kim et al. (2020). We demonstrate this system’s capacity to handle a variety of challenging semantic phenomena using the FraCaS dataset (Cooper et al., 1996).These results give empirical evidence for prior claims that ULF is an appropriate representation to mediate natural logic-like inferences.
Authors:
Award ID(s):
1940981
Publication Date:
NSF-PAR ID:
10299972
Journal Name:
NAtural LOgic Meets MAchine Learning (NALOMA'21)
Sponsoring Org:
National Science Foundation
More Like this
  1. Polyacetylenic lipids accumulate in various Apiaceae species after pathogen attack, suggesting that these compounds are naturally occurring pesticides and potentially valuable resources for crop improvement. These compounds also promote human health and slow tumor growth. Even though polyacetylenic lipids were discovered decades ago, the biosynthetic pathway underlying their production is largely unknown. To begin filling this gap and ultimately enable polyacetylene engineering, we studied polyacetylenes and their biosynthesis in the major Apiaceae crop carrot (Daucus carota subsp. sativus). Using gas chromatography and mass spectrometry, we identified three known polyacetylenes and assigned provisional structures to two novel polyacetylenes. We also quantifiedmore »these compounds in carrot leaf, petiole, root xylem, root phloem, and root periderm extracts. Falcarindiol and falcarinol predominated and accumulated primarily in the root periderm. Since the multiple double and triple carbon-carbon bonds that distinguish polyacetylenes from ubiquitous fatty acids are often introduced by Δ12 oleic acid desaturase (FAD2)-type enzymes, we mined the carrot genome for FAD2 genes. We identified a FAD2 family with an unprecedented 24 members and analyzed public, tissue-specific carrot RNA-Seq data to identify coexpressed members with root periderm-enhanced expression. Six candidate genes were heterologously expressed individually and in combination in yeast and Arabidopsis (Arabidopsis thaliana), resulting in the identification of one canonical FAD2 that converts oleic to linoleic acid, three divergent FAD2-like acetylenases that convert linoleic into crepenynic acid, and two bifunctional FAD2s with Δ12 and Δ14 desaturase activity that convert crepenynic into the further desaturated dehydrocrepenynic acid, a polyacetylene pathway intermediate. These genes can now be used as a basis for discovering other steps of falcarin-type polyacetylene biosynthesis, to modulate polyacetylene levels in plants, and to test the in planta function of these molecules. Many organisms implement specialized biochemical pathways to convert ubiquitous metabolites into bioactive chemical compounds. Since plants comprise the majority of the human diet, specialized plant metabolites play crucial roles not only in crop biology but also in human nutrition. Some asterids produce lipid compounds called polyacetylenes (for review, see Negri, 2015) that exhibit antifungal activity (Garrod et al., 1978; Kemp, 1978; Harding and Heale, 1980, 1981; Olsson and Svensson, 1996) and accumulate in response to fungal phytopathogen attack (De Wit and Kodde, 1981; Elgersma and Liem, 1989). These observations have led to the longstanding hypothesis that polyacetylenes are natural pesticides. These same lipid compounds exhibit cytotoxic activity against human cancer cell lines and slow tumor growth (Fujimoto and Satoh, 1988; Matsunaga et al., 1989, 1990; Cunsolo et al., 1993; Bernart et al., 1996; Kobaek-Larsen et al., 2005; Zidorn et al., 2005), making them important nutritional compounds. The major source of polyacetylenes in the human diet is carrot (Daucus carota L.). Carrot is one of the most important crop species in the Apiaceae, with rapidly increasing worldwide cultivation (Rubatzky et al., 1999; Dawid et al., 2015). The most common carrot polyacetylenes are C17 linear aliphatic compounds containing two conjugated carbon-carbon triple bonds, one or two carbon-carbon double bonds, and a diversity of additional in-chain oxygen-containing functional groups. In carrot, the most abundant of these compounds are falcarinol and falcarindiol (Dawid et al., 2015). Based on their structures, it has been hypothesized that these compounds (alias falcarin-type polyacetylenes) are derived from ubiquitous fatty acids. Indeed, biochemical investigations (Haigh et al., 1968; Bohlman, 1988), radio-chemical tracer studies (Barley et al., 1988), and the discovery of pathway intermediates (Jones et al., 1966; Kawazu et al., 1973) implicate a diversion of flux away from linolenate biosynthesis as the entry point into falcarin-type polyacetylene biosynthesis (for review, see Minto and Blacklock, 2008). The final steps of linolenate biosynthesis are the conversion of oleate to linoleate, mediated by fatty acid desaturase 2 (FAD2), and linoleate to linolenate, catalyzed by FAD3. Some plant species contain divergent forms of FAD2 that, instead of or in addition to converting oleate to linoleate, catalyze the installation of unusual in-chain functional groups such as hydroxyl groups, epoxy groups, conjugated double bonds, or carbon-carbon triple bonds into the acyl chain (Badami and Patil, 1980) and thus divert flux from linolenate production into the accumulation of unusual fatty acids. Previous work in parsley (Petroselinum crispum; Apiaceae) identified a divergent form of FAD2 that (1) was up-regulated in response to pathogen treatment and (2) when expressed in soybean embryos resulted in production of the monoyne crepenynate and, by the action of an unassigned enzyme, dehydrocrepenynate (Kirsch et al., 1997; Cahoon et al., 2003). The results of the parsley studies are consistent with a pathogen-responsive, divergent FAD2-mediated pathway that leads to acetylenic fatty acids. However, information regarding the branch point into acetylenic fatty acid production in agriculturally relevant carrot is still largely missing, in particular, the identification and functional characterization of enzymes that can divert carbon flux away from linolenate biosynthesis into the production of dehydrocrepenynate and ultimately falcarin-type polyacetylenes. Such genes, once identified, could be used in the future design of transgenic carrot lines with altered polyacetylene content, enabling direct testing of in planta polyacetylene function and potentially the engineering of pathogen-resistant, more nutritious carrots. These genes could also provide the foundation for further investigations of more basic aspects of plant biology, including the evolution of fatty acid-derived natural product biosynthesis pathways across the Asterid clade, as well as the role of these pathways and compounds in plant ecology and plant defense. Recently, a high-quality carrot genome assembly was released (Iorizzo et al., 2016), providing a foundation for genome-enabled studies of Apiaceous species. This study also provided publicly accessible RNA sequencing (RNA-Seq) data from diverse carrot tissues. Using these resources, this study aimed to provide a detailed gas chromatography-based quantification of polyacetylenes in carrot tissues for which RNA-Seq data are available, then combine this information with bioinformatics analysis and heterologous expression to identify and characterize biosynthetic genes that underlie the major entry point into carrot polyacetylene biosynthesis. To achieve these goals, thin-layer chromatography (TLC) was combined with gas chromatography-mass spectrometry (GC-MS) and gas chromatography-flame ionization detection to identify and quantify polyacetylenic metabolites in five different carrot tissues. Then the sequences and tissue expression profiles of potential FAD2 and FAD2-like genes annotated in the D. carota genome were compared with the metabolite data to identify candidate pathway genes, followed by biochemical functionality tests using yeast (Saccharomyces cerevisae) and Arabidopsis (Arabidopsis thaliana) as heterologous expression systems.« less
  2. Abstract
    The PoseASL dataset consists of color and depth videos collected from ASL signers at the Linguistic and Assistive Technologies Laboratory under the direction of Matt Huenerfauth, as part of a collaborative research project with researchers at the Rochester Institute of Technology, Boston University, and the University of Pennsylvania. Access: After becoming an authorized user of Databrary, please contact Matt Huenerfauth if you have difficulty accessing this volume. We have collected a new dataset consisting of color and depth videos of fluent American Sign Language signers performing sequences ASL signs and sentences. Given interest among sign-recognition and other computer-vision researchersMore>>
  3. Braverman, Mark (Ed.)
    Grothendieck’s inequality [Grothendieck, 1953] states that there is an absolute constant K > 1 such that for any n× n matrix A, ‖A‖_{∞→1} := max_{s,t ∈ {± 1}ⁿ}∑_{i,j} A[i,j]⋅s(i)⋅t(j) ≥ 1/K ⋅ max_{u_i,v_j ∈ S^{n-1}}∑_{i,j} A[i,j]⋅⟨u_i,v_j⟩. In addition to having a tremendous impact on Banach space theory, this inequality has found applications in several unrelated fields like quantum information, regularity partitioning, communication complexity, etc. Let K_G (known as Grothendieck’s constant) denote the smallest constant K above. Grothendieck’s inequality implies that a natural semidefinite programming relaxation obtains a constant factor approximation to ‖A‖_{∞ → 1}. The exact value of K_G ismore »yet unknown with the best lower bound (1.67…) being due to Reeds and the best upper bound (1.78…) being due to Braverman, Makarychev, Makarychev and Naor [Braverman et al., 2013]. In contrast, the little Grothendieck inequality states that under the assumption that A is PSD the constant K above can be improved to π/2 and moreover this is tight. The inapproximability of ‖A‖_{∞ → 1} has been studied in several papers culminating in a tight UGC-based hardness result due to Raghavendra and Steurer (remarkably they achieve this without knowing the value of K_G). Briet, Regev and Saket [Briët et al., 2015] proved tight NP-hardness of approximating the little Grothendieck problem within π/2, based on a framework by Guruswami, Raghavendra, Saket and Wu [Guruswami et al., 2016] for bypassing UGC for geometric problems. This also remained the best known NP-hardness for the general Grothendieck problem due to the nature of the Guruswami et al. framework, which utilized a projection operator onto the degree-1 Fourier coefficients of long code encodings, which naturally yielded a PSD matrix A. We show how to extend the above framework to go beyond the degree-1 Fourier coefficients, using the global structure of optimal solutions to the Grothendieck problem. As a result, we obtain a separation between the NP-hardness results for the two problems, obtaining an inapproximability result for the Grothendieck problem, of a factor π/2 + ε₀ for a fixed constant ε₀ > 0.« less
  4. Symbolic methods have been used extensively for proving security of cryptographic protocols in the Dolev-Yao model, and more recently for proving security of cryptographic primitives and constructions in the computational model. However, existing methods for proving security of cryptographic constructions in the computational model often require significant expertise and interaction, or are fairly limitedin scope and expressivity. This paper introduces a symbolic approach for proving security of cryptographic constructions based on the Learning With Errors assumption (Regev, STOC 2005). Such constructions are instances of lattice-based cryptography and are extremely important due to their potential role in post-quantum cryptography. Following (Barthe,more »Gregoire and Schmidt, CCS 2015), our approach combines a computational logic and deducibility problems—a standard tool for representing the adversary’s knowledge, the Dolev-Yao model. The computational logic is used to capture (indistinguishability-based) security notions and drive the security proofs whereas deducibility problems are used as side-conditions to control that rules of the logic are applied correctly. We then use AutoLWE, an implementation of the logic, to deliver very short or even automatic proofs of several emblematic constructions, including CPAPKE (Gentry et al., STOC 2008), (Hierarchical) Identity-Based Encryption (Agrawal et al. Eurocrypt 2010), Inner Product Encryption (Agrawal et al. Asiacrypt 2011), CCA-PKE (Micciancio et al., Eurocrypt 2012). The main technical novelty beyond AutoLWE is a set of (semi-)decision procedures for deducibility problems, using extensions of Grobner basis computations for subalgebras in the non-commutative setting (instead of ideals in the commutative setting). Our procedures cover the theory of matrices, which is required for lattice-based assumption, as well as the theory of non-commutative rings, fields, and Diffie-Hellman exponentiation, in its standard, bilinear and multilinear forms. Additionally, AutoLWE supports oracle-relative assumptions, which are used specifically to apply (advanced forms of) the Leftover Hash Lemma, an information-theoretical tool widely used in lattice-based proofs.« less
  5. Symbolic methods have been used extensively for proving security of cryptographic protocols in the Dolev-Yao model, and more recently for proving security of cryptographic primitives and constructions in the computational model. However, existing methods for proving security of cryptographic constructions in the computational model often require significant expertise and interaction, or are fairly limited in scope and expressivity. This paper introduces a symbolic approach for proving security of cryptographic constructions based on the Learning With Errors assumption (Regev, STOC 2005). Such constructions are instances of lattice-based cryptography and are extremely important due to their potential role in post-quantum cryptography. Followingmore »(Barthe, Gre ́goire and Schmidt, CCS 2015), our approach combines a computational logic and deducibility problems—a standard tool for representing the adversary’s knowledge, the Dolev-Yao model. The computational logic is used to capture (indistinguishability-based) security notions and drive the security proofs whereas deducibility problems are used as side-conditions to control that rules of the logic are applied correctly. We then use AutoLWE, an implementation of the logic, to deliver very short or even automatic proofs of several emblematic constructions, including CPA- PKE (Gentry et al., STOC 2008), (Hierarchical) Identity-Based Encryption (Agrawal et al. Eurocrypt 2010), Inner Product Encryption (Agrawal et al. Asiacrypt 2011), CCA-PKE (Micciancio et al., Eurocrypt 2012). The main technical novelty beyond AutoLWE is a set of (semi-)decision procedures for deducibility problems, using extensions of Grobner basis computations for subalgebras in the (non-)commutative setting (instead of ideals in the commutative setting). Our procedures cover the theory of matrices, which is required for lattice-based assumption, as well as the theory of non-commutative rings, fields, and Diffie-Hellman exponentiation, in its standard, bilinear and multilinear forms. Additionally, AutoLWE supports oracle-relative assumptions, which are used specifically to apply (advanced forms of) the Leftover Hash Lemma, an information-theoretical tool widely used in lattice-based proofs.« less