~~NOCACHE~~
/* DO NOT EDIT THIS FILE               */
/* THIS FILE WAS GENERATED             */
/* EDIT THE FILE "indexheader" INSTEAD */
/* OR ACCESS THE DATABASE              */

{{page>.:indexheader}}

\\ ==== Prochaines séances ====
[[seminaires:algocomp:index|Algorithmes et complexité]]\\
Lundi 5 mai 2025, 11 heures, Salle 3052\\
**Ryu Hayakawa** (Kyoto University) //Quantum and classical complexities in the homology of higher-order networks//
<button type="link" size="xs" collapse="b9-1511">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b9-1511" collapsed="true">
<well size="sm">
The algorithm and computational complexity of problems in higher-order networks i.e., higher-dimensional extensions of graphs, gather attention due to a successive application of algebraic topology especially in topological data analysis. Surprisingly, it has recently been revealed that the "homological problems" (e.g. find a high-dim hole) in higher-order networks possess quantum computational complexity. In this talk, I show exponential quantum computational speedup results for such a problem. I also discuss a class of higher-order networks where the problem falls into classical complexity.
</well>
</collapse>


[[seminaires:algocomp:index|Algorithmes et complexité]]\\
Mercredi 21 mai 2025, 11 heures, Salle 3052\\
**Isabella Ziccardi** (IRIF) //The Minority Dynamics//
<button type="link" size="xs" collapse="b9-1512">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b9-1512" collapsed="true">
<well size="sm">
We study the minority-opinion dynamics over a fully-connected network of $n$ nodes with binary opinions. Upon activation, a node receives a sample of opinions from a limited number of neighbors chosen uniformly at
random. Each activated node then adopts the opinion that is least common within the received sample. Unlike all other known consensus dynamics, we prove that this elementary protocol behaves in different ways, depending on whether activations occur sequentially or in parallel. Specifically, we show that its expected consensus time is exponential in n under asynchronous models, but, on the other hand, we show that it converges within $O(\log^2 n)$ rounds with high probability under synchronous models.

Our results shed light on the bit-dissemination problem, which was previously introduced to model the spread of information in biological scenarios. Specifically, our analysis implies that the minority-opinion dynamics is the
first memoryless solution to this problem, in the parallel passive-communication setting, achieving convergence within a polylogarithmic number of rounds. This, together with a known lower bound for sequential stateless dynamics, implies a parallel-vs-sequential gap for this problem that is nearly quadratic in the number $n$ of nodes. This is in contrast to all known results for problems in this area, which exhibit a linear gap between the
parallel and the sequential setting.
</well>
</collapse>


[[seminaires:algocomp:index|Algorithmes et complexité]]\\
Mercredi 18 juin 2025, 11 heures, Salle 3052\\
**Tal Roth** (Tel-Aviv University) //Non encore annoncé.//
\\


\\ ==== Séances passées ====
\\ === Année 2025 ===

{{page>.:algocomp2025}}

\\ === Année 2024 ===

{{page>.:algocomp2024}}

\\ === Année 2023 ===

{{page>.:algocomp2023}}

\\ === Année 2022 ===

{{page>.:algocomp2022}}

\\ === Année 2021 ===

{{page>.:algocomp2021}}

\\ === Année 2020 ===

{{page>.:algocomp2020}}

\\ === Année 2019 ===

{{page>.:algocomp2019}}

\\ === Année 2018 ===

{{page>.:algocomp2018}}

\\ === Année 2017 ===

{{page>.:algocomp2017}}

\\ === Année 2016 ===

{{page>.:algocomp2016}}