More Like this

1. Doubly Balanced Connected Graph Partitioning

   https://doi.org/10.1145/3381419  

   Soltan, Saleh; Yannakakis, Mihalis; Zussman, Gil (April 2020, ACM Transactions on Algorithms)

   null (Ed.)

   We introduce and study the doubly balanced connected graph partitioning problem: Let G =( V , E ) be a connected graph with a weight (supply/demand) function p : V → {−1, +1} satisfying p ( V )=∑ j &isin V p ( j ) = 0. The objective is to partition G into ( V 1 , V 2 ) such that G [ V 1 ] and G [ V 2 ] are connected, ∣ p ( V 1 )∣,∣ p ( V 2 )∣≤ c p , and max{ ∣ V 1 / V 2 ∣,∣ V 2 / V 1 ∣} ≤ c s , for some constants c p and c s . When G is 2-connected, we show that a solution with c p =1 and c s =2 always exists and can be found in randomized polynomial time. Moreover, when G is 3-connected, we show that there is always a “perfect” solution (a partition with p ( V 1 )= p ( V 2 )=0 and ∣ V 1 ∣=∣ V 2 ∣, if ∣ V ∣≡ 0 (mod 4)), and it can be found in randomized polynomial time. Our techniques can be extended, with similar results, to the case in which the weights are arbitrary (not necessarily ±1), and to the case that p ( V )≠ 0 and the excess supply/demand should be split evenly. They also apply to the problem of partitioning a graph with two types of nodes into two large connected subgraphs that preserve approximately the proportion of the two types. 

   more » « less
2. Photoluminescence from Defects in Be‐Doped GaN

   https://doi.org/10.1002/pssb.202400656  

   Reshchikov, Michael_Alexander; McEwen, Benjamin; Shahedipour‐Sandvik, Shadi (February 2025, physica status solidi (b))

   While GaN is a crucial semiconductor material for bright light‐emitting devices, fabrication of p‐type GaN remains challenging since the Mg acceptor commonly used for p‐type doping is not shallow enough. Doping of GaN with Be is a promising path, yet no reliable p‐type GaN has been achieved by Be doping so far. One of the reasons is a poor understanding of point defects in Be‐doped GaN that can be studied by photoluminescence (PL). The yellow (YL_Be) band at 2.15 eV is the dominant PL band in Be‐doped GaN. In this work, a blue PL band named the BL_Beband is discovered. It has a maximum at 2.6 eV and a lifetime of 0.8 μs at temperatures below 100 K. The BL_Beband is observed in GaN samples with relatively high concentrations of Be (>10¹⁸ cm⁻³). Both the YL_Beand BL_Bebands likely originate from the isolated Be_Gadefect, namely from electron transitions via the −/0 and 0/+ thermodynamic transition levels of the Be_Ga. The 0/+ transition level is located at 0.1–0.2 eV above the valence band. Other broad PL bands in Be‐doped GaN were also observed and preliminarily attributed to Be‐containing complexes. 

   more » « less
3. Rewrite rule inference using equality saturation

   https://doi.org/10.1145/3485496  

   Nandi, Chandrakana; Willsey, Max; Zhu, Amy; Wang, Yisu_Remy; Saiki, Brett; Anderson, Adam; Schulz, Adriana; Grossman, Dan; Tatlock, Zachary (October 2021, Proceedings of the ACM on Programming Languages)

   Many compilers, synthesizers, and theorem provers rely on rewrite rules to simplify expressions or prove equivalences. Developing rewrite rules can be difficult: rules may be subtly incorrect, profitable rules are easy to miss, and rulesets must be rechecked or extended whenever semantics are tweaked. Large rulesets can also be challenging to apply: redundant rules slow down rule-based search and frustrate debugging. This paper explores how equality saturation, a promising technique that uses e-graphs toapplyrewrite rules, can also be used toinferrewrite rules. E-graphs can compactly represent the exponentially large sets of enumerated terms and potential rewrite rules. We show that equality saturation efficiently shrinks both sets, leading to faster synthesis of smaller, more general rulesets. We prototyped these strategies in a tool dubbed Ruler. Compared to a similar tool built on CVC4, Ruler synthesizes 5.8× smaller rulesets 25× faster without compromising on proving power. In an end-to-end case study, we show Ruler-synthesized rules which perform as well as those crafted by domain experts, and addressed a longstanding issue in a popular open source tool. 

   more » « less
4. Cycling Phosphorus and Nitrogen through Cropping Systems in an Intensive Dairy Production Region

   https://doi.org/10.3390/agronomy11051005  

   Leytem, April B.; Williams, Paula; Zuidema, Shan; Martinez, Audrey; Chong, Yen Leng; Vincent, Alyssa; Vincent, Aaron; Cronan, Daniel; Kliskey, Andrew; Wulfhorst, J. D.; et al (May 2021, Agronomy)

   null (Ed.)

   As pressure on the dairy industry to reduce its environmental impact increases, efficient recycling of manure nutrients through local cropping systems becomes crucial. The aim of this study was to calculate annual nitrogen (N) and phosphorus (P) budgets in six counties located in the Magic Valley, Idaho and estimate what distance manure would need to be transported to be in balance with crop nutrient demand given current dairy cattle populations and cropping systems. Our analysis suggests that crop N needs will not be met solely by manure, and synthetic fertilizer will need to be applied. However, to balance P with crop production, manure would need to be transported a minimum of 12.9 km from dairies and would have to replace synthetic fertilizer P on 91% of regional cropland. Education of producers and technical specialists would be necessary to improve the management of manure use in regional cropping systems. Technical solutions such as alternative diets for cattle and nutrient capture from manure streams will also likely be necessary to bring regional P into balance to protect environmental quality and improve the sustainability of the regional dairy industry. 

   more » « less
5. Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane

   https://doi.org/10.4230/LIPICS.SOCG.2024.4  

   Agarwal, Pankaj K; Ezra, Esther; Sharir, Micha (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   Let P be a set of m points in ℝ², let Σ be a set of n semi-algebraic sets of constant complexity in ℝ², let (S,+) be a semigroup, and let w: P → S be a weight function on the points of P. We describe a randomized algorithm for computing w(P∩σ) for every σ ∈ Σ in overall expected time O^*(m^{2s/(5s-4)}n^{(5s-6)/(5s-4)} + m^{2/3}n^{2/3} + m + n), where s > 0 is a constant that bounds the maximum complexity of the regions of Σ, and where the O^*(⋅) notation hides subpolynomial factors. For s ≥ 3, surprisingly, this bound is smaller than the best-known bound for answering m such queries in an on-line manner. The latter takes O^*(m^{s/(2s-1)}n^{(2s-2)/(2s-1)} + m + n) time. Let Φ: Σ × P → {0,1} be the Boolean predicate (of constant complexity) such that Φ(σ,p) = 1 if p ∈ σ and 0 otherwise, and let Σ_Φ P = {(σ,p) ∈ Σ× P ∣ Φ(σ,p) = 1}. Our algorithm actually computes a partition ℬ_Φ of Σ_Φ P into bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) O^*(m^{2s/(5s-4)}n^{(5s-6)/(5s-4)} + m^{2/3}n^{2/3} + m + n). It is straightforward to compute w(P∩σ) for all σ ∈ Σ from ℬ_Φ. Similarly, if η: Σ → S is a weight function on the regions of Σ, ∑_{σ ∈ Σ: p ∈ σ} η(σ), for every point p ∈ P, can be computed from ℬ_Φ in a straightforward manner. We also mention a few other applications of computing ℬ_Φ. 

   more » « less