Last update: May 2023
To appear
- Allamigeon, X., Gaubert, S. & Meunier, F. (2023). Tropical complementarity problems and Nash equilibria. SIAM Journal on Discrete Mathematics.
Journals
- Allamigeon, X., Katz, R. D. & Strub, P.-Y. (2022). Formalizing the Face Lattice of Polyhedra. Logical Methods in Computer Science, Volume 18, Issue 2.
- Allamigeon, X., Boyet, M. & Gaubert, S. (2021). Piecewise Affine Dynamical Models of Timed Petri Nets – Application to
Emergency Call Centers. Fundamenta Informaticae, Volume 183, Issues 3-4: Petri Nets 2020.
- Allamigeon, X., Benchimol, P., Gaubert, S. & Joswig, M. (2021). What Tropical Geometry Tells Us about the Complexity of Linear Programming. SIAM Review, 63(1), 123–164. SIAM SIGEST award.
- Gaubert, S., Akian, M., Allamigeon, X., Boyet, M., Colin, B., Grohens, T., … Carli, P. (2020). Understanding and monitoring the evolution of the Covid-19 epidemic from medical emergency calls: the example of the Paris area. Comptes Rendus. Mathématique, 358(7), 843–875.
- Allamigeon, X., Gaubert, S. & Skomra, M. (2020). Tropical Spectrahedra. Discrete & Computational Geometry, 63(3), 507–548.
- Allamigeon, X. & Katz, R. D. (2019). A Formalization of Convex Polyhedra Based on the Simplex Method. Journal of Automated Reasoning, 63(2), 323–345.
- Allamigeon, X., Gaubert, S. & Skomra, M. (2018). Solving generic nonarchimedean semidefinite programs using stochastic game algorithms. Journal of Symbolic Computation, 85, 25–54.
- Allamigeon, X., Benchimol, P., Gaubert, S. & Joswig, M. (2018). Log-Barrier Interior Point Methods Are Not Strongly Polynomial. SIAM Journal on Applied Algebra and Geometry, 2(1), 140–178.
- Allamigeon, X., Gaubert, S., Goubault, E., Putot, S. & Stott, N. (2017). A Fast Method to Compute Disjunctive Quadratic Invariants of Numerical Programs. ACM Trans. Embed. Comput. Syst., 16(5s), 166:1–166:19. Special issue for EMSOFT 2017.
- Allamigeon, X. & Katz, R. D. (2017). Tropicalization of facets of polytopes. Linear Algebra and its Applications, 523, 79–101.
- Allamigeon, X., Bœuf, V. & Gaubert, S. (2017). Stationary solutions of discrete and continuous Petri nets with priorities. Performance Evaluation, 113, 1–12.
- Allamigeon, X., Gaubert, S., Stott, N., Goubault, É. & Putot, S. (2016). A Scalable Algebraic Method to Infer Quadratic Invariants of Switched Systems. ACM Trans. Embed. Comput. Syst., 15(4), 69:1–69:20.
- Allamigeon, X., Benchimol, P., Gaubert, S. & Joswig, M. (2015). Tropicalizing the simplex algorithm. SIAM Journal on Discrete Mathematics, 29(2), 751–795.
- Magron, V., Allamigeon, X., Gaubert, S. & Werner, B. (2015). Formal Proofs for Nonlinear Optimization. Journal of Formalized Reasoning, 8(1).
- Allamigeon, X., Benchimol, P., Gaubert, S. & Joswig, M. (2014). Combinatorial Simplex Algorithms Can Solve Mean Payoff Games. SIAM Journal on Optimization, 24(4), 2096–2117.
- Magron, V., Allamigeon, X., Gaubert, S. & Werner, B. (2014). Certification of real inequalities: templates and sums of squares. Mathematical Programming, 1–30.
- Allamigeon, X., Fahrenberg, U., Gaubert, S., Katz, R. D. & Legay, A. (2014). Tropical Fourier–Motzkin elimination, with an application to real-time verification. International Journal of Algebra and Computation, 24(05), 569–607.
- Allamigeon, X. (2014). On the Complexity of Strongly Connected Components in Directed Hypergraphs. Algorithmica, 69(2).
- Allamigeon, X. & Katz, R. D. (2013). Minimal external representations of tropical polyhedra. Journal of Combinatorial Theory, Series A, 120(4), 907–940.
- Allamigeon, X., Gaubert, S. & Goubault, E. (2013). Computing the Vertices of Tropical Polyhedra using Directed Hypergraphs. Discrete & Computational Geometry, 49(2), 247–279.
- Allamigeon, X., Gaubert, S. & Katz, R. D. (2011). The number of extreme points of tropical polyhedra. Journal of Combinatorial Theory, Series A, 118(1), 162–189.
- Allamigeon, X., Gaubert, S. & Katz, R. D. (2011). Tropical polar cones, hypergraph transversals, and mean payoff games. Linear Algebra and its Applications, 435(7), 1549–1574.
- Allamigeon, X. & Hymans, C. (2008). Static Analysis by Abstract Interpretation: Application
to the Detection of Heap Overflows. Journal in Computer Virology, 4(1), 5–23.
Conferences
- Allamigeon, X., Canu, Q. & Strub, P.-Y. (2023). A Formal Disproof of Hirsch Conjecture. In Proceedings of the 12th ACM SIGPLAN International Conference on Certified Programs and Proofs (pp. 17–29). New York, NY, USA: Association for Computing Machinery.
- Allamigeon, X., Dadush, D., Loho, G., Natura, B. & Végh, L. A. (2022). Interior point methods are not worse than Simplex. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (pp. 267–277). Los Alamitos, CA, USA: IEEE Computer Society.
- Allamigeon, X., Gaubert, S., Katz, R. D. & Skomra, M. (2022). Universal complexity bounds based on value iteration and application to entropy games. In Automata, Languages, and Programming - 49th International Colloquium, ICALP 2022, Paris, France, July 4-8, 2022, Proceedings. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
- Allamigeon, X., Gaubert, S. & Vandame, N. (2022). No self-concordant barrier interior point method is strongly polynomial. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC’22). New York, NY, USA: Association for Computing Machinery.
- Allamigeon, X., Boyet, M. & Gaubert, S. (2022). Computing Transience Bounds of Emergency Call Centers: a Hierarchical Timed Petri Net Approach. In L. Bernardinello & L. Petrucci (Eds.), Proceedings of the 43rd International Conference on Applications and Theory of Petri Nets and Concurrency (PETRI NETS 2022) (Vol. 13288, pp. 90–112). Cham: Springer International Publishing.
- Akian, M., Allamigeon, X., Boyet, M. & Gaubert, S. (2020). A Convex Programming Approach to Solve Posynomial Systems. In A. M. Bigatti, J. Carette, J. H. Davenport, M. Joswig, & T. de Wolff (Eds.), Proceedings of the International Congress on Mathematical Software (ICMS 2020) (pp. 241–250). Cham: Springer International Publishing.
- Allamigeon, X., Katz, R. D. & Strub, P.-Y. (2020). Formalizing the Face Lattice of Polyhedra. In N. Peltier & V. Sofronie-Stokkermans (Eds.), Proceedings of the 10th International Joint Conference on Automated Reasoning (IJCAR 2020) (pp. 185–203). Cham: Springer International Publishing.
- Allamigeon, X., Boyet, M. & Gaubert, S. (2020). Piecewise Affine Dynamical Models of Timed Petri Nets – Application to Emergency Call Centers. In R. Janicki, N. Sidorova, & T. Chatain (Eds.), Proceedings of the 41st International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets 2020) (pp. 260–279). Cham: Springer International Publishing.
- Allamigeon, X., Gaubert, S., Katz, R. D. & Skomra, M. (2018). Condition numbers of stochastic mean payoff games and what they say about nonarchimedean semidefinite programming. In 23rd International Symposium on Mathematical Theory of Networks and Systems (pp. 160–167).
- Allamigeon, X. & Katz, R. D. (2017). A Formalization of Convex Polyhedra Based on the Simplex Method. In M. Ayala-Rincón & C. A. Muñoz (Eds.), Interactive Theorem Proving: 8th International Conference, ITP 2017, Brasília, Brazil, September 26–29, 2017, Proceedings (pp. 28–45). Cham: Springer International Publishing.
- Allamigeon, X., Gaubert, S. & Skomra, M. (2017). The tropical analogue of the Helton–Nie conjecture is true. In International Conference on Effective Methods in Algebraic Geometry, MEGA 2017.
- Allamigeon, X., Bœuf, V. & Gaubert, S. (2016). Stationary solutions of discrete and continuous Petri nets with priorities. In Proceeedings of the 10th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2016. Taormina, Italy.
- Allamigeon, X., Gaubert, S. & Skomra, M. (2016). Solving Generic Nonarchimedean Semidefinite Programs Using Stochastic Game Algorithms. In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2016 (pp. 31–38). New York, NY, USA: ACM.
- Allamigeon, X., Gaubert, S., Goubault, E., Putot, S. & Stott, N. (2015). A scalable algebraic method to infer quadratic invariants of switched systems. In Proceedings of the 12th International Conference on Embedded Software, EMSOFT 2015 (pp. 75–84). IEEE Press. Best paper award.
- Allamigeon, X., Bœuf, V. & Gaubert, S. (2015). Performance Evaluation of an Emergency Call Center: Tropical Polynomial Systems Applied to Timed Petri Nets. In S. Sankaranarayanan & E. Vicario (Eds.), Formal Modeling and Analysis of Timed Systems (Vol. 9268, pp. 10–26). Springer International Publishing.
- Allamigeon, X., Benchimol, P. & Gaubert, S. (2014). The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average. In J. Esparza, P. Fraigniaud, T. Husfeldt, & E. Koutsoupias (Eds.), Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I (Vol. 8572, pp. 89–100). Springer Berlin Heidelberg.
- Allamigeon, X., Stéphane Gaubert, Magron, V. & Werner, B. (2013). Certification of inequalities involving transcendental functions: combining SDP and max-plus approximations. In Proceedings of the 12th European Control Conference. Zürich, Switzerland.
- Allamigeon, X., Gaubert, S. & Goubault, E. (2010). The Tropical Double Description Method. In J.-Y. Marion & T. Schwentick (Eds.), Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010) (Vol. 5, pp. 47–58). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
- Allamigeon, X., Gaubert, S. & Goubault, E. (2008). Inferring Min and Max Invariants Using Max-plus Polyhedra. In M. Alpuente & G. Vidal (Eds.), Proceedings of the 15th International Static Analysis Symposium (SAS’08) (Vol. 5079, pp. 189–204). Valencia, Spain: Springer Verlag.
- Allamigeon, X. (2008). Non-disjunctive Numerical Domain for Array Predicate Abstraction. In S. Drossopoulou (Ed.), Programming Languages and Systems, Proceedings of the 17th European Symposium on Programming (ESOP’08) (Vol. 4960, pp. 163–177). Budapest, Hungary: Springer Verlag.
- Allamigeon, X. & Hymans, C. (2007). Analyse Statique par Interprétation Abstraite : Application à la Détection de Dépassement de Tampon. In E. Filiol (Ed.), 5ème Symposium sur la Sécurité des Technologies de l’Information et des Communications (SSTIC’07) (pp. 347–384). Rennes, France: ESAT.
- Allamigeon, X., Godard, W. & Hymans, C. (2006). Static Analysis of String Manipulations in Critical Embedded C Programs. In K. Yi (Ed.), Static Analysis, 13th International Symposium (SAS’06) (Vol. 4134, pp. 35–51). Seoul, Korea: Springer Verlag.
- Allamigeon, X. & Blanchet, B. (2005). Reconstruction of Attacks against Cryptographic Protocols. In 18th IEEE Computer Security Foundations Workshop (CSFW-18) (pp. 140–154). Aix-en-Provence, France: IEEE Computer Society.
Workshops
- Affeldt, R., Allamigeon, X., Bertot, Y., Canu, Q., Cohen, C., Roux, P., … Trunov, A. (2021). Porting the Mathematical Components library to Hierarchy Builder. Coq Workshop 2021.
- Allamigeon, X., Cohen, C., Sakaguchi, K. & Strub, P.-Y. (2020). A hierarchy of ordered types in Mathematical Components. Coq Workshop 2020.
Preprints
- Allamigeon, X., Canu, Q., Cohen, C., Sakaguchi, K. & Strub, P.-Y. (2023). Design patterns of hierarchies for order structures.
- Allamigeon, X., Aznag, A., Gaubert, S. & Hamdi, Y. (2020). The tropicalization of the entropic barrier.
Theses
- Allamigeon, X. (2009). Static analysis of memory manipulations by abstract interpretation — Algorithmics of tropical polyhedra, and application to abstract interpretation (PhD thesis). École Polytechnique, Palaiseau, France.
Won the Gilles Kahn prize 2010 for best dissertation in Computer Science (awarded by the Société Informatique de France and sponsored by Académie des Sciences).