Fast computation of generic bivariate resultants

We prove that the resultant of two “sufficiently generic” bivariate polynomials over a finite field can be computed in quasi-linear expected time, using a randomized algorithm of Las Vegas type. A similar complexity bound is proved for the computation of the lexicographical Gröbner basis for the ideal generated by the two polynomials.     

Duality respecting representations and compatible complexity measures for gammoids

We show that every gammoid has special digraph representations, such that a representation of the dual of the gammoid may be easily obtained by reversing all arcs. In an informal sense, the duality notion of a poset applied to the digraph of a special representation of a gammoid commutes with the operation of forming the dual of that gammoid. We use these special representations in order to define a complexity measure for gammoids, such that the classes of gammoids with bounded complexity are closed under duality, minors, and direct sums.     

A linear time algorithm for balance vertices on trees

The concept of balance vertices was first investigated by Reid (1999). For the main result “the balance vertices of a tree consist of a single vertex or two adjacent vertices”, Shan and Kang (2004) and Reid and DePalma (2005) improved the length and technique of the proof. In this paper we further discuss the balance vertices on trees in a generalization context. We do not only provide a simple efficient proof for the relevant result but also develop a linear time algorithm to find the set of balance vertices on the underlying tree.     

Sterically Allowed H-type Supramolecular Polymerizations

The functionalization of π-conjugated scaffolds with sterically demanding substituents is a widely used tactic to suppress cofacial (H-type) stacking interactions, which may even inhibit self-assembly. Contrary to expectations, we demonstrate herein that increasing steric effects can result in an enhanced thermodynamic stability of H-type supramolecular polymers. In our approach, we have investigated two boron dipyrromethene (BODIPY) dyes with bulky phenyl ( 2 ) and mesityl ( 3 ) meso-substituents and compared their self-assembly in nonpolar media with that of a parent meso-methyl BODIPY 1 lacking bulky groups. While the enhanced steric demand induces pathway complexity, the superior thermodynamic stability of the H-type pathways can be rationalized in terms of additional enthalpic gain arising from intermolecular C−H⋅⋅⋅F−B interactions of the orthogonally arranged aromatic substituents, which overrule their inherent steric demand. Our findings underline the importance of balancing competing non-covalent interactions in self-assembly.     

Synthetic Matching of Complex Monoterpene Indole Alkaloid Chemical Space

Monoterpene indole alkaloids (MIAs) are endowed with high structural and spatial complexity and characterized by diverse biological activities. Given this complexity-activity combination in MIAs, rapid and efficient access to chemical matter related to and with complexity similar to these alkaloids would be highly desirable, since such compound classes might display novel bioactivity. We describe the design and synthesis of a pseudo-natural product (pseudo-NP) collection obtained by the unprecedented combination of MIA fragments through complexity-generating transformations, resulting in arrangements not currently accessible by biosynthetic pathways. Cheminformatic analyses revealed that both the pseudo-NPs and the MIAs reside in a unique and common area of chemical space with high spatial complexity-density that is only sparsely populated by other natural products and drugs. Investigation of bioactivity guided by morphological profiling identified pseudo-NPs that inhibit DNA synthesis and modulate tubulin. These results demonstrate that the pseudo-NP collection occupies similar biologically relevant chemical space that Nature has endowed MIAs with.