Abstract

TBA

Abstract

TBA

Abstract

Planar Embedding is a drawing of a graph on the plane such that the edges do not intersect each other except at the vertices. We know that testing the planarity of a graph and computing its embedding (if it exists), can efficiently be computed, both sequentially [John E. Hopcroft and Robert Endre Tarjan, 1974] and in parallel [Vijaya Ramachandran and John H. Reif, 1994], when the entire graph is presented as input.

In the dynamic setting, the input graph changes one edge at a time through insertion and deletions and planarity testing/embedding has to be updated after every change. By storing auxilliary information we can improve the complexity of dynamic planarity testing/embedding over the obvious recomputation from scratch. In the sequential dynamic setting, there has been a series of works [David Eppstein et al., 1996; Giuseppe F. Italiano et al., 1993; Jacob Holm et al., 2018; Jacob Holm and Eva Rotenberg, 2020], culminating in the breakthrough result of polylog(n) sequential time (amortized) planarity testing algorithm of Holm and Rotenberg [Jacob Holm and Eva Rotenberg, 2020].

We study planar embedding through the lens of DynFO, a parallel dynamic complexity class introduced by Patnaik et al [Sushant Patnaik and Neil Immerman, 1997] (also [Guozhu Dong et al., 1995]). We show that it is possible to dynamically maintain whether an edge can be inserted to a planar graph without causing non-planarity in DynFO. We extend this to show how to maintain an embedding of a planar graph under both edge insertions and deletions, while rejecting edge insertions that violate planarity. Our main idea is to maintain embeddings of only the triconnected components and a special two-colouring of separating pairs that enables us to side-step cascading flips when embedding of a biconnected planar graph changes, a major issue for sequential dynamic algorithms [Jacob Holm and Eva Rotenberg, 2020; Jacob Holm and Eva Rotenberg, 2020].

This is a joint work with Samir Datta(CMI) and Anish Mukherjee (University of Warwick), that is to appear at MFCS 2023.

Abstract

Negotiations, introduced by Esparza et al., are a model for concurrent systems where computations involving a set of agents are described in terms of their interactions. In many situations, it is natural to impose timing constraints between interactions — for instance, to limit the time available to enter the PIN after inserting a card into an ATM. To model this, we introduce a real-time aspect to negotiations. In our model of local-timed negotiations, agents have local reference times that evolve independently. Inspired by the model of networks of timed automata, each agent is equipped with a set of local clocks. Similar to timed automata, the outcomes of a negotiation contain guards and resets over the local clocks.

As a new feature, we allow some interactions to force the reference clocks of the participating agents to synchronize. This synchronization con- straint allows us to model interesting scenarios. Surprisingly, it also gives unlimited computing power. We show that reachability is undecidable for local-timed negotiations with a mixture of synchronized and unsyn- chronized interactions. We study restrictions on the use of synchronized interactions that make the problem decidable.

Abstract

In the first part of the talk, I will introduce the field of COMSOC - computational social choice. Here, I will briefly explain various problems in the field such as fairly cutting chocolate cakes, fighting politicians, divorcing couples, dead grandma and her five children etc.. and how theoretical computer science gives solutions to these problems.

In the second part, I will talk about my work with my advisor Prajakta Nimbhorkar: "Insights into Proportional Allocation via Matchings". We will explore algorithmic solutions involving graph theory and matching polytopes to solve the problem of fairly dividing chores among roommates.

Prerequisites: A keen interest in computational problem-solving, a sweet tooth for cake, and an appreciation for a touch of drama.

Abstract

In this talk, we address the stable marriage problem in the presence of tied preferences and critical vertices. Each vertex possesses a preference ordering over its neighbors, which may include ties. Additionally, a subset of vertices is designated as critical, with the objective of producing a matching that accommodates as many critical vertices as possible. Such matchings are commonly referred to as critical matchings in the literature. In our setting, we aim to compute a matching that is both critical and optimal based on the preferences of the vertices.

Stability is a widely accepted notion of optimality in the context of two-sided preferences. There are simple examples that show that in the presence of critical vertices (even without ties in preferences), a matching that is both critical and stable may not exist. Popularity is another extensively studied notion of optimality in the two-sided preference list setting. However, in the presence of ties (even without critical vertices), the existence of a popular matching is not guaranteed. We, therefore, consider the notion of relaxed stability, which was introduced and studied by Krishnaa et al. (SAGT 2020).

We present a multi-level Gale and Shapley algorithm for computing critical matching, which is relaxed stable. This proves that in our setting, a critical matching that is relaxed stable always exists, although computing a maximum-sized relaxed stable matching turns out to be NP-hard. To achieve a good approximation to the size of maximum size critical relaxed stable matching, we combine our multi-level algorithm with Kiraly's algorithm. Our algorithm matches the best-known approximation guarantee of 3/2, which was known for the stable matching problem with ties (without critical vertices).

The talk is based on a recent work presented at WG2023 and is a joint work with Meghana Nasre and Prajakta Nimbhorkar. The talk will be self-contained.

Abstract

We consider an extension of the classical Total Store Order (TSO) semantics by expanding it to turn-based 2-player safety games. During her turn, a player can select any of the communicating processes and perform its next transition. We consider different formulations of the safety game problem depending on whether one player or both of them transfer messages from the process buffers to the shared memory. We give the complete decidability picture for all the possible alternatives

Abstract

We will talk about the definition of differential privacy and why it is now the standard mathematical definition used for privacy preserving data analysis by comparing it to some other definitions. We will look at some nice properties of differential privacy, and talk about a private algorithm (that was discovered 40 years before the definition of differential privacy) for getting people to answers truthfully in surveys on matters that one wouldn't like to disclose.