Claire Mathieu

Claire Mathieu, a former student at the ENS and holder of a thesis in computer science from the Université Paris-Sud, is currently Director of Research at the CNRS. She has worked as a CNRS researcher at the ENS-Lyon and as a professor at various institutions: ENS (attached professor), Université Paris-Sud, École Polytechnique, Brown University (USA). Her research focuses on algorithmics, and in particular on the design of algorithms to find near-optimal solutions to problems that are difficult to solve exactly. Recently, she has been interested in modeling social networks, reconstructing hidden graphs, and graphs that can be drawn in the plane. In 2019, she was awarded the CNRS silver medal.

Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics

Cohen-Addad V., Klein P. N. et Mathieu C., « Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics », SIAM Journal on Computing, 2019, p. 644-667, https://doi.org/10.1137/17M112717X.
Effectiveness of Local Search for Geometric Optimization

Cohen-Addad V. et Mathieu C., « Effectiveness of Local Search for Geometric Optimization », 31st International Symposium on Computational Geometry SoCG 2015, 2015, p. 329-343.
A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing

Das A. et Mathieu C., « A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing », Algorithmica 73, 2015, p. 115-142, https://doi.org/10.1007/s00453-014-9906-4.
Linear programming relaxations of maxcut

Fernandez de la Vega W. et Kenyon-Mathieu C., « Linear programming relaxations of maxcut », SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 2007, p. 53-61
How to rank with few errors

Kenyon-Mathieu C. et Schudy W., « How to rank with few errors », STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, p. 95-103.
The Data Broadcast Problem with Non-Uniform Transmission Times

Kenyon C. et Schabanel N., « The Data Broadcast Problem with Non-Uniform Transmission Times », Algorithmica 35, 2003, p. 146-175, https://doi.org/10.1007/s00453-002-0990-5.
Carpooling in Social Networks

Fiat A., Karlin A. R, Koutsoupias E., Mathieu C. et Zach R., « Carpooling in Social Networks », in : Díaz, J., Kirousis, L., Ortiz-Gracia, L., Serna, M. (eds) Extended Abstracts Summer 2015, Trends in mathematics book series, vol. 6, 2017, p. 29-34, https://doi.org/10.1007/978-3-319-51753-7_5.
Convergence of Position Auctions under Myopic Best-Response Dynamics

Carry M., Das A., Edelman B., Giotis I., Heimerl K., Karlin A. R., Kominers S. D., Mathieu C. et Schwarz M., « Convergence of Position Auctions under Myopic Best-Response Dynamics », ACM Trans. Economics and Computation, vol. 2, n° 3, 2014, art. 9, https://doi.org/10.1145/2632226.
Improved Approximation Algorithms for Budgeted Allocations

Azar, Y., Birnbaum, B., Karlin, A.R., Mathieu, C. et Nguyen, C.T. « Improved Approximation Algorithms for Budgeted Allocations », In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A. et Walukiewicz, I. (eds) Automata, Languages and Programming. ICALP 2008. Lecture Notes in Computer Science, vol. 5125, https://doi.org/10.1007/978-3-540-70575-8_16.
Online multicast with egalitarian cost sharing

Charikar M., Karloff H. J., Mathieu C., Naor J., Saks M. E., « Online multicast with egalitarian cost sharing », SPAA'08: Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures, 2008, p. 70-76, https://doi.org/10.1145/1378533.1378544.
Dynamic TCP Acknowledgment and Other Stories about e/(e-1)

Karlin A. R., Kanyon C., Randall D., « Dynamic TCP Acknowledgment and Other Stories about e/(e-1) », Algorithmica 36, 2003, p. 209–224, https://doi.org/10.1007/s00453-003-1013-x.
Distance in the Forest Fire Model How far are you from Eve?

Kanade V., Levi R., Lotker Z., Mallmann-Trenn F., Mathieu C., « Distance in the Forest Fire Model How far are you from Eve? », Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016, p. 1602-1620, https://doi.org/10.1137/1.9781611974331.ch109
Homophily and the Glass Ceiling Effect in Social Networks

Avin C., Keller B., Lortker Z., Mathieu C., Peleg D., Pignolet Y. A., « Homophily and the Glass Ceiling Effect in Social Networks », ITCS 2015, 2015, p. 41-50, https://doi.org/10.1145/2688073.2688097.
On the discrete Bak-Sneppen model of self-organized criticality

Barbay J. et Kenyon C., « On the discrete Bak-Sneppen model of self-organized criticality » SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, 2001, p. 928-933.
Selection in the Presence of Noise: The Design of Playoff Systems

Adler M., Gemmel P., Harchol-Balter M., Karp R. M. et Kenyon C., « Selection in the Presence of Noise: The Design of Playoff Systems », SODA '94: Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms , 1994, p. 564-572.
Commitment under uncertainty: Two-stage stochastic matching problems

Katriel I., Kenyon-Mathieu C. et Upfal E., « Commitment under uncertainty: Two-stage stochastic matching problems », in Arge, L., Cachin, C., Jurdziński, T. et Tarlecki, A. (eds) Automata, Languages and Programming. ICALP 2007, Lecture Notes in Computer Science book series, vol. 4596, 2007, p. 171-182.
Matchings in lattice graphs

Kenyon C., Randall D. et Sinclair A., « Matchings in lattice graphs » STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing, 1998, p. 738-746, https://doi.org/10.1145/167088.167278.
On the Sum-of-Squares algorithm for bin packing

Csirik J., Johnson D. S., Kenyon C., Orlin J. B., Shor P. W. et Weber R., « On the Sum-of-Squares algorithm for bin packing », Journal of the ACM, vol. 53, n° 1, 2006, p. 1-65, https://doi.org/10.1145/1120582.1120583, [arXiv : 0210013].
Correlation Clustering with Noisy Input

Mathieu C. et Schudy W., « Correlation Clustering with Noisy Input », Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010, p. 712-728, https://doi.org/10.1137/1.9781611973075.58.
Near-Linear Query Complexity for Graph Inference

Kannan S., Mathieu C. et Zhou H., « Near-Linear Query Complexity for Graph Inference », ICALP 2015. Lecture Notes in Computer Science, vol. 9134, 2015, p. 773-784, https://doi.org/10.1007/978-3-662-47672-7_63, [arXiv : 1402.4037].
Recognizing Well-Parenthesized Expressions in the Streaming Model

Magniez F., Mathieu C. et Nayak A., « Recognizing Well-Parenthesized Expressions in the Streaming Model », SIAM Journal on Computing, vol 43, n° 6, 2014, p. 1880-1905, https://doi.org/10.1137/130926122.

Presentation

Chair

Claire Mathieu

Selected bibliography