More Like this

1. Hardness and approximation of submodular minimum linear ordering problems

   https://doi.org/10.1007/s10107-023-02038-z  

   Farhadi, Majid; Gupta, Swati; Sun, Shengding; Tetali, Prasad; Wigal, Michael C (December 2023, Mathematical Programming)

   Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost$$f(\cdot )$$ $f(·)$due to an ordering$$\sigma $$ $\sigma$of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ ${min}_{\sigma }{\sum }_{i\in \left[n\right]}f\left(E_{i,\sigma }\right)$, where$$E_{i,\sigma }$$ $E_{i,\sigma }$is the set of items mapped by$$\sigma $$ $\sigma$to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a$$(2-\frac{1+\ell _{f}}{1+|E|})$$ $(2-\frac{1+{\ell }_f}{1+\left|E\right|})$-approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ ${\ell }_f=\frac{f\left(E\right)}{{max}_{x\in E}f\left(\left\{x\right\}\right)}$satisfies$$1 \le \ell _f \le |E|$$ $1\le {\ell }_f\le \left|E\right|$. Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ $(2-\frac{1+r\left(E\right)}{1+\left|E\right|})$-approximation for the matroid MLOP, where$$f = r$$ $f=r$is the rank function of a matroid. We further show that minimum latency vertex cover is$$\frac{4}{3}$$ $\frac{4}{3}$-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest. 

   more » « less
2. VC-Dimension of Hyperplanes Over Finite Fields

   https://doi.org/10.1007/s00373-025-02909-6  

   Ascoli, Ruben; Betti, Livia; Cheigh, Justin; Iosevich, Alex; Jeong, Ryan; Liu, Xuyan; McDonald, Brian; Milgrim, Wyatt; Miller, Steven_J; Romero_Acosta, Francisco; et al (March 2025, Graphs and Combinatorics)

   Abstract Let$$\mathbb {F}_q^d$$ $F_q^d$be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$and a fixed nonzero$$t\in \mathbb {F}_q$$ $t\in F_q$, let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ $H_t\left(E\right)=\{h_y:y\in E\}$, where$$h_y:E\rightarrow \{0,1\}$$ $h_y:E\to \{0,1\}$is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ $\{x\in E:x·y=t\}$. Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ $d=3$that if$$|E|\ge Cq^{\frac{11}{4}}$$ $\left|E\right|\ge C{q}^{\frac{11}{4}}$andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$isdwhenever$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ $\left|E\right|\ge C_d{q}^{d-\frac{1}{d-1}}$. 

   more » « less
3. High resolution X-ray spectra of the time evolution of emission from metastable electronic states of highly charged Ni-like ions

   https://doi.org/10.1140/epjd/s10053-024-00872-0  

   Burke, Timothy; Takacs, Endre; Dipti; Hosier, Adam; O’Neil, Galen; Tan, Joseph; Staiger, Hunter; Naing, Aung; Marler, Joan; Ralchenko, Yuri (June 2024, The European Physical Journal D)

   AbstractMetastable levels of highly charged ions that can only decay via highly forbidden transitions can have a significant effect on the properties of high temperature plasmas. For example, the highly forbidden 3d$$^{10}$$ $_{}^{10}$$$_{J=0}$$ $_{J=0}^{}$- 3d$$^9$$ $_{}^9$4 s$$(\frac{5}{2},\frac{1}{2})_{J=3}$$ ${(\frac{5}{2},\frac{1}{2})}_{J=3}$magnetic octupole (M3) transition in nickel-like ions can result in a large metastable population of its upper level which can then be ionized by electrons of energies below the ground state ionization potential. We present a method to study metastable electronic states in highly charged ions that decay by x-ray emission in electron beam ion traps (EBIT). The time evolution of the emission intensity can be used to study the parameters of ionization balance dynamics and the lifetime of metastable states. The temporal and energy resolution of a new transition-edge sensor microcalorimeter array enables these studies at the National Institute of Standards and Technology EBIT. Graphical abstractNOMAD calculated time evolution of the ratio of the Ni-like and Co-like lines in Nd at varying electron densities compared with measured ratios 

   more » « less
4. Evaluation codes arising from symmetric polynomials

   https://doi.org/10.1007/s10623-025-01637-5  

   Gatti, Barbara; Korchmáros, Gábor; Nagy, Gábor P; Pallozzi_Lavorante, Vincenzo; Schulte, Gioia (May 2025, Designs, Codes and Cryptography)

   Abstract Datta and Johnsen (Des Codes Cryptogr 91:747–761, 2023) introduced a new family of evaluation codes in an affine space of dimension$$\ge 2$$ $\ge 2$over a finite field$${\mathbb {F}}_q$$ $F_q$where linear combinations of elementary symmetric polynomials are evaluated on the set of all points with pairwise distinct coordinates. In this paper, we propose a generalization by taking low dimensional linear systems of symmetric polynomials. Computation for small values of$$q=7,9$$ $q=7,9$shows that carefully chosen generalized Datta–Johnsen codes$$\left[ \frac{1}{2}q(q-1),3,d\right] $$ $\left(\frac{1}{2},q,(q-1),,,3,,,d\right)$have minimum distancedequal to the optimal value minus 1. 

   more » « less
5. The Kondo effect in the quantum XX spin chain

   https://doi.org/10.1088/1751-8121/ad51bb  

   Kattel, Pradip; Tang, Yicheng; Pixley, J H; Andrei, Natan (June 2024, Journal of Physics A: Mathematical and Theoretical)

   Abstract We investigate the boundary phenomena that arise in a finite-sizeXXspin chain interacting through anXXinteraction with a spin $-\frac{1}{2}$impurity located at its edge. Upon Jordan–Wigner transformation, the model is described by a quadratic Fermionic Hamiltonian. Our work displays, within this ostensibly simple model, the emergence of the Kondo effect, a quintessential hallmark of strongly correlated physics. We also show how the Kondo cloud shrinks and turns into a single particle bound state as the impurity coupling increases beyond a critical value. In more detail, using bothBethe Ansatzandexact diagonalizationtechniques, we show that the local moment of the impurity is screened by different mechanisms depending on the ratio of the boundary and bulk coupling $\frac{J_{\mathrm{imp}}}{J}$. When the ratio falls below the critical value $\sqrt{2}$, the impurity is screened via the Kondo effect. However, when the ratio between the coupling exceeds the critical value $\sqrt{2}$an exponentially localized bound mode is formed at the impurity site which screens the spin of the impurity in the ground state. We show that the boundary phase transition is reflected in local ground state properties by calculating the spinon density of states, the magnetization at the impurity site in the presence of a global magnetic field, and the finite temperature susceptibility of the impurity. We find that the spinon density of states in the Kondo phase has the characteristic Lorentzian peak that moves from the Fermi level to the maximum energy of the spinon as the impurity coupling is increased and becomes a localized bound mode in the bound mode phase. Moreover, the impurity magnetization and the finite temperature impurity susceptibility behave differently in the two phases. When the boundary coupling $J_{\mathrm{imp}}$exceeds the critical value $\sqrt{2}J$, the model is no longer boundary conformal invariant as a massive bound mode appears at the impurity site. 

   more » « less