Paul Spirakis

NeurIPS Conference 2025 Conference Paper

MACS: Multi-Agent Reinforcement Learning for Optimization of Crystal Structures

• Elena Zamaraeva
• Christopher Collins
• George Darling
• Matthew S Dyer
• Bei Peng
• Rahul Savani
• Dmytro Antypov
• Vladimir Gusev

Geometry optimization of atomic structures is a common and crucial task in computational chemistry and materials design. Following the learning to optimize paradigm, we propose a new multi-agent reinforcement learning method called Multi-Agent Crystal Structure optimization (MACS) to address the problem of periodic crystal structure optimization. MACS treats geometry optimization as a partially observable Markov game in which atoms are agents that adjust their positions to collectively discover a stable configuration. We train MACS across various compositions of reported crystalline materials to obtain a policy that successfully optimizes structures from the training compositions as well as structures of larger sizes and unseen compositions, confirming its excellent scalability and zero-shot transferability. We benchmark our approach against a broad range of state-of-the-art optimization methods and demonstrate that MACS optimizes periodic crystal structures significantly faster, with fewer energy calculations, and the lowest failure rate.

TCS Journal 2020 Journal Article

Preface

• Giorgio Ausiello
• Lila Kari
• Grzegorz Rozenberg
• Donald Sannella
• Paul Spirakis
• Pierre-Louis Curien

TCS Journal 2019 Journal Article

Preface

• Giorgio Ausiello
• Lila Kari
• Grzegorz Rozenberg
• Donald Sannella
• Paul Spirakis
• Pierre-Louis Curien

AAAI Conference 2017 Conference Paper

The Computational Complexity of Weighted Greedy Matching

• Argyrios Deligkas
• George Mertzios
• Paul Spirakis

Motivated by the fact that in several cases a matching in a graph is stable if and only if it is produced by a greedy algorithm, we study the problem of computing a maximum weight greedy matching on weighted graphs, termed GREEDY- MATCHING. In wide contrast to the maximum weight matching problem, for which many efficient algorithms are known, we prove that GREEDYMATCHING is strongly NP-hard and APX-complete, and thus it does not admit a PTAS unless P=NP, even on graphs with maximum degree at most 3 and with at most three different integer edge weights. Furthermore we prove that GREEDYMATCHING is strongly NP-hard if the input graph is in addition bipartite. Moreover we consider three natural parameters of the problem, for which we establish a sharp threshold behavior between NP-hardness and computational tractability. On the positive side, we present a randomized approximation algorithm (RGMA) for GREEDYMATCHING on a special class of weighted graphs, called bush graphs. We highlight an unexpected connection between RGMA and the approximation of maximum cardinality matching in unweighted graphs via randomized greedy algorithms. We show that, if the approximation ratio of RGMA is ρ, then for every > 0 the randomized MRG algorithm of (Aronson et al. 1995) gives a (ρ − )-approximation for the maximum cardinality matching. We conjecture that a tight bound for ρ is 2 3; we prove our conjecture true for four subclasses of bush graphs. Proving a tight bound for the approximation ratio of MRG on unweighted graphs (and thus also proving a tight value for ρ) is a long-standing open problem (Poloczek and Szegedy 2012). This unexpected relation of our RGMA algorithm with the MRG algorithm may provide new insights for solving this problem.

TCS Journal 2012 Journal Article

On mutual concavity and strategically-zero-sum bimatrix games

• Spyros Kontogiannis
• Paul Spirakis

We study the fundamental problem 2NASH of computing a Nash equilibrium (NE) point in bimatrix games. We start by proposing a novel characterization of the NE set, via a bijective map to the solution set of a parameterized quadratic program (NEQP), whose feasible space is the highly structured set of correlated equilibria (CE). This is, to our knowledge, the first characterization of the subset of CE points that are in “1–1” correspondence with the NE set of the game, and contributes to the quite lively discussion on the relation between the spaces of CE and NE points in a bimatrix game (e. g. , [15, 26, 33]). We proceed with studying a property of bimatrix games, which we call mutually concavity (MC), that assures polynomial-time tractability of 2NASH, due to the convexity of a proper parameterized quadratic program (either NEQP, or a parameterized variant of the Mangasarian & Stone formulation [23]) for a particular value of the parameter. We prove various characterizations of the MC-games, which eventually lead us to the conclusion that this class is equivalent to the class of strategically zero-sum (SZS) games of Moulin & Vial [25]. This gives an alternative explanation of the polynomial-time tractability of 2NASH for these games, not depending on the solvability of zero-sum games. Moreover, the recognition of the MC-property for an arbitrary game is much faster than the recognition SZS-property. This, along with the comparable time-complexity of linear programs and convex quadratic programs, leads us to a much faster algorithm for 2NASH in MC-games. We conclude our discussion with a comparison of MC-games (or, SZS-games) to k -rank games, which are known to admit for 2NASH a FPTAS when k is fixed [18], and a polynomial-time algorithm for k = 1 [2]. We finally explore some closeness properties under well-known NE set preserving transformations of bimatrix games.

TCS Journal 2009 Journal Article

Computing on a partially eponymous ring

• Marios Mavronicolas
• Loizos Michael
• Paul Spirakis

We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all identical (as in the anonymous model) nor necessarily unique (as in the eponymous model). In a decision problem formalized as a relation, processors receive inputs and seek to reach outputs respecting the relation. We focus on the partially eponymous ring, and we shall consider the computation of circularly symmetric relations on it. We consider sets of rings where all rings in the set have the same multiset of identity multiplicities. • We distinguish between solvability and computability: in solvability, processors are required to always reach outputs respecting the relation; in computability, they must do so whenever this is possible, and must otherwise report impossibility. – We present a topological characterization of solvability for a relation on a set of rings, which can be expressed as an efficiently checkable, number-theoretic predicate. – We present a universal distributed algorithm for computing a relation on a set of rings; it runs any distributed algorithm for constructing views, followed by local steps. • We derive, as our main result, a universal upper bound on the message complexity to compute a relation on a set of rings; this bound demonstrates a graceful degradation with the Least Minimum Base, a parameter indicating the degree of least possible eponymity for a set of rings. Thereafter, we identify two cases where a relation can be computed on a set of rings, with rings of size n, with an efficient number of O ( n ⋅ lg n ) messages.

TCS Journal 2009 Journal Article

The structure and complexity of Nash equilibria for a selfish routing game

• Dimitris Fotakis
• Spyros Kontogiannis
• Elias Koutsoupias
• Marios Mavronicolas
• Paul Spirakis

In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel links. We assume a collection of n users, each employing a mixed strategy, which is a probability distribution over links, to control the routing of her own traffic. In a Nash equilibrium, each user selfishly routes her traffic on those links that minimize her expected latency cost, given the network congestion caused by the other users. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link. We embark on a systematic study of several algorithmic problems related to the computation of Nash equilibria for the selfish routing game we consider. In a nutshell, these problems relate to deciding the existence of a pure Nash equilibrium, constructing a Nash equilibrium, constructing the pure Nash equilibria of minimum and maximum social cost, and computing the social cost of a given mixed Nash equilibrium. Our work provides a comprehensive collection of efficient algorithms, hardness results, and structural results for these algorithmic problems. Our results span and contrast a wide range of assumptions on the syntax of the Nash equilibria and on the parameters of the system.

TCS Journal 2008 Journal Article

Efficient sensor network design for continuous monitoring of moving objects

• Sotiris Nikoletseas
• Paul Spirakis

We study the problem of localizing and tracking multiple moving targets in wireless sensor networks, from a network design perspective i. e. towards estimating the least possible number of sensors to be deployed, their positions and operation characteristics needed to perform the tracking task. To avoid an expensive massive deployment, we try to take advantage of possible coverage overlaps over space and time, by introducing a novel combinatorial model that captures such overlaps. Under this model, we abstract the tracking network design problem by a combinatorial problem of covering a universe of elements by at least three sets (to ensure that each point in the network area is covered at any time by at least three sensors, and thus being localized). We then design and analyze an efficient approximate method for sensor placement and operation, that with high probability and in polynomial expected time achieves a Θ ( log n ) approximation ratio to the optimal solution. Our network design solution can be combined with alternative collaborative processing methods, to suitably fit different tracking scenarios.

TCS Journal 2007 Journal Article

The increase of the instability of networks due to Quasi-Static link capacities

• Dimitrios Koukopoulos
• Marios Mavronicolas
• Paul Spirakis

In this work, we study the impact of the dynamic changing of the network link capacities on the stability properties of packet-switched networks. Especially, we consider the Adversarial, Quasi-Static Queuing Theory model, where each link capacity may take on only two possible (integer) values, namely 1 and C > 1 under a ( w, ρ ) -adversary. We obtain the following results: • Allowing such dynamic changes to the link capacities of a network with just ten nodes that uses the LIS (Longest-in-System) protocol for contention–resolution results in instability at rates ρ > 2 − 1 and for large enough values of C. • The combination of dynamically changing link capacities with compositions of contention–resolution protocols on network queues suffices for similar instability bounds: The composition of LIS with any of SIS (Shortest-in-System), NTS (Nearest-to-Source), and FTG (Furthest-to-Go) protocols is unstable at rates ρ > 2 − 1 for large enough values of C. • The instability bound of the network subgraphs that are forbidden for stability is affected by the dynamic changes to the link capacities: we present improved instability bounds for all the directed subgraphs that were known to be forbidden for stability on networks running a certain greedy protocol.

TCS Journal 2005 Journal Article

Selfish unsplittable flows

• Dimitris Fotakis
• Spyros Kontogiannis
• Paul Spirakis

What is the price of anarchy when unsplittable demands are routed selfishly in general networks with load-dependent edge delays? Motivated by this question we generalize the model of Koutsoupias and Papadimitriou (Worst-case equilibria, in: Proc. of the 16th Annual Symp. on Theoretical Aspects of Computer Science (STACS ’99), Lecture Notes in Computer Science, Vol. 1563, Springer, Berlin, 1999, pp. 404–413) to the case of weighted congestion games. We show that varying demands of users crucially affect the nature of these games, which are no longer isomorphic to exact potential games, even for very simple instances. Indeed we construct examples where even a single-commodity (weighted) network congestion game may have no pure Nash equilibrium. On the other hand, we prove that any weighted network congestion game with linear edge delays admits a pure Nash equilibrium that can be found in pseudo-polynomial time. Finally, we consider the family of ℓ -layered networks and give a surprising answer to the question above: the price of anarchy of any weighted congestion game in a ℓ -layered network with m edges and edge delays equal to the loads is Θ ( log m / log log m ).

TCS Journal 2005 Journal Article

The cost of concurrent, low-contention Read&Modify&Write

• Costas Busch
• Marios Mavronicolas
• Paul Spirakis

This work addresses the possibility or impossibility, and the corresponding costs, of devising concurrent, low-contention implementations of atomic Read&Modify&Write (or RMW) operations in a distributed system. A natural class of monotone RMW operations associated with monotone groups, a certain class of algebraic groups introduced here, is considered. The popular Fetch&Add and Fetch&Multiply operations are examples from the class. A Monotone Linearizability Lemma is proved and employed as a chief combinatorial instrument in this work; it establishes inherent ordering constraints of linearizability for a certain class of executions of any distributed system implementing a monotone RMW operation. The end results of this work specifically apply to implementations of (monotone) RMW operations that are based on switching networks, a recent class of concurrent, low-contention data structures that generalize counting networks (J. ACM 41(5) (1994) 1020–1048) (which implemented the traditional Fetch&Increment operation). These results are negative; they are shown through the Monotone Linearizability Lemma. In particular, the first lower bounds on size (the number of switches in the network) for any (non-trivial) switching network implementing a monotone RMW operation are derived. It is proven that if the network incurs low contention, then its size must be infinite, no matter whether the number of states of each switch is finite or infinite. Since Fetch&Increment is implementable with counting networks of finite-size (J. ACM 41(5) (1994) 1020–1048), these lower bounds imply a space complexity separation between Fetch&Increment and any monotone RMW operation in the model of switching networks. The presented lower bounds provide a mathematical explanation for the observed inability of researchers over the last thirteen years to extend counting networks, while keeping their finite-size, high-concurrency and low-contention, in order to perform tasks more complex than Fetch&Increment but yet as simple as Fetch&Add.

TCS Journal 2003 Journal Article

An efficient deterministic parallel algorithm for two processors precedence constraint scheduling

• Hermann Jung
• Maria Serna
• Paul Spirakis

We present here a new deterministic parallel algorithm for the two-processor scheduling problem. The algorithm uses only O(n3) processors and takes O(log 2n) time on a CREW PRAM. In order to prove the above bounds we show how to compute in NC the lexicographically first matching for a special kind of convex bipartite graphs.

TCS Journal 2003 Journal Article

Preface

• Shay Kutten
• Paul Spirakis

TCS Journal 1998 Journal Article

Preface

• Paul Spirakis

TCS Journal 1987 Journal Article

The parallel complexity of deadlock detection

• Paul Spirakis

When serially re-usable multi-unit resources are shared among many processes, each of which has exclusive control over some resource units, it is possible for deadlocks to happen. The work of Holt (1971) stated the problem of deadlock detection as a directed multigraph problem. In this paper we examine the possibility of existence of fast parallel algorithms for deadlock detection. Although many graph problems have efficient parallel solutions (in parallel polylogarithmic time, by using only a polynomial number of processors), we present strong evidence that this is not the case for the general deadlock detection problem. We show that the problem is complete in Punder log-space reductions and thus probably not efficiently parallelizable. Fortunately, when the problem is restricted (e. g. , single-unit requests of processes or single-unit resources), then it falls in NC. We present efficient parallel algorithms for the restricted versions of the deadlock detection problem.