Mihalis Yannakakis - Selected publications#

X Chen, D Paparas, M Yannakakis: The complexity of non-monotone markets. Proc. STOC 181-190, 2013.

K Etessami, A. Stewart, M Yannakakis: Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars. Proc. STOC, 579-588, 2012.

VV Vazirani, M Yannakakis: Market equilibrium under separable, piecewise-linear, concave utilities. J. ACM 58(3), 1-25, 2011.

K Etessami, M Yannakakis: On the Complexity of Nash Equilibria and Other Fixed Points. SIAM J. Comput. 39(6), 2531-2597, 2010.

K Etessami, M Yannakakis: Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. J. ACM 56(1), 1-66, 2009.

CH Papadimitriou, M. Yannakakis: On the Approximability of Trade-offs and Optimal Access of Web Sources. Proc. FOCS, 86-92, 2000.

D Lee, M Yannakakis: Principles and methods of testing finite state machines-a survey. Proc. IEEE 84 (8), 1090-1123, 1996.

C Lund, M Yannakakis: On the hardness of approximating minimization problems. J. ACM 41(5), 960-981, 1994.

C. Courcoubetis, MY Vardi, P Wolper, M Yannakakis: Memory-Efficient Algorithms for the Verification of Temporal Properties. Formal Methods in System Design 1(2/3): 275-288, 1992.

CH Papadimitriou, M Yannakakis: Optimization, approximation, and complexity classes. J. Computer and System Sciences 43(3), 425-440, 1991.

M. Yannakakis: Expressing Combinatorial Optimization Problems by Linear Programs. J. Computer and System Sciences 43(3), 441-466, 1991.

DS Johnson, CH Papadimitriou, M Yannakakis: How easy is local search? J. Computer and System Sciences 37 (1), 79-100, 1988.

C Beeri, R Fagin, D Maier, M Yannakakis: On the desirability of acyclic database schemes. J. ACM 30(3), 479-513, 1983


Full publication list (Google Scholar)
Full publication list (DBLP)