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. Time-Space Lower Bounds for Finding Collisions in Merkle-Damgard Hash Functions

   Akshima; Guo, Siyao; Lie, Qipeng (July 2022, IACR CRYPTO 2022)

   We revisit the problem of finding B-block-long collisions in Merkle-Damg˚ard Hash Functions in the auxiliary-input random oracle model, in which an attacker gets a piece of S-bit advice about the random oracle and makes T oracle queries. Akshima, Cash, Drucker and Wee (CRYPTO 2020), based on the work of Coretti, Dodis, Guo and Steinberger (EUROCRYPT 2018), showed a simple attack for 2 ≤ B ≤ T (with respect to a random salt). The attack achieves advantage Ω( e ST B/2 n + T 2/2 n) where n is the output length of the random oracle. They conjectured that this attack is optimal. However, this so-called STB conjecture was only proved for B ≈ T and B = 2. Very recently, Ghoshal and Komargodski (CRYPTO 22) confirmed STB conjecture for all constant values of B, and provided an Oe(S 4T B2/2 n + T 2/2 n) bound for all choices of B. In this work, we prove an Oe((ST B/2 n)· max{1, ST2/2 n}+T 2/2 n) bound for every 2 < B < T. Our bound confirms the STB conjecture for ST2 ≤ 2 n, and is optimal up to a factor of S for ST2 > 2 n (note as T 2 is always at most 2n, otherwise finding a collision is trivial by the birthday attack). Our result subsumes all previous upper bounds for all ranges of parameters except for B = Oe(1) and ST2 > 2 n. We obtain our results by adopting and refining the technique of Chung, Guo, Liu, and Qian (FOCS 2020). Our approach yields more modular proofs and sheds light on how to bypass the limitations of prior techniques. Along the way, we obtain a considerably simpler and illuminating proof for B = 2, recovering the main result of Akshima, Cash, Drucker and Wee. 

   more » « less