# Seminar of the Talgo team

## Efficient Plurality Consensus on the Complete Graph

4pm at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

Abstract:

Plurality consensus considers a network of n nodes, each having one of k opinions. Nodes execute a (randomized) distributed protocol to gain knowledge about opinions in their neighborhood, which might cause them to change their opinion. The goal is to find a protocol that, with high probability, causes all nodes to adopt the plurality (the opinion initially supported by the most nodes). A major open question has been whether there is a protocol for the complete graph that converges in polylogarithmic time and uses only polylogarithmic memory (per node). This paper answers this question affirmative.

We propose two plurality consensus protocols that require only an arbitrarily small constant multiplicative bias towards the plurality. Both assume a complete graph and realize communication via a random phone call model. The first protocol is very simple, and achieves plurality consensus within O(log k · log log n) rounds using log k + Θ(log log k) bits of memory. The second protocol achieves plurality consensus within O(log log n · log n) rounds using only log k + O(1) bits of memory. The latter result disproves a conjecture of Becchetti et al. (SODA 2015) implying that any protocol using log k + O(1) bits of memory has runtime at least linear in k in the worst case. At the heart of our protocols lies the usage of an undecided state, a technique introduced by Angluin et al.

## Approximate constraint satisfaction requires large LP relaxations

2:30 pm at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

Abstract:

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. In particular, we show that no polynomial-sized LP can achieve better than a 1/2-approximation for MAX-CUT, a 7/8-approximation for MAX-3SAT, or a 3/4-approximation for MAX-2SAT.

There has been a recent sequence of exciting lower bounds on the size of extended formulations for various polytopes that arise in combinatorial optimization. Unfortunately, these prior results are essentially based on one particular family of "high-complexity" matrices coming from the set disjointness problem. We show that for max-CSP problems, general polynomial-sized LPs are exactly as power as LPs arising from a constant number of rounds of the Sherali-Adams hierarchy. This allows us access to a wealth of non-trivial hard instances.

Joint work with Siu On Chan and Prasad Raghavendra.

## Byzantine Agreement with a Strong Adversary in Polynomial Expected Time

10am, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

Abstract: Byzantine agreement is a fundamental problem of distributed computing which involves coordination of players when a constant fraction are controlled by a malicious adversary. Each player starts with a bit, and the goal is for all good players to agree on a bit whose value is is equal to some good player's initial bit.

I'll present the first algorithm with polynomial expected time in the asynchronous message-passing model with a strong adversary. A strong adversary in the asynchronous model may corrupt players adaptively, may schedule message delivery with arbitrarily long delays unknown to the players, and has full knowledge of the state of all players.

Ben-Or's 1983 expected exponential time algorithm reduced the problem to a series of iterations in which the players attempt to agree on a global coinflip using their private coinflips. In our algorithm, players use the history of observed coinflips to individually detect statistically deviant behavior by adversarily controlled players, so as to eventually disregard their inputs to arrive at a global coinflip.

No knowledge of distributed computing will be assumed. One of my goals is to give a characterization of the model which is easy for non-experts to reason about.

This is joint work with Jared Saia.

## Faster algorithms for computing the straight skeleton of a polygon

10:30am, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

The straight skeleton of a polygon is defined as the trace of the vertices when the polygon shrinks, each edge moving at the same speed inwards in a perpendicular direction to its orientation. We present a new algorithm for computing the straight skeleton of a polygon. For a non-degenerate input polygon with n vertices, r of which being reflex vertices, the running time of our algorithm is O(n^{4/3+e}+n(log n)log r), for any e>0. It improves on previously known algorithms.

# Past seminars

## Mechanism Design for Data Science

11:15am, at ENS, 45 rue d'Ulm, Salle W (45 rue d'Ulm, main building, staircase B, go to 3rd floor, then follow the signs "Toits du DMA": go up one more level using the other staircase).

The promise of data science is that system data can be analyzed and its understanding can be used to improve the system (i.e., to obtain good outcomes). For this promise to be realized, the necessary understanding must be inferable from the data. Whether or not this understanding is inferable often depends on the system itself. Therefore, the system needs to be designed to both obtain good outcomes and to admit good inference. This talk will explore this issue in a mechanism design context where the designer would like use past bid data to adapt an ction mechanism to optimize revenue.

Data analysis is necessary for revenue optimization in auctions, but revenue optimization is at odds with good inference. The revenue-optimal auction for selling an item is typically parameterized by a reserve price, and the appropriate reserve price depends on how much the bidders are willing to pay. This willingness to pay could be potentially be learned by inference, but a reserve price precludes learning anything about willingness-to-pay of bidders who are not willing to pay the reserve price. The auctioneer could never learn that lowering the reserve price would give a higher revenue (even if it would). To address this impossibility, the auctioneer could sacrifice revenue-optimality in the initial auction to obtain better inference properties so that the auction's parameters can be adapted to changing preferences in the future. In this talk, I will develop a theory for optimal auction design subject to good inference.

Joint work with Shuchi Chawla and Denis Nekipelov.

## Low Tree-depth Decompositions (With Applications to Algorithms, Homomorphisms, and Limits)

10:30am, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

The tree-depth of a graph G is the minimum height of a forest F such that every edge of G connects vertices that have an ancestor-descendant relationship in F. This parameter is minor-monotone and it is closely related to other measures in combinatorics such as vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs, the star height of regular languages, and the quantifier rank of formulas.

For non-negative integer p, a low tree-depth decomposition with parameter p of a graph G is a partition V_1 ,...,V_k of its vertex set such that every i <= p parts induce a subgraph with tree-depth at most i. The minimum number of parts k for which a low tree-depth decomposition with parameter p of G exists is chi_p (G). This minor-monotone graph invariant is related to the densities of the shallow minors (topological minors, or immersions) of the graph G.

In this talk, we survey several theoretical and algorithmic applications of low-tree depth decompositions --- like distance coloring, taxonomy of graph classes, restricted homomorphism dualities, and first-order model-checking in classes of sparse graphs, as well as connections with recent construction of explicit limit objects for trees and graphs with bounded tree-depth.

This is joint work with Jaroslav Nesetril.

## Epsilon-biased sets with just a little randomness

10am, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

Subsets of F_2^n that are epsilon-biased, meaning that the parity of any set of bits is even or odd with probability epsilon close to 1/2, are useful tools in derandomization. They also correspond to optimal error-correcting codes, i.e. meeting the Gilbert-Varshamov bound, with distance close to n/2.

A simple randomized construction shows that such sets exist of size O(n/eps^2); recently, Ben-Aroya and Ta-Shma gave a deterministic construction of size O((n/eps^2)^(5/4)). I will review deterministic constructions of Alon, Goldreich, Haastad, and Peralta of sets of size O(n/eps^3) and O(n^2/eps^2), and discuss the delightful pseudorandom properties of the Legendre symbol along the way.

Then, rather than derandomizing these sets completely in exchange for making them larger, we will try moving in a different direction on the size-randomness plane, constructing sets of optimal size O(n/eps^2) with as few random bits as possible. The naive randomized construction requires O(n^2/eps^2) random bits. I will show that this can be reduced to O(n log(n/eps)) random bits. Like Alon et al., our construction uses the Legendre symbol and Weil sums, but in a different way to control high moments of the bias. I'll end by saying a few words about Ramsey graphs and random polynomials.

## Speed scaling scheduling and convex programming

11am, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

We consider scheduling problems on speed-scalable processors so as to minimize the energy consumption. Especially, we focus on designing efficient algorithms for this class of problems by formulating them as convex programs. We introduce this approach via the classical YDS algorithm [Yao, Demers and Senker; FOCS 1995] and its optimality proof by using the Karush-Kuhn-Tucker (KKT) conditions for convex programs [Bansal, Kimprel, Pruhs; FOCS 2004; JACM 2007]. Then we consider an Open-Shop scheduling problem in the speed-scaling setting and we present an optimal algorithm by applying the primal-dual method in the context of convex programming.

## The diameters of associahedra

10:30am, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

Abstract: Associahedra are polytopes that were independently discovered within different areas of mathematics such as algebraic topology, discrete geometry, and combinatorial optimization. The boundary complex of the d-dimensional associahedron can be indifferently represented using bracketed words of d+2 letters, triangulations of convex polygons with d+3 vertices, or size d+1 binary trees.

In 1988, Daniel Sleator, Robert Tarjan, and William Thurston have shown that the diameter of this polytope is at most 2d-4 when d is larger than 9 and that this bound holds with equality when d is large enough. They further conjecture that "large enough" means "greater than 9".

The recently announced proof of this conjecture will be sketched in this talk. As a preliminary, the associahedra will be described as well as a selection of the many problems these polytopes are related to.

## Local-search techniques for geometric optimization

10:30am, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

Abstract: Local-search is an intuitive approach towards solving combinatorial optimization problems: start with any feasible solution, and try to improve it by local improvement steps. Like other greedy approaches, it can fail to find the global optimum by getting stuck on a local maximum.

There have been a number of papers in the past few years which show the utility of local-search for geometric problems. I will survey the ideas and techniques behind them. In particular, I will describe a simple local-search (1+eps)-approximation algorithm for the geometric set cover problem (by extension, for computing minimum hitting sets) for a wide-range of geometric objects. For example, this gives the first PTAS for the problem of covering a given set of points by a minimum-sized subset of disks from a given set of disks in the plane. The main technique is to construct an auxiliary planar graph on the geometric objects, and then follow the effect of local-search on this graph.

Joint work with Saurabh Ray. Slides of the talk

## Computing and extending continuous maps: polynomiality and undecidability

10:30am, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

Abstract: We consider several basic problems in algebraic topology from a point of view of computational complexity.

A central theme in algebraic topology is to understand the structure of all (continuous) maps from X to Y, for given topological spaces X and Y. For topological purposes, maps are usually considered equivalent if they are homotopic, i.e., if they can be continuously deformed into one another. Thus, the object of interest is [X,Y], the set of homotopy classes of maps from X to Y. A special case of this homotopy classification problem are the higher homotopy groups \pi_k(Y) of a space Y which, roughly speaking can be identified with [S^d,Y].

A closely related question is the extension problem, which asks whether a map f from a subspace A of X into Y can be extended (continuously) over all of X. For example, the famous Brouwer Fixed-Point Theorem states that the identity map from the k-sphere to itself cannot be extended to the (k+1)-dimensional disk.

In full generality, the above problems are undecidable, as follows from classical undecidability results by Adyian--Rabin and Novikov concerning the fundamental group \pi_1(Y), i.e., concerning homotopy classification and extendability for maps from the circle S^1 into Y.

Thus, we study the problem under the assumption that the target Y is (k-1)-connected for some k\geq 2, i.e., that the first (k-1) homotopy groups of Y vanish; informally, this means that "Y has no holes up to dimension k-1" (a basic example of such a Y is the sphere S^k).

We show that, under this assumption, [X,Y] can be computed if the dimension of X is at most 2k-2, and the extension problem can be solved if the dimension of X is at most 2k-1. Moreover, if k is fixed, the algorithms run in polynomial time.

On the other, we show that, for \dim X=2k, the extension problem becomes undecidable, even for fixed k.

We also discuss related results concerning homotopy groups.

This is joint work with M. Cadek, M. Krcal, J. Matousek, F. Sergeraert, and L. Vokrinek.

## Topology and Ramsey theory of families of convex bodies

10:30am, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

The classical Erdos-Szekeres theorem claims that there exists a function M_points(n), such that among any M points in the plane in general position, at least n of them are in convex position (i.e. conv (F) \neq conv (F-x) for all x \in F).

In the 80's Goodman and Pollack generalized the theorem to the realm of pseudoline arrangements and made a conjecture on the growth of the analogous Ramsey function M_{pseudo lines}. Still in the 80's Bisztriczky and Fejes Toth generalized this theorem to the realm of families of disjoint convex bodies and made a conjecture on the growth of the analogous Ramsey function M_{disjoint}. Then around twelve years ago Pach and Toth generalized this theorem to the realm of non crossing convex bodies and conjectured that the theorem holds for families of k-crossing convex bodies. The upper bounds on M_{disjoint} and M_{non crossing} were improved a couple of times in the last 20 years.

Using the concept of order type, we show that M_{disjoint} \leq M_{pseudo lines}=M_{noncrossing} and improve all the known upper bounds for these functions. We also prove the Pach-Toth conjecture.

The concept of order type generalizes the well known concept for point sets in euclidean space. I will briefly discuss connections to oriented matroid theory. In a celebrated result, Mnev constructed order types with realization spaces with arbitrary homotopy type. We begin the study of realization spaces of order types by endowing families of convex bodies with the Hausdorff distance. Our results in this direction generalize theorems of Levi and Mnev.

If time permits, I will discuss yet another generalization of the Erdos-Szekeres theorem and a connection to the big circle conjecture of Angel, Holroyd, Romik and Virag via the metric geometry of realization spaces.

These results are joint work with Andreas Holmsen and Michael Dobbins.

## Proportional Contact Representation of Planar Graphs

2pm, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in linear time.

We also describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. However, to compute the exact representation from the area-universal layout required numerical iteration, or can be approximated with a hill-climbing heuristic.

## Thursday, March 15, 2012: Jeff Erickson (U. of Illinois at Urbana-Champaign, USA, and IST, Vienna, Austria) and Arnaud de Mesmay (ENS, Paris)

Room Pasteur. Enter the 45, rue d'Ulm through the lodge, then go immediately to your right. Enter the door labeled "Pavillon Pasteur", in the Philosophy Department, walk in the corridor, find the stairs to your right, go one level up.

### At 2pm: Jeff Erickson, Topological hexahedral meshing of multiply-connected domains

In the mid-1990s, Thurston and Mitchell proved that any quadrilateral mesh of the sphere with an even number of faces can be extended to a topological hexahedral mesh of the ball. I will prove the following natural generalization of Thurston and Mitchell's result to higher-genus surfaces, which surprisingly seems to be new. A quadrilateral mesh of any closed surface embedded in R^3 can be extended to a compatible hexahedral mesh of the interior if and only if (1) the surface mesh has an even number of faces, and (2) the system of curves dual to the surface mesh has trivial Z_2-homology in the interior body.

### Around 3:15pm: Arnaud de Mesmay, Testing graph isotopy on surfaces

In the study of graphs embedded on surfaces, the notion of graph isotopy is a natural variation of the well known homotopy of paths or cycles: We say that two graphs are isotopic if there exists a continous deformation between them. In this work, we investigate the following problem : Given two embeddings of the same abstract graph on a surface, decide whether they are isotopic.

We provide efficient algorithms to solve this problem in two models. In the first one the embeddings are described by their arrangements with a cellularly embedded graph on the surface; in the second one they are piecewise-linear embeddings in the plane minus a finite set of points. The main tools we use are the existing algorithms to test homotopy, which we use as a subroutine, and a surgical approach inspired by the theory of mapping class groups. As a by-product, we reprove the following mathematical characterization, first observed by Ladegaillerie: Two graph embeddings are isotopic if and only if they are homotopic and congruent by an oriented homeomorphism.

This is joint work with Éric Colin de Verdière, to appear at SoCG 2012.

## Ultra-Fast Rumor Spreading on Social Networks

11am, at ENS, 45 rue d'Ulm, room U/V (Aile Rataud, 2nd basement floor, see map).

We analyze the popular push-pull protocol for spreading rumors in networks. Initially, a single node knows of a rumor. In each succeeding round, every node chooses a random neighbor, and the two nodes share the rumor if one of them is already aware of it. We present the first theoretical analysis of this protocol on random graphs that have a power law degree distribution with an arbitrary exponent beta > 2.

Our main findings reveal a dichotomy in the performance of the protocol that depends on the exponent of the power law. More specifically, we show that if 2 < beta < 3, then the rumor spreads to almost all nodes in Theta(log log n) rounds with high probability. This is exponentially faster than all previously known upper bounds for the push-pull protocol established for various classes of networks. On the other hand, if beta > 3, then Omega(log n) rounds are necessary.

This is joint work with Nikolaos Fountoulakis and Konstantinos Panagiotou.

## The maximum number of faces of the Minkowski sum of two convex polytopes

2pm, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

Abstract: We derive tight expressions for the maximum values of the number of $k$-faces, $0\le k\le d-1$, of the Minkowski sum $P_1\oplus P_2$ of two $d$-dimensional convex polytopes $P_1$ and $P_2$, as a function of the number of vertices of the polytopes.

For even dimensions $d\ge 2$, the maximum values are attained if $P_1$ and $P_2$ are cyclic $d$-polytopes with disjoint vertex sets. For odd dimensions $d\ge 3$, the maximum values are attained if $P_1$ and $P_2$ are $\lfloor d/2\rfloor$-neighborly $d$-polytopes, whose vertex sets are chosen appropriately from two distinct $d$-dimensional moment-like curves.

This is joint work with Eleni Tzanaki.

References:

## Tracing Curves on Triangulated Surfaces

at 2pm, at ENS, 45 rue d'Ulm, salle des Hauts du DI. Access modified: Enter the main building through the main entrance; in the hall ("Aquarium"), take the staircase on the left ("Headmistress' staircase"), 3rd floor, door to the right.

Abstract: Let S be a triangulated surface, possibly with boundary, composed of n triangles. A simple path or cycle in S is normal if it avoids every vertex of S and it does not cross any edge of S twice in a row. We describe a simple algorithm to trace any normal curve in S in O(n^2\log X) time, where X is the total number of times the curve crosses edges of S. In particular, our algorithm runs in polynomial time even when the number of crossings is exponential in n. Our tracing algorithm computes a new cellular decomposition of S with complexity O(n); the traced curve appears as a simple path or cycle in the 1-skeleton of the new decomposition.

Our tracing strategy implies several fast algorithms for (multi)curves represented by normal coordinates. For example, we can count the components of a normal curve, determine whether two disjoint normal curves are isotopic, or determine whether a normal curve disconnects two given points on the surface, all in O(n^2\log X) time. Our algorithms are competitive with and conceptually simpler than earlier algorithms by Schaefer, Sedgwick, and Stefankovic [COCOON 2002] based on word equations and text compression.

Our algorithm can also be used to trace simple geodesic paths in piecewise-linear surfaces, represented by a set of Euclidean triangles with pairs of equal-length edges identified. For example, given a starting point and a direction, in the local coordinate system of one of the triangles, we can locate the first point of self-intersection of the resulting geodesic path in O(n^2\log X) time.

This is unpublished joint work with my PhD student Amir Nayyeri. The talk will be self-contained; no prior exposure to computational topology is necessary.

## Unknot recognition, linear programming and the elusive polynomial time algorithm

at 11am, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor)

Abstract: What do practical tools such as integer and linear programming have to do with theoretical problems such as unknot recognition and the Poincaré conjecture? In this talk we explore new approaches to old and difficult computational problems from geometry and topology: how to tell whether a loop of string is knotted, or whether a 3-dimensional space has no interesting topological features. Although the best known algorithms for these problems run in exponential time, there is increasing evidence that a polynomial time solution might be possible. We outline several promising approaches in which linear programming and integer programming play a starring role.

Slides of the talk.

Webmaster: webdidiensfr.