Workpackages

algebra

Algebraic Algorithms
Geometric Modeling
Computational Game Theory

References:
[1] G. Christodoulou, E. Koutsoupias, and P. Spirakis. On the performance of approximate equilibria in congestion games. Algorithmica, 61(1):116–140, 2011.
[2] A. Dickenstein and I. Emiris, editors. Solving Polynomial Equations: Foundations, Algorithms and Applications, volume 14 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, May 2005.
[3] Z. Du, V. Sharma, and C. K. Yap. Amortized bound for root isolation via Sturm sequences. In D. Wang and L. Zhi, editors, Proc. Intern. Workshop on Symbolic Numeric Computing, pages 113–129, Beijing, 2005.
[4] I. Emiris, A. Galligo, and E. Tsigaridas. Random polynomials and expected-case complexity of real root isolation. In Proc. Annual ACM Intern. Symp. on Symbolic and Algebraic Computation, pages 235–242. ACM Press, 2010.
[5] I. Emiris, B. Mourrain, and E. Tsigaridas. Real algebraic numbers: Complexity analysis and experimentations. In P. Hertling, C. Hoffmann, W. Luther, and N. Revol, editors, Reliable Implementation of Real Number Algorithms: Theory and Practice, volume 5045 of LNCS, pages 57–82. Springer, 2008.
[6] I. Emiris, B. Mourrain, and E. Tsigaridas. The DMM bound: multivariate (aggregate) separation bounds. In Proc. Annual ACM Intern. Symp. on Symbolic and Algebraic Computation, pages 243–250. ACM Press, 2010. Distinguished Paper Award.
[7] I. Gelfand, M. Kapranov, and A. Zelevinsky. Discriminants, Resultants and Multidimensional Determinants. Birkhauser, Boston, 1994.
[8] K. A. Hansen, M. Koucky, N. Lauritzen, P. B. Miltersen, and E. P. Tsigaridas. Exact algorithms for solving stochastic games. In Proc. 43rd Annual ACM Symp. Theory of Computing (STOC), 2011. To appear.
[9] R. Lipton, E. Markakis, and A. Mehta. Playing large games using simple strategies. In Proc. 4th ACM Conf. Electronic Commerce, pages 36–41, 2003.
[10]E. Tsigaridas and I. Emiris. On the complexity of real root isolation using continued fractions. Theoret. Computer Science, Special Issue Computat. Algebraic Geom. & Applic., 392(1–3):158–173, Feb. 2008.