Amos Fiat et. al.

Research Interests

• Competitive Analysis of Online Algorithms
  For an introduction to this active field of research see
  • Online Algorithms: The State of the Art, Springer LNCS State of the Art Survey,
    Edited by A. Fiat and G. Woeginger, and
  • Online Computation and Competitive Analysis by Alan Borodin and Ran El-Yaniv.
• Computational Game Theory
  

Classes 2008, Spring Semester

• Computational Game Theory.

LI> Class in Introduction to Cryptography (Spring Semester 2007-2008).
• Class in Data Mining (Winter Semester 2005-2006).
• Seminar in Game Theory and Networks (Winter Semester 2005-2006).
• Class in Efficiency of Computation, Spring semester 2005-2006.
• Class in Introduction to Cryptography, Winter semester 2003-2004.
• Class in Data Mining (Winter Semester 2002-2003), Includes Scribe Notes.
• Seminar in Data Mining, Spring semester 2002-2003.
• Seminar in Online Computation, Spring semester 2003-2003.
• Class in Introduction to Cryptography, Spring semester 2002-2003.

Selected Papers

(Not updated since 2004, see DBLP below, pending update)

• A. Fiat, Dmitry Pechyony
  Decision Trees: More Theoretical Justification for Practical Algorithms.
  To appear ALT'04, Padova, Italy.

• Ron Berman, A. Fiat, A. Ta-Shma
  Provable Unlinkability against Traffic Analysis.
  Financial Cryptography, 2004, Key West, Florida.

• Dotan Emanuel, A. Fiat
  Correlation Clustering - Minimizing Disagreements on Arbitrary Weighted Graphs.
  Proceedings of ESA 2003.

• Y. Azar, E. Cohen, A. Fiat, H. Kaplan, Harald Räcke
  Optimal oblivious routing in polynomial time.
  Proceedings of STOC 2003.

• E. Cohen, A. Fiat, H. Kaplan
  Associative Search in Peer to Peer Networks: Harnessing Latent Semantics.
  Proceedings of Infocom 2003.

• E. Cohen, A. Fiat, H. Kaplan
  Efficient Sequences of Trials.
  Proceedings of SODA 2003.

• A. Fiat, M. Mendel, S. Seiden
  Online Companion Caching.
  Proceedings of ESA 2002..

• E. Cohen, A. Fiat, H. Kaplan
  A Case for Associative Peer to Peer Overlays.
  Proceedings of Hotnets 2002.

• A. Fiat, A.V. Goldberg, J.D. Hartline, A.R. Karlin
  Competitive Generalized Auctions
  Proceedings of STOC '2002.

• A. Fiat, J. Saia
  Censorship Resistant Peer-to-Peer Content Addressable Networks
  Proceedings of SODA '2002.

• D. Achlioptas, A. Fiat, A. Karlin, F. McSherry
  Web Search Via Hub Synthesis
  Proceedings of FOCS '2001.

• Y. Azar, A. Fiat, A. Karlin, F. McSherry, J. Saia
  Spectral Analysis of Data
  Proceedings of STOC '2001.

• A. Fiat, H. Kaplan
  Making Data Structures Confluently Persistent
  Proceedings of SODA '2001.

• A. Fiat, T. Tassa
  Dynamic Traitor Tracing
  Proceedings of Crypto '99. Also Journal of Cryptology 14(3): 211-223 (2001).

• R. El-Yaniv, A. Fiat, R.M. Karp, G. Turpin,
  Optimal Search and One Way Trading Online Algorithms
  Algorithmica (2001) 30: 101–139.

• A. Fiat, M. Mendel
  Better Algorithms for Unfair Metrical Task Systems and Applications
  STOC '2000.

• A. Fiat, M. Mendel
  Truly Online Paging with Locality of Reference
  FOCS 1997.

• A. Fiat, Z. Rosen
  Experimental Studies of Access Graph Based Heuristics: Beating the LRU Standard?
  SODA 1997.

• A.Fiat, M. Naor
  Rigorous Time/Space Tradeoffs for Inverting Functions
  SIAM J. Comput. 29(3): 790-803 (1999).

• Baruch Awerbuch, Yair Bartal, Amos Fiat
  Distributed Paging for General Networks
  J. Algorithms 28(1): 67-104 (1998)

• Baruch Awerbuch, Yair Bartal, Amos Fiat
  Competitive Distributed File Allocation
  To appear Information and Computation, Preliminary version appeared in STOC 1993: 164-173.

• Amos Fiat
  Batch RSA
  Journal of Cryptology 10(2): 75-88 (1997)

• B. Awerbuch, Y. Azar, A. Fiat, S. Leonardi, A. Rosen
  On-line competitive algorithms for call admission in optical networks
  Proc. of 4th ESA (1996), 431-444 and Algorithmica 31(1): 29-43 (2001).

• Y. Azar, Y. Bartal, E. Feuerstein, A. Fiat, S. Leonardi, Adi Rosén
  On capital investment
  Proc. of 23rd ICALP (1996), 429-441 and Algorithmica 25(1): 22-36 (1999).

• B. Awerbuch, Y. Azar, A. Fiat
  Packet routing via min-cost circuit routing
  Proc. of 4th ISTCS (1996), 37-42.

• B. Awerbuch, Y. Azar, A. Fiat, T. Leighton
  Making commitments in the face of uncertainty: how to pick a winner almost every time
  Proc. of 28th STOC (1996), 519-530.

• Piotr Berman, Avrim Blum, Amos Fiat, Howard J. Karloff, Adi Rosén, Michael E. Saks
  Randomized Robot Navigation Algorithms
  SODA 1996: 75-84

• J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, O. Waarts
  On-line load balancing with applications to machine scheduling and virtual circuit routing
  Proc. of 25th STOC (1993), 623-631.
  Also in Journal of the ACM 44:3 (1997), 486-504.

• Y. Bartal, A. Fiat, and Y. Rabani.
  Competitive Algorithms for Distributed Data Management.
  J. Comput. System Sci., 51(3):341--358, December 1995. Preliminary version appeared in STOC '92.

• A. Fiat, D.P. Foster, H.J. Karloff, Y. Rabani, Y. Ravid, and S. Vishwanathan.
  Competitive Algorithms for Layered Graph Traversal.
  SIAM J. Comput. 28(2): 447-462 (1998). Preliminary version appeared in FOCS '91.

• A. Fiat, Y. Rabani, and Y. Ravid.
  Competitive k-Server Algorithms.
  J. Comput. System Sci., 48(3):410--428, 1994. Preliminary version appeared in FOCS '90.

• Y. Bartal, A. Fiat, Stefano Leonardi
  Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing
  STOC 1996: 531-540

• Amos Fiat, Yishay Mansour, Adi Rosén, Orli Waarts
  Competitive Access Time via Dynamic Storage Rearrangement (Preliminary Version)
  FOCS 1995: 392-401

• Amos Fiat, Anna R. Karlin
  Randomized and Multipointer Paging with Locality of Reference
  STOC 1995: 626-634
  

Graduate Students

• Meital Levy
• Danny Feldman (Co-advisor with Micha Sharir)
• Uri Nadav (Co-advisor with Yishay Mansour)
• Svetlana Olonestsky (Co-advisor with Hiam Kaplan)

• Hila Poch,

Former Ph.D. Students who have graduated:

• Yuval Rabani, Computer Science Department, The Technion, Haifa, Israel
• Yiftach Ravid, IBM Research Labs, Tel Aviv
• Moti Ricklin
• Adi Rosen, Computer Science Department, The Technion, Haifa, Israel
• Yair Bartal, Dept. of Computer Science, the Hebrew University of Jerusalem
• Manor Mendel Currently at the University of Illinois at Urbana, e-mail: mendelma@uiuc.edu.

• Eldad Bar-Eli
• Ziv Rozen
• Alon Eker
• Tali Kaufman-Halman
• Dotan Emanuel
• Ron Berman
• Meital Levy
• Dmitry Pechyonyj
• Danny Feldman
• Sagi Shporer,
• Amit Kagan
• Eyal Carmi
• Felix Gartsman
• Yaniv Nachum

If you are interested in any of my research areas, and are considering a Ph.D. or M.Sc., send me e-mail at fiat@math.tau.ac.il, so we can schedule a meeting to discuss it and I can try to talk you out of it. While theoretical studies form a significant part of any thesis, there is also plenty of very interesting experimental work to be done.

Very Short Biography - Amos Fiat

• Born Dec. 1, 1956, Haifa, Israel.
• Children: Itai (b. 1985), Yonatan (b. 1989), Nimrod (b. 1992) and Dina (b. 1995).
• Married to Michal, e-mail: fiat_michal@hotmail.com.
• 1976-1982: IDF Service.
• 1987: Ph.D. Weizmann Institute, 1986, Advisor: Adi Shamir. Thesis: Fibonnacci Lattices: Theory and Practice.
• Co-inventor (with Adi Shamir) of the Fiat-Shamir Signature and Identification schemes.
• 1987-1989: Weizmann Postdoctoral Fellowship at EECS UC Berkeley, hosted by: Richard M. Karp and Manuel Blum.
• Since 1989 at the Department of Computer Science, Tel Aviv University.
• Member of program committees of various Crypto, EuroCrypt, SODA, STOC, and other conferences.
• Editorial Board member, Theoretical Computer Science (TCSA) and Electronic Notes in Theoretical Computer Science (ENTCS).
• Drives Editors nuts in being late with referee reports, gets far too many referee reports to do.
• Co-organizer with Gerhard Woeginger, of the 1996 ,1999, and 2002 Schloss Dagstul seminars on Online Algorithms (see photo album for 2002). In all cases, Gerhard did all the work.
• The survey talks of the 1996 Dagstuhl Seminar on Online Algorithms were updated by the authors and published as a Springer LNCS State of the Art Survey, Online Algorithms: The State of the Art, Edited by A. Fiat and G. Woeginger. Again, Gerhard did all the work.
• Dragged by Yossi Tulpan to become co-founder of Algorithmic Research Ltd. (AR), acquired by the Cylink Corporation in 1997.
• Following acquisition, became somewhat of an expert on Israeli tax code, Alice's Adventures in Wonderland makes much more sense. Have yet to find an accountant I have any faith in.
• Self-appointed "Official Photographer" at Alan Borodin's 2001 Birthday Celebrations. Photo album online.
• 2000-2001: Sabbatical at University of Washington at Seattle with Anna Karlin.
• Sailed new sailboat, Jumanji, a J120, from Hyeres, France to Hertzilya, Israel, via Corsica, Sardinia, Sicily, Corfu, Ithaka, Lefkada, Pireus, Santorini, Rhodes, and Limassol. See map.

Contact Information

Snail Address:

Professor Amos Fiat
School of Computer Science
Tel Aviv University
Tel Aviv Israel
Link to Campus Map

Home Address:

20 Shalom Ash
Tel Aviv, Israel
Link to Map (in Hebrew)

Telephones

Campus

+972-3-6409161

Res.

+972-3-6477085

Fax (Res.)

+972-3-6475966

E-mail

fiat@tau.ac.il

Administrative Stuff

Other Links