More Like this

1. Lattice Hamiltonian for adjoint QCD2

   https://doi.org/10.1007/JHEP08(2024)009  

   Dempsey, Ross; Klebanov, Igor R; Pufu, Silviu S; Søgaard, Benjamin T (August 2024, Journal of High Energy Physics)

   A<sc>bstract</sc> We introduce a Hamiltonian lattice model for the (1 + 1)-dimensional SU(N_c) gauge theory coupled to one adjoint Majorana fermion of massm. The discretization of the continuum theory uses staggered Majorana fermions. We analyze the symmetries of the lattice model and find lattice analogs of the anomalies of the corresponding continuum theory. An important role is played by the lattice translation by one lattice site, which in the continuum limit involves a discrete axial transformation. On a lattice with periodic boundary conditions, the Hilbert space breaks up into sectors labeled by theN_c-alityp= 0, …N_c− 1. Our symmetry analysis implies various exact degeneracies in the spectrum of the lattice model. In particular, it shows that, form= 0 and evenN_c, the sectorspandp′ are degenerate if |p−p′| =N_c/2. In theN_c= 2 case, we explicitly construct the action of the Hamiltonian on a basis of gauge-invariant states, and we perform both a strong coupling expansion and exact diagonalization for lattices of up to 12 lattice sites. Upon extrapolation of these results, we find good agreement with the spectrum computed previously using discretized light-cone quantization. One of our new results is the first numerical calculation of the fermion bilinear condensate. 

   more » « less
2. Fermi isospectrality for discrete periodic Schrödinger operators

   https://doi.org/10.1002/cpa.22161  

   Liu, Wencai (September 2023, Communications on Pure and Applied Mathematics)

   Abstract Let , where , , are pairwise coprime. Let be the discrete Schrödinger operator, where Δ is the discrete Laplacian on and the potential is Γ‐periodic. We prove three rigidity theorems for discrete periodic Schrödinger operators in any dimension :If at some energy level, Fermi varieties of two real‐valued Γ‐periodic potentialsVandYare the same (this feature is referred to asFermi isospectralityofVandY), andYis a separable function, thenVis separable;If two complex‐valued Γ‐periodic potentialsVandYare Fermi isospectral and both and are separable functions, then, up to a constant, lower dimensional decompositions and are Floquet isospectral, ;If a real‐valued Γ‐potentialVand the zero potential are Fermi isospectral, thenVis zero.In particular, all conclusions in (1), (2) and (3) hold if we replace the assumption “Fermi isospectrality” with a stronger assumption “Floquet isospectrality”. 

   more » « less
3. Smallest Synthetic Witnesses for Conjunctive Queries

   https://doi.org/10.1145/3725250  

   Esmailpour, Aryan; Glavic, Boris; Hu, Xiao; Sintos, Stavros (June 2025, Proceedings of the ACM on Management of Data)

   Given a self-join-free conjunctive queryQand a set of tuplesS, asynthetic witness Dis a database instance such that the result ofQonDisS. In this work, we are interested in two problems. First, the existence problem ESW decides whether any synthetic witnessDexists. Second, given that a synthetic witness exists, the minimization problem SSW computes a synthetic witness of minimal size. The SSW problem is related to thesmallest witness problemrecently studied by Hu and Sintos [22]; however, the objective and the results are inherently different. More specifically, we show that SSW is poly-time solvable for a wider range of queries. Interestingly, in some cases, SSW is related to optimization problems in other domains, such as therole miningproblem in data mining and theedge concentrationproblem in graph drawing. Solutions to ESW and SSW are of practical interest, e.g., fortest database generationfor applications accessing a database and fordata compressionby encoding a datasetSas a pair of a queryQand databaseD. We prove that ESW is in P, presenting a simple algorithm that, given anyS, decides whether a synthetic witness exists in polynomial time in the size ofS. Next, we focus on the SSW problem. We show an algorithm that computes a minimal synthetic witness in polynomial time with respect to the size ofSfor any queryQthat has thehead-dominationproperty. IfQdoes not have such a property, then SSW is generally hard. More specifically, we show that for the class ofpath queries(of any constant length), SSW cannot be solved in polynomial time unless P = NP. We then extend this hardness result to the class ofBerge-acyclicqueries that do not have the head-domination property, obtaining a full dichotomy of SSW for Berge-acyclic queries. Finally, we investigate the hardness of SSW beyond Berge-acyclic queries by showing that SSW cannot be solved in polynomial time for some cyclic queries unless P = NP. 

   more » « less
4. Universal Algorithms for Clustering Problems

   https://doi.org/10.1145/3572840  

   Ganesh, Arun; Maggs, Bruce M; Panigrahi, Debmalya (April 2023, ACM Transactions on Algorithms)

   This article presentsuniversalalgorithms for clustering problems, including the widely studiedk-median,k-means, andk-center objectives. The input is a metric space containing allpotentialclient locations. The algorithm must selectkcluster centers such that they are a good solution foranysubset of clients that actually realize. Specifically, we aim for lowregret, defined as the maximum over all subsets of the difference between the cost of the algorithm’s solution and that of an optimal solution. A universal algorithm’s solutionSolfor a clustering problem is said to be an α , β-approximation if for all subsets of clientsC^′, it satisfiessol(C^′) ≤ α ċopt(C′) + β ċmr, whereopt(C′ is the cost of the optimal solution for clients (C′) andmris the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives ofk-median,k-means, andk-center that achieve (O(1),O(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other ℓ_p-objectives and the setting where some subset of the clients arefixed. We also give hardness results showing that (α, β)-approximation is NP-hard if α or β is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1),O(1))-approximation is the strongest type of guarantee obtainable for universal clustering. 

   more » « less
5. Membership Testing for Semantic Regular Expressions

   https://doi.org/10.1145/3729300  

   Huang, Yifei; Amini, Matin; Le_Glaunec, Alexis; Mamouras, Konstantinos; Raghothaman, Mukund (June 2025, Proceedings of the ACM on Programming Languages)

   This paper is about semantic regular expressions (SemREs). This is a concept that was recently proposed by Smore (Chen et al. 2023) in which classical regular expressions are extended with a primitive to query external oracles such as databases and large language models (LLMs). SemREs can be used to identify lines of text containing references to semantic concepts such as cities, celebrities, political entities, etc. The focus in their paper was on automatically synthesizing semantic regular expressions from positive and negative examples. In this paper, we study themembership testing problem. First, we present a two-pass NFA-based algorithm to determine whether a stringwmatches a SemRErinO(|r|²|w|²+ |r| |w|³) time, assuming the oracle responds to each query in unit time. In common situations, where oracle queries are not nested, we show that this procedure runs inO(|r|²|w|²) time. Experiments with a prototype implementation of this algorithm validate our theoretical analysis, and show that the procedure massively outperforms a dynamic programming-based baseline, and incurs a ≈ 2 × overhead over the time needed for interaction with the oracle. Second, we establish connections between SemRE membership testing and the triangle finding problem from graph theory, which suggest that developing algorithms which are simultaneously practical and asymptotically faster might be challenging. Furthermore, algorithms for classical regular expressions primarily aim to optimize their time and memory consumption. In contrast, an important consideration in our setting is to minimize the cost of invoking the oracle. We demonstrate an Ω(|w|²) lower bound on the number of oracle queries necessary to make this determination. 

   more » « less