Abstracts (WarwickWeizmann 2019 workshop)
Sayan Bhattacharya (Warwick):
Dynamic algorithms for graph coloring
Abstract:
We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for (Δ + 1)vertex coloring and (2Δ  1)edge coloring in a graph with maximum degree Δ. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results.
 We present a randomized algorithm which maintains a (Δ+1)vertex coloring with O(log Δ) expected amortized update time.
 We present a deterministic algorithm which maintains a (1+o(1))Δvertex coloring with O(polylog Δ) amortized update time.
 We present a simple, deterministic algorithm which maintains a (2Δ  1)edge coloring with O(log Δ) worstcase update time.
Joint work with Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai.
Charis Efthymiou (Warwick):
Stochastic block model and the replica symmetric phase
Abstract:
We consider the community detection problem for the stochastic block model. This is a standard inference problem on networks which has gathered interest by many communities including computer science, biology, physics etc.
The focus of this talk is on estimating information theoretic lower bounds for the inference algorithms for this problem. We provide tight estimations for these bounds and we prove a conjecture originating from statistical physics, [Decelle et al.: Phys. Rev. E 2011]. Our approach is based on using the formalism from the socalled diluted meanfield models in physics. These are spin systems whose geometry of interactions is induced by a sparse random graph or hypergraph.
In a pathbreaking paper based on the nonrigorous “cavity method,” physicists predicted not only the existence of a replica symmetry breaking phase transition in such models but also sketched a detailed picture of the evolution of the Gibbs measure within the replica symmetric phase and its impact on important problems in combinatorics, computer science and physics [Krzakala et al.: PNAS 2007]. In this talk we rigorize this picture completely for a broad class of models, encompassing the Potts antiferromagnet on the random graph, the kXORSAT model and the diluted kspin model for even k. We prove a correspondence between the replica symmetry breaking phase and the information theoretic lower bound for the stochastic block model.
This is a joint work with A. CojaOghlan, N. Jaafari, M. Kang and T. Kapetanopoulos.
Tom Gur (Warwick):
Zero knowledge proofs in a quantum world
Abstract:
The seminal work of BenOr et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally by making the physical assumption that spatiallyisolated provers are playing independent strategies. In this talk I will discuss new techniques involving coding theory, cryptography, complexity, and sublineartime algorithms, that allow us to strengthen the foregoing result to hold even in light of quantum mechanics, which tells us that spatiallyisolated provers can realise nonlocal correlated strategies by sharing a quantum entangled state.
We provide the first construction of a zeroknowledge proof system that is sound against quantum entangled provers. Along the way, we introduce a framework that leverages local testability to "lift" classical protocols to quantum protocols in a blackbox manner. The talk is directed towards a broad theoretical computer science audience, and in particular, no familiarity with quantum computing and cryptography is required.
The talk is based on a FOCS 2018 and QIP 2019 work, joint with Alessandro Chiesa, Michael Forbes, and Nick Spooner, as well as on forthcoming works.
Shaofeng Jiang (Weizmann):
Coresets for clustering in graphs with bounded treewidth
Abstract:
We consider the coreset for the kmedian clustering problem on a graph G=(V, E). Let d be the shortest path metric of G. For some ksubset C of V, the objective for the kmedian clustering is defined as the sum of the distances to C from all points in V. An εcoreset S is a small (multi)subset of V, such that for any ksubset C, the clustering objective evaluated on S is within (1±ε) from that of V.
We present a sampling based epscoreset construction for graphs with bounded treewidth, whose size (the number of distinct elements) is O(k^{3}/ε^{2} tw(G)). The construction is based on the importance sampling framework that was proposed by [Feldman, Langberg, 11]. The importance sampling framework essentially reduces the coreset problem to bounding (some variation of) the shattering dimension of the metric space (V, d), and our technical contribution is bounding the shattering dimension for bounded treewidth graphs.
We start with an introduction to the FeldmanLangberg framework. Then we present how the bounded treewidth implies the bounded shattering dimension. We conclude with future directions. This talk is based on a workinprogress project.
Marcin Jurdziński (Warwick):
Universal trees and quasipolynomial bounds for parity games
Abstract:
Universal trees are a very basic combinatorial object: an ordered tree is (n, h)universal if every ordered tree of height at most h and with at most n leaves can be embedded into it.
Parity games play a fundamental role in the theory of logic and automata on infinite words and trees, and its applications to automated verification and synthesis of hardware and software, but they are at least as intriguing from the algorithmic point of view:
 deciding the winner in them is both in NP and in coNP, and whether there is a polynomialtime algorithm is a longstanding open problem;
 examples of hard parity games led to breakthroughs in our understanding of the complexity of policy iteration in Markov Decision Processes (Fearnley, 2010) and of randomized simplex pivoting rules (Hansen, Friedmann, Zwick, 2011); and
 in a recent breakthrough (Calude, Jain, Khoussainov, Li, and Stephan, 2017), the first quasipolynomial algorithm was discovered for solving parity games.
We argue that the size of universal trees is intimately linked to the worstcase running times of all currently known quasipolynomial algorithms for solving parity games. We give nearly matching quasipolynomial upper and lower bounds for the size of smallest universal trees, suggesting that we may need to develop new algorithmic tools to be able to solve parity games in time better than the current quasipolynomial stateoftheart.
The talk is based on several joint works with various subsets of: Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Ranko Lazić, Karoliina Lehtinen, Paweł Parys, and Thejaswini K. S..
Ranko Lazić (Warwick):
The reachability problem for Petri nets is not elementary (STOC 2019 best paper)
Abstract:
Petri nets, also known as vector addition systems, 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 for Petri nets is reachability: whether from the given initial configuration there exists a sequence of valid execution steps that reaches the 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 verification. Decidability was proved by Mayr in his seminal STOC 1981 work, and the currently best published upper bound is nonprimitive recursive Ackermannian of Leroux and Schmitz from LICS 2019. We establish a nonelementary lower bound, i.e. that the reachability problem needs a tower of exponentials of time and space. Until this work, the best lower bound has been exponential space, due to Lipton in 1976. The new lower bound is a major breakthrough for several reasons. Firstly, it shows that the reachability problem is much harder than the coverability (i.e., state reachability) problem, which is also ubiquitous but has been known to be complete for exponential space since the late 1970s. Secondly, it implies that a plethora of problems from formal languages, logic, concurrent systems, process calculi and other areas, that are known to admit reductions from the Petri nets reachability problem, are also not elementary. Thirdly, it makes obsolete the currently best lower bounds for the reachability problems for two key extensions of Petri nets: with branching and with a pushdown stack.
Merav Parter (Weizmann):
Low congestion cycle covers and their applications
Refined vertex sparsifiers of planar graphs
Abstract:
In this talk, we will study the following version of cut sparsification. Given a large edgeweighted network G with k terminal vertices, compress it into a smaller network H with the same terminals, such that every minimum terminal cut in H approximates the corresponding one in G, up to a factor q ≥ 1 that is called the quality. (The case q=1 is known also as a mimicking network). I will present new insights about the structure of minimum terminal cuts, leading to new results for cut sparsifiers of planar graphs.
The first result identifies a subset of the minimum terminal cuts, which we call elementary, that generates all the others. Consequently, H is a cut sparsifier if and only if it preserves all the elementary terminal cuts (up to this factor q).
The second and main result refines the known bounds in terms of γ = γ(G), which is defined as the minimum number of faces that are incident to all the terminals in a planar graph G. In particular, the number of elementary terminal cuts in G is O((2k/γ)^{2γ}) (compared to O(2^{k}) terminal cuts), and it obtains a mimicking network of size O(γ 2^{2γ} k^{4}), which is nearoptimal as a function of γ.
Pavel Veselý (Warwick):
Tight lower bound for comparisonbased quantile summaries
Abstract:
Quantiles, such as the median or percentiles, provide concise and useful information about the distribution of a collection of items, drawn from a linearly ordered universe. We study data structures, called quantile summaries, which keep track of all quantiles, up to an error of at most ε. That is, an εapproximate quantile summary first processes a stream of items and then, given any quantile query 0 ≤ ϕ ≤ 1, returns an item from the stream, which is a ϕ'quantile for some ϕ' = ϕ±ε. We focus on comparisonbased quantile summaries that can only compare two items and are otherwise completely oblivious of the universe.
The best deterministic comparisonbased quantile summary to date, by Greenwald and Khanna [ACM SIGMOD '01], stores at most O(1/ε · log εN) items, where N is the number of items in the stream. We prove that this space bound is optimal by providing a matching lower bound. Our result thus rules out the possibility of constructing a deterministic comparisonbased quantile summary in space f(ε)· o(log N), for any function f that does not depend on N.
Joint work with Graham Cormode.

Sayan Bhattacharya (Warwick)

Charis Efthymiou (Warwick)

Tom Gur (Warwick)

Shaofeng Jiang (Weizmann)

Marcin Jurdziński (Warwick)

Ranko Lazic (Warwick)

Merav Parter (Weizmann)

Havana Rika (Weizmann)

Pavel Veselý (Warwick)