More Like this

1. Universally-optimal distributed algorithms for known topologies

   https://doi.org/10.1145/3406325.3451081  

   Haeupler, Bernhard; Wajc, David; Zuzic, Goran (June 2021, Symposium on Theory of Computing (STOC))

   null (Ed.)

   Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster algorithms. This motivates two questions: (i) What network topology parameters determine the complexity of distributed optimization? (ii) Are there universally-optimal algorithms that are as fast as possible on every topology? We resolve these 25-year-old open problems in the known-topology setting (i.e., supported CONGEST) for a wide class of global network optimization problems including MST, (1+є)-min cut, various approximate shortest paths problems, sub-graph connectivity, etc. In particular, we provide several (equivalent) graph parameters and show they are tight universal lower bounds for the above problems, fully characterizing their inherent complexity. Our results also imply that algorithms based on the low-congestion shortcut framework match the above lower bound, making them universally optimal if shortcuts are efficiently approximable. 

   more » « less
2. Learning a Partially-Known Discrete Event System

   https://doi.org/10.1109/ACCESS.2020.2983074  

   Wendell Bates, Ira; Karimoddini, Ali; Karimadini, Mohammad (January 2020, IEEE Access)
3. A checklist of lichens known from the Philippines

   https://doi.org/10.5943/cream/10/1/29  

   Paguirigan, JAG (January 2020, Current Research in Environmental & Applied Mycology)
4. Urban-adapted mammal species have more known pathogens

   https://doi.org/10.1038/s41559-022-01723-0  

   Albery, Gregory F.; Carlson, Colin J.; Cohen, Lily E.; Eskew, Evan A.; Gibb, Rory; Ryan, Sadie J.; Sweeny, Amy R.; Becker, Daniel J. (June 2022, Nature Ecology & Evolution)
5. Strategy synthesis for partially-known switched stochastic systems

   https://doi.org/10.1145/3447928.3456649  

   Jackson, John; Laurenti, Luca; Frew, Eric; Lahijanian, Morteza (May 2021, The 24th International Conference on Hybrid Systems: Computation and Control)

   null (Ed.)

   We present a data-driven framework for strategy synthesis for partially-known switched stochastic systems. The properties of the system are specified using linear temporal logic (LTL) over finite traces (LTLf), which is as expressive as LTL and enables interpretations over finite behaviors. The framework first learns the unknown dynamics via Gaussian process regression. Then, it builds a formal abstraction of the switched system in terms of an uncertain Markov model, namely an Interval Markov Decision Process (IMDP), by accounting for both the stochastic behavior of the system and the uncertainty in the learning step. Then, we synthesize a strategy on the resulting IMDP that maximizes the satisfaction probability of the LTLf specification and is robust against all the uncertainties in the abstraction. This strategy is then refined into a switching strategy for the original stochastic system. We show that this strategy is near-optimal and provide a bound on its distance (error) to the optimal strategy. We experimentally validate our framework on various case studies, including both linear and non-linear switched stochastic systems. 

   more » « less