Search
Now showing items 1-10 of 111
A distributed algorithm for gathering many fat mobile robots in the plane
(2013)
We revisit the problem of gathering autonomous robots in the plane. In particular, we consider non-transparent unit-disc robots (i.e., fat) in an asynchronous setting with vision as the only means of coordination and robots ...
Supporting increment and decrement operations in balancing networks
(1999)
Counting networks are a class of distributed data structures that support highly concurrent implementations of shared Fetch&Increment counters. Applications of these counters include shared pools and stacks, load balancing, ...
Efficiency of semisynchronous versus asynchronous networks
(1994)
The s-session problem is studied in asynchronous and semisynchronous networks. Processes are located at the nodes of an undirected graph G and communicate by sending messages along links that correspond to the edges of G. ...
A catalog of ∃ℝ-complete decision problems about Nash equilibria in multi-player games
(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016)
[Schaefer and Štefankovic, Theory of Computing Systems, 2015] provided an explicit formulation of ∃ℝ as the class capturing the complexity of deciding the Existential Theory of the Reals, and established that deciding, ...
∃ℝ-complete decision problems about symmetric nash equilibria in symmetric multi-player games
(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017)
We study the complexity of decision problems about symmetric Nash equilibria for symmetric multi-player games. These decision problems concern the existence of a symmetric Nash equilibrium with certain natural properties. ...
Complexity of rational and irrational Nash equilibria
(2011)
We introduce two new decision problems, denoted as ∃ RATIONAL NASH and ∃ IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ask, ...
The complexity of decision problems about nash equilibria in win-lose games
(2012)
We revisit the complexity of deciding, given a (finite) strategic game, whether Nash equilibria with certain natural properties exist
Efficient counting network
(1998)
Counting networks were introduced as a new class of concurrent, distributed, low contention data structures suitable for implementing shared counters. Their structure is similar to that of sorting networks. High-performance ...
Impossibility results for weak threshold networks
(1997)
It is shown that a weak threshold network (in particular, threshold network) of width w and depth d cannot be constructed from balancers of width p0, p1, . . . , pm-1, if w does not divide Pd, where P is the least common ...