More Like this

1. A hybridizable discontinuous Galerkin method for the coupled Navier–Stokes/Biot problem

   https://doi.org/10.1051/m2an/2024045  

   Cesmelioglu, Aycil; Lee, Jeonghun J; Rhebergen, Sander (July 2024, ESAIM: Mathematical Modelling and Numerical Analysis)

   In this paper we present a hybridizable discontinuous Galerkin method for the time-dependent Navier–Stokes equations coupled to the quasi-static poroelasticity equationsviainterface conditions. We determine a bound on the data that guarantees stability and well-posedness of the fully discrete problem and provea priorierror estimates. A numerical example confirms our analysis. 

   more » « less
2. The two-center problem of uncertain points on cactus graphs

   https://doi.org/10.1007/s10878-025-01292-5  

   Xu, Haitao; Zhang, Jingru (April 2025, Journal of Combinatorial Optimization)

   Abstract We study the two-center problem on cactus graphs in facility locations, which aims to place two facilities on the graph network to serve customers in order to minimize the maximum transportation cost. In our problem, the location of each customer is uncertain and may appear atO(m) points on the network with probabilities. More specifically, given are a cactus graphGand a set$$\mathcal {P}$$ $P$ofn(weighted) uncertain points where every uncertain point hasO(m) possible locations onGeach associated with a probability and is of a non-negative weight. The problem aims to compute two centers (points) onGso that the maximum (weighted) expected distance of thenuncertain points to their own expected closest center is minimized. No previous algorithms are known for this problem. In this paper, we present the first algorithm for this problem and it solves the problem in$$O(|G|+ m^{2}n^{2}\log mn)$$ $O\left(\right|G|+m^2{n}^{2}logmn)$time. 

   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. 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
5. Ranked Document Retrieval in External Memory

   https://doi.org/10.1145/3559763  

   Shah, Rahul; Sheng, Cheng; Thankachan, Sharma; Vitter, Jeffrey (January 2023, ACM Transactions on Algorithms)

   The ranked (or top-k) document retrieval problem is defined as follows: preprocess a collection{T₁,T₂,… ,T_d}ofdstrings (called documents) of total lengthninto a data structure, such that for any given query(P,k), wherePis a string (called pattern) of lengthp ≥ 1andk ∈ [1,d]is an integer, the identifiers of thosekdocuments that are most relevant toPcan be reported, ideally in the sorted order of their relevance. The seminal work by Hon et al. [FOCS 2009 and Journal of the ACM 2014] presented anO(n)-space (in words) data structure withO(p+klogk)query time. The query time was later improved toO(p+k)[SODA 2012] and further toO(p/log_σn+k)[SIAM Journal on Computing 2017] by Navarro and Nekrich, whereσis the alphabet size. We revisit this problem in the external memory model and present three data structures. The first one takesO(n)-space and answer queries inO(p/B+ log_Bn + k/B+log^*(n/B)) I/Os, whereBis the block size. The second one takesO(nlog^*(n/B)) space and answer queries in optimalO(p/B+ log_Bn + k/B)I/Os. In both cases, the answers are reported in the unsorted order of relevance. To handle sorted top-kdocument retrieval, we present anO(nlog(d/B))space data structure with optimal query cost. 

   more » « less