## 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 ...