Author name cluster

Jonas Schmidt

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

Highlights Conference 2023 Conference Abstract

Dynamic constant-time parallel graph algorithms with sub-linear work

Jonas Schmidt

The talk proposes dynamic parallel algorithms for connectivity and bipartiteness of undirected graphs that require constant-time and n^{1/2} times polylog(n) work on the (arbitrary) CRCW PRAM model. The work of these algorithms almost matches the work of the O(log n) time algorithm for Connectivity by Kopelowitz et al. (2018) on the EREW PRAM model and the time of the sequential algorithm for bipartiteness by Eppstein et al. (1997). In particular, it is shown that the sparsification technique, which has been used in both mentioned papers, can in principle also be used for constant time algorithms in the CRCW PRAM model, despite the logarithmic depth of sparsification trees. This talk presents yet unpublished joined work with Thomas Schwentick. Contributed talk given by Jonas Schmidt

Details

IJCAI Conference 2023 Conference Paper

Schelling Games with Continuous Types

Davide Bilò
Vittorio Bilò
Michelle Döring
Pascal Lenzner
Louise Molitor
Jonas Schmidt

In most major cities and urban areas, residents form homogeneous neighborhoods along ethnic or socioeconomic lines. This phenomenon is widely known as residential segregation and has been studied extensively. Fifty years ago, Schelling proposed a landmark model that explains residential segregation in an elegant agent-based way. A recent stream of papers analyzed Schelling's model using game-theoretic approaches. However, all these works considered models with a given number of discrete types modeling different ethnic groups. We focus on segregation caused by non-categorical attributes, such as household income or position in a political left-right spectrum. For this, we consider agent types that can be represented as real numbers. This opens up a great variety of reasonable models and, as a proof of concept, we focus on several natural candidates. In particular, we consider agents that evaluate their location by the average type-difference or the maximum type-difference to their neighbors, or by having a certain tolerance range for type-values of neighboring agents. We study the existence and computation of equilibria and provide bounds on the Price of Anarchy and Stability. Also, we present simulation results that compare our models and shed light on the obtained equilibria for our variants.

PDF Details DOI

Highlights Conference 2020 Conference Abstract

Work-sensitive Dynamic Complexity of Formal Languages

Jonas Schmidt

DynFO is the dynamic complexity class of all queries that can be main- tained by first-order dynamic programs with the help of auxiliary relations under insertions and deletions of tuples. If one tries to make the “DynFO approach” to maintaining queries relevant for practical considerations, the work that is needed to carry out the specified updates, hence the work of an algorithm (i. e. the sum of the number of operations of all processors) implementing them, is a crucial factor. In this talk, I will introduce a work-aware version of DynFO and present first results for the question which queries can be maintained in DynFO with little work – in this first investigation restricted to dynamic language membership queries.

Details