More Like this

1. Approximation Algorithm for Norm Multiway Cut

   https://doi.org/10.4230/LIPIcs.ESA.2023.32  

   Carlson, Charlie; Jafarov, Jafar; Makarychev, Konstantin; Makarychev, Yury; Shan, Liren (August 2023, Proceedings of the European Symposium on Algorithms)

   Gørtz, Inge Li; Farach-Colton, Martin; Puglisi, Simon J; Herman, Grzegorz (Ed.)

   We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced l_p-norm Multiway Cut, a generalization of the problem, in which the goal is to minimize the l_p norm of the edge boundaries of k parts. We provide an O(log^{1/2} n log^{1/2 + 1/p} k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log^{3/2} n log^{1/2} k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log^{1/2} n log^{7/2} k) approximation algorithm with a weaker oracle and an O(log^{1/2} n log^{5/2} k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n^{1/4-ε} approximation algorithm for every ε > 0 assuming the Hypergraph Dense-vs-Random Conjecture. 

   more » « less
2. Engineering Escherichia coli for enhanced sensitivity to the autoinducer‐2 quorum sensing signal

   https://doi.org/10.1002/btpr.2881  

   Stephens, Kristina; Zargar, Amin; Emamian, Milad; Abutaleb, Nadia; Choi, Erica; Quan, David_N; Payne, Gregory; Bentley, William_E (August 2019, Biotechnology Progress)

   Abstract The autoinducer‐2 (AI‐2) quorum sensing system is involved in a range of population‐based bacterial behaviors and has been engineered for cell–cell communication in synthetic biology systems. Investigation into the cellular mechanisms of AI‐2 processing has determined that overexpression of uptake genes increases AI‐2 uptake rate, and genomic deletions of degradation genes lowers the AI‐2 level required for activation of reporter genes. Here, we combine these two strategies to engineer anEscherichia colistrain with enhanced ability to detect and respond to AI‐2. In anE. colistrain that does not produce AI‐2, we monitored AI‐2 uptake and reporter protein expression in a strain that overproduced the AI‐2 uptake or phosphorylation units LsrACDB or LsrK, a strain with the deletion of AI‐2 degradation units LsrF and LsrG, and an “enhanced” strain with both overproduction of AI‐2 uptake and deletion of AI‐2 degradation elements. By adding up to 40 μM AI‐2 to growing cell cultures, we determine that this “enhanced” AI‐2 sensitive strain both uptakes AI‐2 more rapidly and responds with increased reporter protein expression than the others. This work expands the toolbox for manipulating AI‐2 quorum sensing processes both in native environments and for synthetic biology applications. 

   more » « less
3. Crossing numbers of cable knots

   https://doi.org/10.1112/blms.13140  

   Kalfagianni, Efstratia; Mcconkey, Rob (June 2024, Bulletin of the London Mathematical Society)

   We use the degree of the colored Jones knot polynomials to show that the crossing number of a (p,q)‐cable of an adequate knot with crossing number c is larger than q^2 c. As an application, we determine the crossing number of 2‐cables of adequate knots. We also determine the crossing number of the connected sum of any adequate knot with a 2‐cable of an adequate knot. 

   more » « less
4. Spherical conical metrics and harmonic maps to spheres

   https://doi.org/10.1090/tran/8578  

   Karpukhin, Mikhail; Zhu, Xuwen (February 2022, Transactions of the American Mathematical Society)

   A spherical conical metric g g on a surface Σ \Sigma is a metric of constant curvature 1 1 with finitely many isolated conical singularities. The uniformization problem for such metrics remains largely open when at least one of the cone angles exceeds 2 π 2\pi . The eigenfunctions of the Friedrichs Laplacian Δ g \Delta _g with eigenvalue λ = 2 \lambda =2 play a special role in this problem, as they represent local obstructions to deformations of the metric g g in the class of spherical conical metrics. In the present paper we apply the theory of multivalued harmonic maps to spheres to the question of existence of such eigenfunctions. In the first part we establish a new criterion for the existence of 2 2 -eigenfunctions, given in terms of a certain meromorphic data on Σ \Sigma . As an application we give a description of all 2 2 -eigenfunctions for metrics on the sphere with at most three conical singularities. The second part is an algebraic construction of metrics with large number of 2 2 -eigenfunctions via the deformation of multivalued harmonic maps. We provide new explicit examples of metrics with many 2 2 -eigenfunctions via both approaches, and describe the general algorithm to find metrics with arbitrarily large number of 2 2 -eigenfunctions. 

   more » « less
5. On binary quartics and the Cassels–Tate pairing

   https://doi.org/10.1007/s40993-022-00376-z  

   Fisher, Tom (December 2022, Research in Number Theory)

   Abstract We use the invariant theory of binary quartics to give a new formula for the Cassels–Tate pairing on the 2-Selmer group of an elliptic curve. Unlike earlier methods, our formula does not require us to solve any conics. An important role in our construction is played by a certain K 3 surface defined by a (2, 2, 2)-form. 

   more » « less