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. Numerical signatures of ultra-local criticality in a one dimensional Kondo lattice model

   https://doi.org/10.21468/SciPostPhys.17.2.034  

   Nikolaenko, Alexander; Zhang, Ya-Hui (January 2024, SciPost Physics)

   Heavy fermion criticality has been a long-standing problem in condensed matter physics. Here we study a one-dimensional Kondo lattice model through numerical simulation and observe signatures of local criticality. We vary the Kondo couplingJ_K $J_K$at fixed doping x. At large positiveJ_K $J_K$, we confirm the expected conventional Luttinger liquid phase with2k_F=\frac{1+x}{2} $2k_F=\frac{1+x}{2}$(in units of2\pi $2\pi$), an analogue of the heavy Fermi liquid (HFL) in the higher dimension. In theJ_K ≤ 0 $J_K\le 0$side, our simulation finds the existence of a fractional Luttinger liquid (LL\star $\star$) phase with2k_F=\frac{x}{2} $2k_F=\frac{x}{2}$, accompanied by a gapless spin mode originating from localized spin moments, which serves as an analogue of the fractional Fermi liquid (FL\star $\star$) phase in higher dimensions. The LL\star $\star$phase becomes unstable and transitions to a spin-gapped Luther-Emery (LE) liquid phase at small positiveJ_K $J_K$. Then we mainly focus on the “critical regime” between the LE phase and the LL phase. Approaching the critical point from the spin-gapped LE phase, we often find that the spin gap vanishes continuously, while the spin-spin correlation length in real space stays finite and small. For a certain range of doping, in a point (or narrow region) ofJ_K $J_K$, the dynamical spin structure factor obtained through the time-evolving block decimation (TEBD) simulation shows dispersion-less spin fluctuations in a finite range of momentum space above a small energy scale (around0.035 J $0.035J$) that is limited by the TEBD accuracy. All of these results are unexpected for a regular gapless phase (or critical point) described by conformal field theory (CFT). Instead, they are more consistent with exotic ultra-local criticality with an infinite dynamical exponentz=+ $z=+$. The numerical discovery here may have important implications on our general theoretical understanding of the strange metals in heavy fermion systems. Lastly, we propose to simulate the model in a bilayer optical lattice with a potential difference. 

   more » « less
4. 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
5. 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