More Like this

1. Embeddings and labeling schemes for A*

   T Eden, T.; Indyk, P.; Xu, H. (January 2022, Innovations in Theoretical Computer Science (ITCS))

   A* is a classic and popular method for graphs search and path finding. It assumes the existence of a heuristic function h(u,t) that estimates the shortest distance from any input node u to the destination t. Traditionally, heuristics have been handcrafted by domain experts. However, over the last few years, there has been a growing interest in learning heuristic functions. Such learned heuristics estimate the distance between given nodes based on "features" of those nodes. In this paper we formalize and initiate the study of such feature-based heuristics. In particular, we consider heuristics induced by norm embeddings and distance labeling schemes, and provide lower bounds for the tradeoffs between the number of dimensions or bits used to represent each graph node, and the running time of the A* algorithm. We also show that, under natural assumptions, our lower bounds are almost optimal. 

   more » « less
2. Engineering Biology for Climate and Sustainability: A research roadmap for a cleaner future

   Engineering Biology Research Consortium (September 2022, Engineering Biology Research Consortium)

   Strategic research roadmap document outlining critical gaps and future needs to develop sustainable biotechnologies through engineering biology. 

   more » « less
3. A Candidate for a Strong Separation of Information and Communication

   https://doi.org/10.4230/LIPIcs.ITCS.2018.11  

   Braverman, Mark; Ganor, Anat; Kol, Gillat; Raz, Ran (January 2018, Innovations in Theoretical Computer Science Conference (ITCS 2018))
4. A fit-for-purpose framework for urban occupancy modeling: Theory and a case study

   https://doi.org/10.1016/j.buildenv.2025.113113  

   Yang, Yiting; Dong, Bing (July 2025, Building and Environment)
5. A trichotomy for hitting times and escape rates for a class of unimodal maps

   https://doi.org/10.1017/etds.2025.10201  

   DEMERS, MARK; TODD, MIKE (December 2025, Ergodic Theory and Dynamical Systems)

   Abstract We consider local escape rates and hitting time statistics for unimodal interval maps of Misiurewicz–Thurston type. We prove that for any pointzin the interval, there is a local escape rate and hitting time statistics that is one of three types. While it is key that we cover all pointsz, the particular interest here is whenzis periodic and in the postcritical orbit that yields the third part of the trichotomy. We also prove generalized asymptotic escape rates of the form first shown by Bruin, Demers and Todd. 

   more » « less