Biography and publications | Claire Mathieu - Computer Sciences and Digital Technologies

Biography

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.

Selected bibliography

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

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

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

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

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

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

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

Fiat A., Karlin A. R, Koutsoupias E., Mathieu C. and 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, pp. 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. and Schwarz M., "Convergence of Position Auctions under Myopic Best-Response Dynamics", ACM Trans. Economics and Computation, vol. 2, no. 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. and 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. and 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, pp. 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, pp. 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, pp. 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, pp. 41-50, https://doi.org/10.1145/2688073.2688097.
On the discrete Bak-Sneppen model of self-organized criticality

Barbay J. and 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. and 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, pp. 564-572.
Commitment under uncertainty: Two-stage stochastic matching problems

Katriel I., Kenyon-Mathieu C. and Upfal E., "Commitment under uncertainty: Two-stage stochastic matching problems", in Arge, L., Cachin, C., Jurdziński, T. and 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. and Sinclair A., "Matchings in lattice graphs" STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing, 1998, pp. 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. and Weber R., "On the Sum-of-Squares algorithm for bin packing", Journal of the ACM, vol. 53, no. 1, 2006, pp. 1-65, https://doi.org/10.1145/1120582.1120583,[arXiv: 0210013].
Correlation Clustering with Noisy Input

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

Kannan S., Mathieu C. and Zhou H., "Near-Linear Query Complexity for Graph Inference," ICALP 2015. Lecture Notes in Computer Science, vol. 9134, 2015, pp. 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. and Nayak A., "Recognizing Well-Parenthesized Expressions in the Streaming Model," SIAM Journal on Computing, vol 43, no 6, 2014, pp. 1880-1905, https://doi.org/10.1137/130926122.