Invited Speakers

Andrew Chi-Chih Yao

Tsinghua University
(Joint Plenary Speakers of ICALP-LICS)

An Incentive Analysis of Some Bitcoin Fee Designs

Invited Talk: WED, 08.07.2020, 12:00-13:00 UTC+2 | When ist this is my timezone?

In the Bitcoin system, miners are incentivized to join the system and validate transactions through fees paid by the users. A simple “pay your bid” auction has been employed to determine the transaction fees. Recently, Lavi, Sattath and Zohar [Lavi et al., 2019] proposed an alternative fee design, called the monopolistic price (MP) mechanism, aimed at improving the revenue for the miners. Although MP is not strictly incentive compatible (IC), they studied how close to IC the mechanism is for iid distributions, and conjectured that it is nearly IC asymptotically based on extensive simulations and some analysis. In this paper, we prove that the MP mechanism is nearly incentive compatible for any iid distribution as the number of users grows large. This holds true with respect to other attacks such as splitting bids. We also prove a conjecture in [Lavi et al., 2019] that MP dominates the RSOP auction in revenue (originally defined in [Goldberg et al., 2006] for digital goods). These results lend support to MP as a Bitcoin fee design candidate. Additionally, we explore some possible intrinsic correlations between incentive compatibility and revenue in general. Read more …

Jérôme Leroux

Bordeaux University
(Joint Plenary Speakers of LICS-ICALP)

When Reachability Meets Grzegorczyk

Invited Talk: THU, 09.07.2020, 12:30-13:30 UTC+2 | When is this in my timezone?

Vector addition systems with states, or equivalently vector addition systems, or Petri nets are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and database systems, as well as chemical, biological and business processes. The central algorithmic problem is reachability: whether from a given initial configuration there exists a sequence of valid execution steps that reaches a given final configuration. The complexity of the problem has remained unsettled since the 1960s, and it is one of the most prominent open questions in the theory of computation. In this paper, we survey results about the reachability problem focusing on the general problem. We also show how a recent paper about the reachability problem in fixed dimension combined with vector addition systems with states weakly computing Grzegorczyk hierarchy provides a logspace reduction of the general reachability problem to the bounded case. This result, not included in the original paper due to a lack of space shows that the reachability problem can obviously be decided by a deterministic brute-force exploration. We provide perspectives based on this observation. Read more …

Mariangiola Dezani-Ciancaglini

A tale of intersection types

Invited Talk: SAT, 11.07.2020, 12:30-13:30 UTC+2 | When is this in my timezone?

Intersection types have come a long way since their introduction in the Seventies. They have been exploited for characterising behaviours of λ-terms and π-calculus processes, building λ-models, verifying properties of higher-order programs, synthesising code, and enriching the expressivity of programming languages. This paper is a light overview of intersection types and some of their applications. Read more …