Francis Zane



Room 2c-354
600 Mountain Avenue
Murray Hill, NJ 07974
(908) 582-6081
/cm/ms/who/francis/
francis@research.bell-labs.com


Interests Digital watermarking and fingerprinting, Internet and networking, algorithms for NP-complete problems, circuit complexity, combinatorics, unusual models of computation (quantum computing, biological computing, etc.).

Education UNIVERSITY OF CALIFORNIA AT SAN DIEGO La Jolla, CA
September 1993-July 1998
Ph.D in Computer Science and Engineering, 1998. Thesis title: “Circuits, CNFs, and Satisfiability.” Classes include Architecture, Programming Languages, Cryptography, Graphics, and Complexity Theory.

MASSACHUSETTS INSTITUTE OF TECHNOLOGY Cambridge, MA
August 1989-June 1993
Bachelor of Science in Mathematics, 1993. Subjects completed include Algorithms, Adv. Parallel Algorithms, Adv. Cryptography, Theory of Computation, and Algebra.

Experience BELL LABS, LUCENT TECHNOLOGIES Murray Hill, NJ
August 1998-present
Postdoctoral member of the Fundamental Mathematics department. Conducted research on digital watermarking, satisfiability, and Internet networking. In addition, participated in several business-related projects, including developing a Java scheduling tool capable of interfacing with Excel spreadsheets using COM.

CONSULTANT – INTERTRUST STAR LABS Sunnyvale, CA
August 1997-March 1998
Participated in research on the evaluation, design, and analysis of digital watermarking algorithms. Watermarks are signals added to content (eg. images) enabling programs to distinguish perceptually indistinguishable copies for copyright or ownership purposes. Involved both theoretical as well as experimental work.

CONSULTANT – IXSYS INC. San Diego, CA
June 1997-March 1998
Worked on project analyzing alternative approaches to drug design. Developed simple computer models for chemical-receptor interaction in order to simulate the drug discovery process. Designed and implemented algorithms for identifying potential drugs in the context of these models.

CONSULTANT – NEC RESEARCH Princeton, NJ
September 1996-January 1997
Involved in research and development of image watermarking software. Work included theoretical and experimental analysis on the robustness and performance of the watermarking algorithms, as well as writing programs implementing the algorithms. Wrote pre-release version of watermarking software.

UCSD OPTOELECTRONIC COMPUTING GROUP La Jolla, CA
September 1994-July 1998
Research Assistant with Optoelectronic Computing Group in the Electrical and Computer Engineering Department. Involved in research and writing proposals. Worked on applications of optoelectronic devices to interconnection networks, focusing on system architecture and network design and modeling. Particular interest in applications to digital signal processing systems.

UCSD La Jolla, CA
September 1993-March 1995
Winter 1995: Teaching Assistant for CSE 80: Unix Lab. Also involved in developing the course. Winter 1994: Grader for CSE 200-201, graduate complexity theory classes. Fall 1993: Reader for CSE 202, the graduate algorithms class. Held regular office hours.

PROFS. TOM LEIGHTON AND SILVIO MICALI Cambridge, MA
July 1992-August 1993
Involved in development of cryptographically secure ID badge system. End users would be given cards which contained digitized pictures, personal information, and digital signatures. Developed system running under Unix and modified existing software running under OS/2. Included work on device interfacing and graphics programming.

MIT EXPERIMENTAL STUDIES GROUP Cambridge, MA
September 1990-January 1991
Taught 4 person class in 18.011 and 18.021 (Calculus I and II)

Awards President, CSE Graduate Student Association (1994-96)

Spring 1994 Comprehensive Exams: Pass with Distinction

Powell Fellowship (1993-94)

Publications   

Efficient Watermark Detection and Collusion Security. Francis Zane. Proceedings of Financial Crypto '00. To appear.

Watermarking Maps: Hiding Information in Structured Data. Sanjeev Khanna and Francis Zane. Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. January 2000, San Francisco, CA. To appear.

Circuits, CNFs, and Satisfiability. Francis Zane. PhD Thesis, Dept. of Computer Science and Engineering, UCSD. 1998.

An Improved Exponential-time Algorithm for k-SAT. Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane. Proceedings of the 39th Annual Symposium on Foundations of Computer Science. November 1998, Palo Alto, CA. pp. 628-637.

Which Problems Have Strongly Exponential Complexity? Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Proceedings of the 39th Annual Symposium on Foundations of Computer Science. November 1998, Palo Alto, CA. pp. 653-662.

Resistance of Digital Fingerprints to Collusional Attacks. Joe Kilian, F. Thomson Leighton, Lesley R. Matheson, Talal G. Shamoon, Robert E. Tarjan, and Francis Zane. Proceedings of 1998 IEEE International Symposium on Information Theory. Cambridge, MA, 16-21 August 1998. p. 271. Full version available as: Resistance of Digital Watermarks to Collusive Attacks. Princeton Computer Science Technical Report TR-585-98.

Robustness and Security of Digital Watermarks. Lesley R. Matheson, Stephen G. Mitchell, Talal G. Shamoon, Robert E. Tarjan, and Francis Zane. Proceedings of Financial Cryptography '98, Anguilla, BWI, 23-25 February 1998.

Satisfiability Coding Lemma. Ramamohan Paturi, Pavel Pudlák, and Francis Zane. Proceedings of the 38th Annual Symposium on Foundations of Computer Science. October 1997, Miami, FL. pp. 566-574.

Dimension of Projections in Boolean Functions. Ramamohan Paturi and Francis Zane. SIAM Journal on Discrete Mathematics. Vol 11, No. 4. pp. 624-632.

Exponential Lower Bounds for Depth 3 Boolean Circuits. Ramamohan Paturi, Michael E. Saks, and Francis Zane. Proceedings of the 29th Annual ACM Symposium of Theory of Computing. May 1997, El Paso, TX. pp. 86-91.

Scalable Network Architectures Using the Optical Transpose Interconnection System (OTIS). Francis Zane, Ramamohan Paturi, Philippe Marchand, and Sadik Esener. Journal of Parallel and Distributed Computing, to appear. Preliminary version appeared in Proceedings of the 3rd International Conference on Massively Parallel Processing Using Optical Interconnects (MPPOI). October 1996, Maui, HI. pp. 114-121