More Like this

1. Persistence Over Posets

   https://doi.org/10.1090/noti2761  

   Kim, Woojin; Mémoli, Facundo (September 2023, Notices of the American Mathematical Society)
2. Sustainability Over Sets

   https://doi.org/10.1002/ep.12761  

   Manousiouthakis, Vasilios I.; Jorat, Masih (May 2018, Environmental Progress & Sustainable Energy)
3. Constraint Optimization over Semirings

   https://doi.org/10.1609/aaai.v37i4.25522  

   Pavan, A.; Meel, Kuldeep S.; Vinodchandran, N. V.; Bhattacharyya, Arnab (June 2023, Proceedings of the AAAI Conference on Artificial Intelligence)

   Interpretations of logical formulas over semirings (other than the Boolean semiring) have applications in various areas of computer science including logic, AI, databases, and security. Such interpretations provide richer information beyond the truth or falsity of a statement. Examples of such semirings include Viterbi semiring, min-max or access control semiring, tropical semiring, and fuzzy semiring. The present work investigates the complexity of constraint optimization problems over semirings. The generic optimization problem we study is the following: Given a propositional formula phi over n variable and a semiring (K,+, . ,0,1), find the maximum value over all possible interpretations of phi over K. This can be seen as a generalization of the well-known satisfiability problem (a propositional formula is satisfiable if and only if the maximum value over all interpretations/assignments over the Boolean semiring is 1). A related problem is to find an interpretation that achieves the maximum value. In this work, we first focus on these optimization problems over the Viterbi semiring, which we call optConfVal and optConf. We first show that for general propositional formulas in negation normal form, optConfVal and optConf are in FP^NP. We then investigate optConf when the input formula phi is represented in the conjunctive normal form. For CNF formulae, we first derive an upper bound on the value of optConf as a function of the number of maximum satisfiable clauses. In particular, we show that if r is the maximum number of satisfiable clauses in a CNF formula with m clauses, then its optConf value is at most 1/4^(m-r). Building on this we establish that optConf for CNF formulae is hard for the complexity class FP^NP[log]. We also design polynomial-time approximation algorithms and establish an inapproximability for optConfVal. We establish similar complexity results for these optimization problems over other semirings including tropical, fuzzy, and access control semirings. 

   more » « less
4. Consensus over evolutionary graphs

   https://doi.org/10.23919/ECC.2018.8550392  

   Smyrnakis, Michalis; Freris, Nikolaos M.; Tembine, Hamidou (June 2018, Consensus over evolutionary graphs)

   We establish average consensus on graphs with dynamic topologies prescribed by evolutionary games among strategic agents. Each agent possesses a private reward function and dynamically decides whether to create new links and/or whether to delete existing ones in a selfish and decentralized fashion, as indicated by a certain randomized mechanism. This model incurs a time-varying and state-dependent graph topology for which traditional consensus analysis is not applicable. We prove asymptotic average consensus almost surely and in mean square for any initial condition and graph topology. In addition, we establish exponential convergence in expectation. Our results are validated via simulation studies on random networks. 

   more » « less
5. Robust Transport Over Networks

   https://doi.org/10.1109/TAC.2016.2626796  

   Chen, Yongxin; Georgiou, Tryphon; Pavon, Michele; Tannenbaum, Allen (September 2017, IEEE Transactions on Automatic Control)