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. 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
3. 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
4. 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
5. Half-time range description for the free space wave operator and the spherical means transform

   https://doi.org/10.1088/1361-6420/adb0e6  

   Kuchment, P.; Kunyansky, L. (February 2025, Inverse Problems)

   Abstract The forward problem arising in several hybrid imaging modalities can be modeled by the Cauchy problem for the free space wave equation. Solution to this problems describes propagation of a pressure wave, generated by a source supported inside unit sphereS. The datagrepresent the time-dependent values of the pressure on the observation surfaceS. Finding initial pressureffrom the known values ofgconsitutes the inverse problem. The latter is also frequently formulated in terms of the spherical means offwith centers onS. Here we consider a problem of range description of the wave operator mappingfintog. Such a problem was considered before, with datagknown on time interval at least $[0,2]$(assuming the unit speed of sound). Range conditions were also found in terms of spherical means, with radii of integration spheres lying in the range $[0,2]$. However, such data are redundant. We present necessary and sufficient conditions for functiongto be in the range of the wave operator, forggiven on a half-time interval $[0,1]$. This also implies range conditions on spherical means measured for the radii in the range $[0,1]$. 

   more » « less