Agenda
janvier
-
14:0015:00
A central concept in social choice theory is that of a Condorcet winner: an outcome that defeats every alternative in a pairwise majority vote. While compelling, this notion is famously fragile, as Condorcet’s paradox shows that such a winner need not exist at all. This tension between desirability and nonexistence motivates much of modern voting theory.
In this talk, we explore how these ideas arise in matching problems, where voters’ preferences over potential matches induce an election over all possible matchings. The appropriate analogue of a Condorcet winner in this setting is a popular matching, defined via pairwise elections between matchings that account carefully for ties in preferences. As in classical social choice, popular matchings are highly appealing when they exist, but unfortunately, they often do not.
To address this, we study a natural relaxation: instead of a single winning matching, we allow a set of matchings that collectively defeats any alternative matching. This leads to the notion of the popular dimension, defined as the minimum size of such a winning set, in the worst case, for a given class of matching problems. We will present algorithmic results and open questions on the popular dimension for three classical settings: the house allocation problem, the marriage problem, and the roommates problem.
Joint work with Frank Connor, Louis-Roy Langevin, Ndiamé Ndiaye, Rohit Vasishta and Adrian Vetta.
(Agnes Totschnig) [MIT]
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .FrançaisLaBRI/178 -
11:0012:00
Jonas Sénizergues
Title: Self-stabilizing Minimal Clique Decomposition with Byzantine Fault tolerance
Abstract:
In distributed systems, a clique decomposition of the communication graph (i.e. a partition of the vertices such that every part of the partition induce a clique in the graph) can provide a natural way to structure the communication graph into fully connected groups. In this work, we aim to provide a way to compute a minimal clique decomposition in asynchronous networks in spite of both transient and byzantine faults happening in the network while keeping memory usage low. We rely on self-stabilization to handle transcient faults, and use containment to guarantee that the provided solution is good as long as we are far enough from the malicious byzantine nodes.
FrançaisLaBRI 178
février
-
11:0012:00
Jonathan Narboni
Title: Lower Bound for Constant-Size Local Certification
Abstract:
Given a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct. The quality of a certification is measured by the size of its labels: the smaller, the better. This notion plays a central role in self-stabilization, because the size of the certification is a lower bound (and often an upper bound) on the memory needed for silent self-stabilizing construction of distributed data structures.
When it comes to the size of the certification labels, one can identify three important regimes: the properties for which the optimal size is polynomial in the number of vertices of the graph, the ones that require only polylogarithmic size, and the ones that can be certified with a constant number of bits. The first two regimes are well studied, with several upper and lower bounds, specific techniques, and active research questions. On the other hand, the constant regime has never been really explored.
The main contribution of this paper is the first non-trivial lower bound for this low regime. More precisely, we show that by using certification on just one bit (a binary certification), one cannot certify k-colorability for k≥3. To do so, we develop a new technique, based on the notion of score, and both local symmetry arguments and a global parity argument. We hope that this technique will be useful for establishing stronger results.
We complement this result with an upper bound for a related problem, illustrating that in some cases one can do better than the natural upper bound.
FrançaisLaBRI 178 -
14:0015:00
TBA
FrançaisLaBRI -
10:4511:45
Tensor networks (TNs) offer powerful algorithms for simulating quantum systems, but struggle to represent states with high entanglement. In contrast, quantum computers naturally accommodate entanglement, though developing efficient quantum algorithms remains an active area of research. Integrating TNs with quantum computing has emerged as a promising strategy to overcome limitations inherent to both classical and quantum approaches. In this talk, we will cover two examples of hybrid TN/quantum algorithms. First, we demonstrate how TNs can enhance the simulation of quantum dynamics on noisy quantum devices. In particular, we use a TN algorithm to compress quantum circuits and show that this approach significantly reduces noise requirements to reach a practical advantage on noisy hardware. Second, we explore how TNs can assist in preparing approximate ground states on quantum computers by optimizing parameterized quantum circuits. We show that carefully selecting TN algorithms enables scaling to large qubit systems and that pre-optimizing circuits offers a promising strategy to avoid barren plateaus by providing warm-start initialization. Finally, we analyze the classical simulation costs of this approach and identify scenarios where quantum computers exhibit favorable scaling.
FrançaisLaBRI