More Like this

1. Enumerating Nontrivial Knot Mosaics with SAT (Student Abstract)

   https://doi.org/10.1609/aaai.v36i11.21645  

   Miller, Hannah (June 2022, Proceedings of the AAAI Conference on Artificial Intelligence)

   Mathematical knots are interesting topological objects. Using simple arcs, lines, and crossings drawn on eleven possible tiles, knot mosaics are a representation of knots on a mosaic board. Our contribution is using SAT solvers as a tool for enumerating nontrivial knot mosaics. By encoding constraints for local knot mosaic properties, we computationally reduce the search space by factors of up to 6600. Our future research directions include encoding constraints for global properties and using parallel SAT techniques to attack larger boards. 

   more » « less
2. The distribution of knots in the Petaluma model

   https://doi.org/10.2140/agt.2018.18.3647  

   Even-Zohar, C; Hass, J; Linial, N; Nowik, T (October 2018, Algebraic geometric topology)

   The representation of knots by petal diagrams (Adams et al 2012) naturally defines a sequence of distributions on the set of knots. We establish some basic properties of this randomized knot model. We prove that in the random n–petal model the probability of obtaining every specific knot type decays to zero as n, the number of petals, grows. In addition we improve the bounds relating the crossing number and the petal number of a knot. This implies that the n–petal model represents at least exponentially many distinct knots. Past approaches to showing, in some random models, that individual knot types occur with vanishing probability rely on the prevalence of localized connect summands as the complexity of the knot increases. However, this phenomenon is not clear in other models, including petal diagrams, random grid diagrams and uniform random polygons. Thus we provide a new approach to investigate this question. 

   more » « less
3. A Linear Time Algorithm for Quantum 2-SAT

   De Beaudrap, Niel; Gharibian, Sevag (January 2016, Conference on Computational Complexity)

   The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to the quantum setting, defining the problem "quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unit-cost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2-SAT which runs in linear time, i.e. deterministic time O(n+m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2-SAT, and bears similarities with both the linear time 2-SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979]. 

   more » « less
4. A note on the involutive invariants of certain pretzel knots

   https://doi.org/10.1142/S0218216522500444  

   Hendricks, Kristen; Issac, Matthew; McConnell, Nicholas (June 2022, Journal of Knot Theory and Its Ramifications)

   We compute the involutive knot invariants for pretzel knots of the form P(−2,m,n) for m and n odd and greater than or equal to 3. 

   more » « less
5. The Spitzer Coverage of HSC-Deep with IRAC for Z studies (SHIRAZ). I. IRAC Mosaics

   https://doi.org/10.3847/1538-3881/acd773  

   Annunziatella, Marianna; Sajina, Anna; Stefanon, Mauro; Marchesini, Danilo; Lacy, Mark; Labbé, Ivo; Houston, Lilianna; Bezanson, Rachel; Egami, Eiichi; Fan, Xiaohui; et al (June 2023, The Astronomical Journal)

   Abstract We present new Spitzer Infrared Array Camera (IRAC) 3.6 and 4.5 μ m mosaics of three fields, E-COSMOS, DEEP2-F3, and ELAIS-N1. Our mosaics include both new IRAC observations as well as reprocessed archival data in these fields. These fields are part of the HSC-Deep grizy survey and have a wealth of additional ancillary data. The addition of these new IRAC mosaics is critical in allowing for improved photometric redshifts and stellar population parameters at cosmic noon and earlier epochs. The total area mapped by this work is ∼17 deg 2 with a mean integration time of ≈1200s, providing a median 5 σ depth of 23.7(23.3) at 3.6(4.5) μ m in AB. We perform SExtractor photometry both on the combined mosaics as well as the single-epoch mosaics taken ≈6 months apart. The resultant IRAC number counts show good agreement with previous studies. In combination with the wealth of existing and upcoming spectrophotometric data in these fields, our IRAC mosaics will enable a wide range of galactic evolution and AGN studies. With that goal in mind, we make the combined IRAC mosaics and coverage maps of these three fields publicly available. 

   more » « less