Amos Fiat

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Amos Fiat (born December 1, 1957 in Haifa, Israel)[1] is an Israeli computer scientist, a professor of computer science at Tel Aviv University. He is known for his work in cryptography, online algorithms, and algorithmic game theory.


Fiat earned his Ph.D. in 1987 from the Weizmann Institute of Science under the supervision of Adi Shamir.[2] After postdoctoral studies with Richard Karp and Manuel Blum at the University of California, Berkeley, he returned to Israel, taking a faculty position at Tel Aviv University.


Many of Fiat's most highly cited publications concern cryptography, including his work with Adi Shamir on digital signatures (leading to the Fiat–Shamir heuristic for turning interactive identification protocols into signature schemes).[3] and his work with David Chaum and Moni Naor on electronic money, used as the basis for the ecash system.[4] With Shamir and Uriel Feige in 1988, Fiat invented the Feige–Fiat–Shamir identification scheme, a method for using public-key cryptography to provide challenge-response authentication.

With Gerhard Woeginger, Fiat organized a series of Dagstuhl workshops on competitive analysis of online algorithms, and together with Woeginger he edited the book Online Algorithms: The State of the Art (Lecture Notes in Computer Science 1442, Springer-Verlag, 1998). His research papers include methods for applying competitive analysis to paging,[5] call control,[6] data management,[7] and the assignment of files to servers in distributed file systems.[8]

Fiat's interest in game theory stretches back to his thesis research, which included analysis of the children's game Battleship.[9] He has taken inspiration from the game Tetris in developing new job shop scheduling algorithms,[10] as well as applying competitive analysis to the design of game-theoretic auctions.[11]


  1. ^ Fiat's home page at Tel Aviv University, retrieved 2012-02-19.
  2. ^ Amos Fiat at the Mathematics Genealogy Project
  3. ^ Fiat, Amos; Shamir, Adi (1987), "How to prove yourself: practical solutions to identification and signature problems", Proceedings on Advances in cryptology—CRYPTO '86, Lecture Notes in Computer Science 263, London, UK: Springer-Verlag, pp. 186–194, doi:10.1007/3-540-47721-7_12 .
  4. ^ Chaum, D.; Fiat, A.; Naor, M. (1990), "Untraceable electronic cash", Proceedings on Advances in cryptology—CRYPTO '88, Lecture Notes in Computer Science 403, London, UK: Springer-Verlag, pp. 319–327 .
  5. ^ Fiat, Amos; Karp, Richard M.; Luby, Michael; McGeoch, Lyle A.; Sleator, Daniel D.; Young, Neal E. (1991), "Competitive paging algorithms", Journal of Algorithms 12 (4): 685–699, arXiv:cs.DS/0205038, doi:10.1016/0196-6774(91)90041-V .
  6. ^ Awerbuch, Baruch; Bartal, Yair; Fiat, Amos; Rosén, Adi (1994), "Competitive non-preemptive call control", Proceedings of the Fifth ACM-SIAM Symposium on Discrete Algorithms (SODA '94), pp. 312–320 .
  7. ^ Bartal, Yair; Fiat, Amos; Rabani, Yuval (1995), "Competitive algorithms for distributed data management", Journal of Computer and System Sciences 51 (3): 341–358, doi:10.1006/jcss.1995.1073, MR 1368903 .
  8. ^ Awerbuch, Baruch; Bartal, Yair; Fiat, Amos (1993), "Competitive distributed file allocation", Proceedings of the Twenty-Fifth ACM Symposium on Theory of Computing (STOC '93), pp. 164–173, doi:10.1145/167088.167142 .
  9. ^ Fiat, Amos; Shamir, Adi (1989), "How to find a battleship", Networks 19 (3): 361–371, doi:10.1002/net.3230190306, MR 996587 .
  10. ^ Bartal, Yair; Fiat, Amos; Karloff, Howard; Vohra, Rakesh (1992), "New algorithms for an ancient scheduling problem", Proceedings of the Twenty-Fourth ACM Symposium on Theory of Computing (STOC '92), pp. 51–58, doi:10.1145/129712.129718 .
  11. ^ Fiat, Amos; Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R. (2002), "Competitive generalized auctions", Proceedings of the Thirty-Fourth ACM Symposium on Theory of Computing (STOC '02), pp. 72–81, doi:10.1145/509907.509921 .