Papers and Reports: 1999-2000

Cryptographic Foundations

• Cynthia Dwork and Moni Naor: "Zaps and Their Applications", to appear in the Proceedings of the 41st Annual Symposium on Foundations of Computer Science - FOCS'00, Redondo Beach, California, November 12-14, 2000.

• Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, and Mahesh Viswanathan: "The Relationship between Public Key Encryption and Oblivious Transfer", in the Proceedings of the 41st Annual Symposium on Foundations of Computer Science - FOCS'00, Redondo Beach, California, November 12-14, 2000.

• Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar: "Rank Aggregation, Spam Resistance, and Social Choice", submitted for publication, 2000.

Security Protocols and Access Control

• Vitaly Shmatikov and John Mitchell: "Analysis of a Fair Exchange Protocol", in the Proceedings of the 7th Annual Symposium on Network and Distributed System Security - NDSS 2000, San Diego, February 3-4, 2000.

• Vitaly Shmatikov and John Mitchell: "Analysis of Abuse-Free Contract Signing", in the Proceedings of the 4th International Conference on Financial Cryptography - FC'00, Anguilla, February 21-24, 2000.

• Iliano Cervesato, Nancy Durgin, John Mitchell, Patrick Lincoln, and Andre Scedrov: "Relating strands and multiset rewriting for security protocol analysis", in the Proceedings of the 13th IEEE Computer Security Foundations Workshop - CSFW 2000, Cambridge, U.K., July 3-5, 2000.

• Iliano Cervesato, Nancy Durgin, Max Kanovich, and Andre Scedrov: "Interpreting strands in linear logic", in the Proceedings of the 2000 Workshop on Formal Methods and Computer Security [link], Satellite Workshop of the 12th International Conference on Computer Aided Verification - CAV 2000, Chicago, Illinois, July, 2000.
• Joseph Halpern and Ron van der Meyden: "A Logic for SDSI's Linked Local Name Spaces", to appear in Journal of Computer Security. Also in the Proceedings of the 12th IEEE Computer Security Foundations Workshop, pp. 111-122 - CSFW'99, Mordano, Italy, June 28-30, 1999.

Monitoring Real-Time and Distributed Systems

• S. Kannan, M. Kim, I. Lee, O. Sokolsky, and M. Viswanathan: "Run-time monitoring and Steering based on Formal Specifications", Workshop on Modeling Software System Structures in a fastly moving scenario, June 2000.

• K. Bhargavan, C.A. Gunter, M. Kim, I. Lee, D. Obradovic, O. Sokolsky, and M. Viswanathan: "Formal Analysis of Network Simulations", in the Proceedings of the 2000 International Symposium on Software Testing and Analysis - ISSTA'00, Portland, Oregon, August 22-24, 2000.

• R. Alur, R. Grosu, Y. Hur, V. Kumar, and I. Lee: "Modular Specification of Hybrid Systems in Charon", in the Proceedings of the 3rd International Workshop on Hybrid Systems: Computation and Control - HSCC'00, Pittsburgh, March 23-25, 2000.

• A. Philippou, I. Lee, and O. Sokolsky: "Weak Bisimulation for Probabilistic Systems", in the Proceedings of the 11th International Conference on Concurrency Theory - CONCUR'00, Penn State University, August 22-25, 2000.

Result Checking and Large Data Streams

• Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan: "An Approximate L1-Difference Algorithm for Massive Data Streams", in the Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science - FOCS'99, New York City, October 17-19, 1999.

• Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan: "Testing and Spot-Checking of Data Streams", in the Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms - SODA'00, San Francisco, January 9-11, 2000.

• F. Ergün, S. Kannan, S. Ravi Kumar, R. Rubinfeld, and M. Vishwanathan: "Spot Checking", Journal of Computer and System Sciences, Vol. 60, No. 3, Jun 2000, pp. 717-751.

Complexity

• Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, and Mike Paterson: "A bound on the capacity of backoff and acknowledgement-based protocols", in the Proceedings of the 27th International Colloquium on Automata, Languages and Programming - ICALP'00, Geneva, July 9-15, 2000.

• R. Fagin, A. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan, and A. Tomkins: "Random Walks with `Back Buttons'", in the Proceedings of the 32nd ACM Symposium on Theory of Computing - STOC'00, Portland, Oregon, May 21-23, 2000.

Adaptive Systems

• Diana Gordon: "APT Agents: Agents that are adaptive, predictable, and timely", to appear in the Proceedings of the First Goddard Workshop on Formal Approaches to Agent-Based Systems [link], Greenbelt, Maryland, April 5-7, 2000.
• Kiriakidis, K. and Gordon, D.: "Supervisory control of multiagent systems subject to failure", Abstract to appear in the Proceedings of the First Goddard Workshop on Formal Approaches to Agent-Based Systems [link], Greenbelt, Maryland, April 5-7, 2000.
• Diana Gordon: "Asimovian adaptive agents", Journal of Artificial Intelligence Research, Vol. 13, Sep 2000, pp. 95-143 - JAIR.
• Gordon, D. and Kiriakidis, K.: "Adaptive supervisory control of interconnected discrete event systems", in the Proceedings of the IEEE International Conference on Control Applications - CCA'00, Anchorage, Alaska, September 25-27, 2000.
• Gordon, D. and Kiriakidis, K.: "Design of adaptive supervisors for discrete event systems via learning", in the Proceedings of the International Mechanical Engineering Congress and Exposition - IMECE'00, Orlando, Florida, November 5-10, 2000.
• Spears, W. and Gordon, D.: "Evolving finite-state machine strategies for protecting resources", in the Proceedings of the 12th International Symposium on Methodologies for Intelligent Systems - ISMIS'00, Charlotte, North Carolina, October 11-14, 2000.