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 …

Robert Krauthgamer

Sketching Graphs and Combinatorial Optimization

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

Graph-sketching algorithms summarize an input graph G in a manner that suffices to later answer (perhaps approximately) one or more optimization problems on G, like distances, cuts, and matchings. Two famous examples are the Gomory-Hu tree, which represents all the minimum st-cuts in a graph G using a tree on the same vertex set V(G); and the cut-sparsifier of Benczúr and Karger, which is a sparse graph (often a reweighted subgraph) that approximates every cut in G within factor 1±ε. Another genre of these problems limits the queries to designated terminal vertices, denoted T ⊆ V(G), and the sketch size depends on |T| instead of |V(G)|. The talk will survey this topic, particularly cut and flow problems such as the three examples above. Currently, most known sketches are based on a graph representation, often called edge and vertex sparsification, which leaves room for potential improvements like smaller storage by using another representation, and faster running time to answer a query. These algorithms employ a host of techniques, ranging from combinatorial methods, like graph partitioning and edge or vertex sampling, to standard tools in data-stream algorithms and in sparse recovery. There are also several lower bounds known, either combinatorial (for the graph representation) or based on communication complexity and information theory. Many of the recent efforts focus on characterizing the tradeoff between accuracy and sketch size, yet many intriguing and very accessible problems are still open, and I will describe them in the talk. Read more …

Virginia Vassilevska Williams

MIT
(Track A)

The graph diameter problem – approximation algorithms and fine-grained lower bounds

Invited Talk: WED, 08.07.2020, 15:30-16:30 UTC+2 | When is this in my timezone?

A fundamental graph parameter, the diameter of a graph G is the maximum shortest paths distance between any pair of vertices of G. The diameter can be computed exactly by computing all pairwise distances, i.e. by solving the All Pairs Shortest Paths (APSP) problem. In an n-vertex graph, there are n^2 pairs of vertices, so APSP already has a quadratic overhead just because all pairs are considered. Meanwhile, the diameter is a single number, so it is completely unclear why this quadratic overhead should be necessary, especially in sparse graphs in which the number of edges is linear in n. Nevertheless, the best known algorithms for computing the diameter in sparse graphs do run in quadratic time. Some faster approximation algorithms are known – for instance in linear time one can output an estimate of the diameter that is always within a factor of 2 (a so-called 2-approximation), and in n^{1.5}polylog(n) time one can output a 3/2-approximation for any sparse graph. Why can’t there be a near-linear time (1+epsilon)-approximation algorithm for Diameter for arbitrarily small epsilon? Fine-grained complexity provides an answer: the known 3/2-approximation algorithm is likely optimal, both in its approximation quality and in its running time, unless the Strong Exponential Time Hypothesis about the time complexity of Boolean Satisfiability fails. This talk will discuss much of what we know about the running time – approximation tradeoffs for the diameter problem.

Stefan Kiefer

Oxford University
(Track B)

How to play in infinite MDPs

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

Markov decision processes (MDPs) are a standard model for dynamic systems that exhibit both stochastic and nondeterministic behavior. For MDPs with finite state space it is known that for a wide range of objectives there exist optimal strategies that are memoryless and deterministic. In contrast, if the state space is infinite, the picture is much richer: optimal strategies may not exist, and optimal or epsilon-optimal strategies may require (possibly infinite) memory. Based on many examples, I am going to give an introduction to a collection of techniques that allow for the construction of strategies with little or no memory in countably infinite MDPs. Read more …