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 2012-2013

Class in Electronic Commerce (Largely following the Easley-Kleinberg book, Networks, Crowds, and Markets) 2012-2013.
Class in Auctions and Mechanism Design (Following Jason Hartline’s book) 2012-2013.
Seminar in Information Markets 2012-2013.

Previous Classes

Seminar in Auctions and Mechanism Design (Following Jason Hartline’s book).
Computational Game Theory 2012.
Computational Game Theory. 2010
Computational Game Theory, 2008.
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)

See list of publications for Amos Fiat at DBLP Bibliography Server and citations at CiteSeer

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

Current Ph.D. Candidates I'm advising:

Svetlana Olonestsky (Co-advisor with Hiam Kaplan)

Current M.Sc. candidates I'm advising:

Sarel Cohen
Eran Nir
Alon Ardenboim

Former Ph.D. Students who have graduated:

Yuval Rabani, The Hebrew University of Jerusalem.
Yiftach Ravid, IBM Research Labs, Tel Aviv
Moti Ricklin
Adi Rosen, CNRS, Paris 7, France
Yair Bartal, The Hebrew University of Jerusalem
Manor Mendel The Open University (now at Microsoft/UW/Princeton).
Meital Levy Bar Ilan University
Uri Nadav Yahoo Research, Sunnyvale
Danny Feldman MIT

Former Ms.C. Students who have gradutated:

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.