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.
Presentation
Selected bibliography
-
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.
-
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.
-
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.
-
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
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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
-
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.
-
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.
-
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.
-
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.
-
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.
-
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].
-
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.
-
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].
-
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.