Lance Fortnow

Publications

• H. Buhrman, L. Fortnow, M. Koucky, J. Rogers, and N. Vereshchagin. Inverting onto functions and the polynomial hierarchy. Theory of Computing Systems, 2009. To appear. (PostScript, 15 pages, 356018 bytes) (PDF, 207830 bytes)

• L. Fortnow and A. Klivans. Efficient learning algorithms yield circuit lower bounds. Journal of Computer and System Sciences, 75:27-36, January 2009. Special issue for selected papers from the 19th Annual Conference on Computational Learning Theory. (PDF, 171886 bytes)

• L. Fortnow and R. Vohra. The complexity of forecast testing. Econometrica, 77(1):93-105, 2009. (PDF, 165722 bytes)

• L. Antunes and L. Fortnow. Sophistication revisited. Theory of Computing Systems, 2008. To appear. (PostScript, 9 pages, 323800 bytes) (PDF, 184684 bytes)

• H. Buhrman, L. Fortnow, I. Newman, and H. Röhrig. Quantum property testing. SIAM Journal on Computing, 37(5):1387-1400, 2008. (PDF, 244397 bytes)

• Y. Chen, L. Fortnow, N. Lambert, D. Pennock, and J. Wortman. Complexity of combinatorial market makers. In Proceedings of the 9th ACM Conference on Electronic Commerce, pages 190-199. ACM, New York, 2008. (PostScript, 10 pages, 340386 bytes) (PDF, 220707 bytes)

• N. Devanur and L. Fortnow. A computational theory of awareness and decision making. Technical Report TR08-046, Electronic Colloquium on Computational Complexity, 2008. (PostScript, 12 pages, 296108 bytes) (PDF, 135035 bytes)

• L. Fortnow. Program equilibria and discounted computation time. Technical Report 1473, Center for Mathematical Studies in Economics and Management Science Discussion Paper, 2008.

• L. Fortnow and R. Santhanam. Infeasibility of instance compression and succinct PCPs for NP. In Proceedings of the 40th ACM Symposium on the Theory of Computing, pages 133-142. ACM, New York, 2008. (PostScript, 10 pages, 301112 bytes) (PDF, 227173 bytes)

• L. Fortnow, R. Impagliazzo, V. Kabanets, and C. Umans. On the complexity of succinct zero-sum games. Computational Complexity, 17(3):353-376, October 2008. (PostScript, 24 pages, 421093 bytes) (PDF, 248928 bytes)

• L. Fortnow, A. Pavan, and S. Sengupta. Proving SAT does not have small circuits with an application to the two queries problem. Journal of Computer and System Sciences, 74(3):358-363, May 2008. Special issue for selected papers from the 18th IEEE Conference on Computational Complexity. (PostScript, 10 pages, 145348 bytes) (PDF, 86714 bytes)

• L. Antunes, L. Fortnow, A. Pinto, and A. Souto. Low-depth witnesses are easy to find. In Proceedings of the 22nd IEEE Conference on Computational Complexity, pages 46-51. IEEE, New York, 2007. (PostScript, 10 pages, 271691 bytes) (PDF, 176223 bytes)

• Y. Chen, L. Fortnow, E. Nikolova, and D. Pennock. Betting on permutations. In Proceedings of the 8th ACM Conference on Electronic Commerce, pages 326-335. ACM, New York, 2007. (PostScript, 10 pages, 329764 bytes) (PDF, 185447 bytes)

• Y. Chen, L. Fortnow, E. Nikolova, and D. Pennock. Combinatorial betting. SIGecom Exchanges, 7(1), December 2007. Survey. (PDF, 125680 bytes)

• Y. Chen, D. Reeves, D. Pennock, R. Hanson, L. Fortnow, and R. Gonen. Bluffing and strategic reticence in prediction markets. In The 3rd International Workshop On Internet And Network Economics, volume 4858 of Lecture Notes in Computer Science, pages 70-81. Springer, Berlin, 2007. (PDF, 148678 bytes)

• L. Antunes, L. Fortnow, D. van Melkebeek, and N. Vinodchandran. Computational depth: Concept and applications. Theoretical Computer Science, 354(3):391-404, April 2006. Special issue of selected papers from Foundations of Computation Theory (FCT 2003). (PostScript, 14 pages, 380904 bytes) (PDF, 265228 bytes)

• R. Beigel, H. Buhrman, P. Fejer, L. Fortnow, P. Grabowski, L. Longpré, A. Muchnik, F. Stephan, and L. Torenvliet. Enumerations of the Kolmogorov function. Journal of Symbolic Logic, 71(2):501-528, June 2006. (PostScript, 37 pages, 526645 bytes) (PDF, 316585 bytes)

• R. Beigel, L. Fortnow, and W. Gasarch. A tight lower bound for restricted PIR protocols. Computational Complexity, 15(1):82-91, May 2006. (PostScript, 11 pages, 211545 bytes)

• R. Beigel, L. Fortnow, and F. Stephan. Infinitely-often autoreducible sets. SIAM Journal on Computing, 6(3):595-608, 2006. (PostScript, 17 pages, 361700 bytes) (PDF, 226040 bytes)

• E. Fischer and L. Fortnow. Tolerant versus intolerant testing for Boolean properties. Theory of Computing, 2(9):173-183, 2006. (PostScript, 6 pages, 321045 bytes) (PDF, 209933 bytes)

• L. Fortnow and A. Klivans. Linear advice for randomized logarithmic space. In Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science, volume 3884 of Lecture Notes in Computer Science, pages 469-476. Springer, Berlin, 2006. (PostScript, 8 pages, 309254 bytes) (PDF, 216557 bytes)

• L. Fortnow and M. Ogihara. Very sparse leaf languages. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, volume 4162 of Lecture Notes in Computer Science, pages 375-386. Springer, Berlin, 2006. (PostScript, 14 pages, 363263 bytes) (PDF, 235525 bytes)

• L. Fortnow and R. Santhanam. Fixed-polynomial size circuit bounds. Technical Report TR06-157, Electronic Colloquium on Computational Complexity, 2006. (PostScript, 18 pages, 419928 bytes) (PDF, 244574 bytes)

• L. Fortnow and R. Santhanam. Recent work on hierarchies for semantic classes. SIGACT News, 37(3):36-54, September 2006. (PostScript, 17 pages, 392947 bytes) (PDF, 219493 bytes)

• L. Fortnow, J. Hitchcock, A. Pavan, N.V. Vinodchandran, and F. Wang. Extracting kolmogorov complexity with applications to dimension zero-one laws. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, number 4051 in Lecture Notes in Computer Science, pages 335-345. Springer, Berlin, 2006. (PostScript, 13 pages, 356990 bytes) (PDF, 223304 bytes)

• L. Fortnow, T. Lee, and N. Vereshchagin. Kolmogorov complexity with error. In Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science, number 3884 in Lecture Notes in Computer Science, pages 137-148. Springer, Berlin, 2006. (PostScript, 12 pages, 343279 bytes) (PDF, 242845 bytes)

• L. Antunes and L. Fortnow. Time-bounded universal distributions. Technical Report TR05-144, Electronic Colloquium on Computational Complexity, 2005. Current Title: Worst-Case Running Times for Average-Case Algorithms. (PostScript, 9 pages, 322870 bytes) (PDF, 220571 bytes)

• H. Buhrman, L. Fortnow, I. Newman, and N. Vereshchagin. Increasing Kolmogorov complexity. In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science, number 3404 in Lecture Notes in Computer Science, pages 412-421. Springer, Berlin, 2005. (PostScript, 7 pages, 291366 bytes) (PDF, 167448 bytes)

• H. Buhrman, L. Fortnow, and A. Pavan. Some results on derandomization. Theory of Computing Systems, 38(2):211-227, February 2005. Special issue on the 20th Symposium on Theoretical Aspects of Computer Science. (PostScript, 15 pages, 359485 bytes) (PDF, 247775 bytes)

• Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, and Christian Sohler. Approximating the weight of the euclidean minimum spanning tree in sublinear time. SIAM Journal on Computing, 35(1):91-109, 2005. (PostScript, 20 pages, 490097 bytes)

• J. Feigenbaum, L. Fortnow, D. Pennock, and R. Sami. Computation in a distributed information market. Theoretical Computer Science, 343(1-2):114-132, October 2005. Special issue on Game Theory Meets Theoretical Computer Science. (PostScript, 24 pages, 384879 bytes)

• L. Fortnow. Beyond NP: The work and legacy of Larry Stockmeyer. In Proceedings of the 37th ACM Symposium on the Theory of Computing, pages 120-127. ACM, New York, 2005. Keynote address. (PostScript, 8 pages, 252758 bytes) (PDF, 147858 bytes)

• L. Fortnow and A. Klivans. NP with small advice. In Proceedings of the 20th IEEE Conference on Computational Complexity, pages 228-234, New York, 2005. IEEE. (PostScript, 7 pages, 350956 bytes) (PDF, 234686 bytes)

• L. Fortnow and J. Lutz. Prediction and dimension. Journal of Computer and System Sciences, 70(4):570-589, June 2005. Special issue for selected papers from the 15th Annual Conference on Computational Learning Theory. (PostScript, 23 pages, 568212 bytes)

• L. Fortnow, J. Kilian, D. Pennock, and M. Wellman. Betting Boolean-style: A framework for trading in securities based on logical formulas. Decision Support Systems, 39(1):87-104, 2005. Special Issue on the Fourth ACM Conference on Electronic Commerce. (PostScript, 32 pages, 426385 bytes) (PDF, 288382 bytes)

• L. Fortnow, R. Lipton, D. van Melkebeek, and A. Viglas. Time-space lower bounds for satisfiability. Journal of the ACM, 52(6):835-865, November 2005. (PostScript, 30 pages, 473605 bytes)

• L. Fortnow, R. Santhanam, and L. Trevisan. Hierarchies for semantic classes. In Proceedings of the 37th ACM Symposium on the Theory of Computing, pages 348-355. ACM, New York, 2005. (PostScript, 9 pages, 303232 bytes) (PDF, 184540 bytes)

• L. Fortnow. Kolmogorov complexity and computational complexity. In Jan Karjícek, editor, Complexity of Computations and Proofs, volume 13 of Quaderni di Matematica, pages 229-248. Dipartimento di Matematica della Seconda Universitá Napoli, 2004. (PostScript, 12 pages, 264781 bytes) (PDF, 180580 bytes)

• L. Fortnow and R. Santhanam. Hierarchy theorems for probabilistic polynomial time. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pages 316-324. IEEE, New York, 2004. (PostScript, 20 pages, 305748 bytes)

• L. Antunes, L. Fortnow, and V. Vinodchandran. Using depth to capture average-case complexity. In 14th International Symposium on Fundamentals of Computation Theory, volume 2751 of Lecture Notes in Computer Science, pages 303-310. Springer, Berlin, 2003. Journal Version merged into Computational depth: Concept and applications.

• R. Beigel and L. Fortnow. Are Cook and Karp ever the same?. In Proceedings of the 18th IEEE Conference on Computational Complexity, pages 333-336. IEEE, New York, 2003. (PostScript, 4 pages, 78004 bytes) (PDF, 105993 bytes)

• H. Buhrman, R. Chang, and L. Fortnow. One bit of advice. In Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science, volume 2607 of Lecture Notes in Computer Science, pages 547-558. Springer, Berlin, 2003. (PostScript, 341502 bytes) (PDF, 151351 bytes)

• R. Downey and L. Fortnow. Uniformly hard languages. Theoretical Computer Science, 298(2):303-315, 2003. (PostScript, 14 pages, 205981 bytes) (PDF, 208146 bytes)

• S. Fenner, L. Fortnow, S. Kurtz, and L. Li. An oracle builder's toolkit. Information and Computation, 182(2):95-136, 2003. (PostScript, 44 pages, 503324 bytes)

• S. Fenner, L. Fortnow, A. Naik, and J. Rogers. Inverting onto functions. Information and Computation, 186(1):90-103, October 2003. (PostScript, 15 pages, 179214 bytes) (PDF, 192319 bytes)

• L. Fortnow. One complexity theorist's view of quantum computing. Theoretical Computer Science, 292(3):597-610, 2003. Special Issue of papers presented at the second workshop on Algorithms in Quantum Information Processing. (PostScript, 13 pages, 206015 bytes) (PDF, 189903 bytes)

• L. Fortnow and S. Homer. A short history of computational complexity. Bulletin of the European Association for Theoretical Computer Science, 80, June 2003. Computational Complexity Column. (PostScript, 26 pages, 273616 bytes) (PDF, 230775 bytes)

• R. Beigel, L. Fortnow, and A. Pavan. Membership comparable and p-selective sets. Technical Report 2002-006N, NEC Research Institute, 2002. (PostScript, 12 pages, 313812 bytes) (PDF, 200514 bytes)

• H. Buhrman, L. Fortnow, and S. Laplante. Resource-bounded Kolmogorov complexity revisited. SIAM Journal on Computing, 31(3):887-905, 2002. (PostScript, 22 pages, 304144 bytes)

• L. Fortnow. Theory of quantum computing and communication: A report from the NSF sponsored workshop held January 17-18, 2002 in Elmsford, New York. Technical Report arXiv:physics.quant-ph/0203074, arXiv.org e-Print archive, 2002. (PDF, 28333 bytes)

• L. Fortnow and J. Rogers. Separability and one-way functions. Computational Complexity, 11(3-4):137-157, June 2002. (PostScript, 16 pages, 226823 bytes)

• Y. Zheng, J. Szustakowski, L. Fortnow, R. Roberts, and S. Kasif. Computational identification of operons in microbial genomes. Genome Research, 12(8):1221-1230, August 2002. (PDF, 375063 bytes)

• L. Antunes, L. Fortnow, and D. van Melkebeek. Computational depth. In Proceedings of the 16th IEEE Conference on Computational Complexity, pages 266-273. IEEE, New York, 2001. Journal Version merged into Computational depth: Concept and applications.

• T. Batu, E. Fischer, L. Fortnow, R. Kumar, R. Rubinfeld, and P. White. Testing random variables for independence and identity. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pages 442-451. IEEE, New York, 2001. (PostScript, 10 pages, 193589 bytes)

• R. Beigel, N. Alon, M. S. Apaydin, L. Fortnow, and S. Kasif. An optimal procedure for gap closing in whole genome shotgun sequences. In Proceedings of the 5th Annual International Conference on Computational Molecular Biology, pages 22-30. ACM, New York, 2001. (PostScript, 9 pages, 195829 bytes)

• H. Buhrman, S. Fenner, L. Fortnow, and L. Torenvliet. Two oracles that force a big crunch. Computational Complexity, 10(2):93-116, 2001. (PostScript, 25 pages, 299738 bytes)

• L. Fortnow. Comparing notions of full derandomization. In Proceedings of the 16th IEEE Conference on Computational Complexity, pages 28-34. IEEE, New York, 2001. (PostScript, 7 pages, 150262 bytes)

• L. Fortnow. Kolmogorov complexity. In R. Downey and D. Hirschfeldt, editors, Aspects of Complexity, Minicourses in Algorithmics, Complexity, and Computational Algebra, NZMRI Mathematics Summer Meeting, Kaikoura, New Zealand, January 7-15, 2000, volume 4 of de Gruyter Series in Logic and Its Applications. de Gruyter, 2001. (PostScript, 14 pages, 193447 bytes) (PDF, 220681 bytes)

• L. Fortnow. Special issue for the 1999 Conference on Computational Complexity. Journal of Computer and System Sciences, 62(2), March 2001. Guest Editor.

• L. Fortnow, A. Pavan, and A. Selman. Distributionally hard languages. Theory of Computing Systems, 34(3):245-262, 2001. (PostScript, 19 pages, 119177 bytes)

• T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing that distributions are close. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, pages 259-269. IEEE, New York, 2000. (PostScript, 11 pages, 356186 bytes)

• H. Buhrman, S. Fenner, L. Fortnow, and D. van Melkebeek. Optimal proof systems and sparse sets. In Proceedings of the 17th Symposium on Theoretical Aspects of Computer Science, volume 1770 of Lecture Notes in Computer Science, pages 407-418. Springer, Berlin, 2000. (PostScript, 17 pages, 208378 bytes)

• H. Buhrman, L. Fortnow, D. van Melkebeek, and L. Torenvliet. Separating complexity classes using autoreducibility. SIAM Journal on Computing, 29(5):1497-1520, 2000. (PostScript, 27 pages, 391012 bytes)

• L. Fortnow. Diagonalization. Bulletin of the European Association for Theoretical Computer Science, 71:102-112, June 2000. Computational Complexity Column. (PostScript, 11 pages, 170758 bytes)

• L. Fortnow. Time-space tradeoffs for satisfiability. Journal of Computer and System Sciences, 60(2):337-353, April 2000. Special issue for selected papers from the 12th IEEE Conference on Computational Complexity. (PostScript, 16 pages, 203569 bytes) (PDF, 220528 bytes)

• H. Buhrman and L. Fortnow. One-sided versus two-sided error in probabilistic computation. In Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, volume 1563 of Lecture Notes in Computer Science, pages 100-109. Springer, Berlin, 1999. (PostScript, 10 pages, 141838 bytes)

• H. Buhrman and L. Fortnow. Two queries. Journal of Computer and System Sciences, 59(2):182-194, 1999. Special issue for selected papers from the 13th IEEE Conference on Computational Complexity. (PostScript, 10 pages, 123792 bytes)

• L. Fortnow. Relativized worlds with an infinite hierarchy. Information Processing Letters, 69(6):309-313, 1999. (PostScript, 8 pages, 122529 bytes)

• L. Fortnow and J. Rogers. Complexity limitations on quantum computation. Journal of Computer and System Sciences, 59(2):240-252, 1999. Special issue for selected papers from the 13th IEEE Conference on Computational Complexity. (PostScript, 13 pages, 177788 bytes) (PDF, 186171 bytes)

• L. Fortnow, J. Goldsmith, M. Levy, and S. Mahaney. L-printable sets. SIAM Journal on Computing, 28(1):137-151, 1999. (PostScript, 25 pages, 230237 bytes)

• R. Beigel, H. Buhrman, and L. Fortnow. NP might not be as easy as detecting unique solutions. In Proceedings of the 30th ACM Symposium on the Theory of Computing, pages 203-208. ACM, New York, 1998. (PostScript, 6 pages, 170794 bytes)

• H. Buhrman, L. Fortnow, and T. Thierauf. Nonrelativizing separations. In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 8-12. IEEE, New York, 1998. (PostScript, 5 pages, 64104 bytes)

• J. Feigenbaum, L. Fortnow, S. Laplante, and A. Naik. On coherence, random-self-reducibility, and self-correction. Computational Complexity, 7(2):174-191, 1998. (PostScript, 18 pages, 247260 bytes)

• L. Fortnow and P. Kimmel. Beating a finite automaton in the big match. In Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge, pages 225-234. Morgan Kaufmann, San Francisco, 1998. (PostScript, 10 pages, 165621 bytes)

• L. Fortnow and S. Laplante. Nearly optimal language compression using extractors. In Proceedings of the 15th Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science, pages 84-93. Springer, Berlin, 1998. Journal Version merged into Resource-Bounded Kolmogorov Complexity Revisited.

• L. Fortnow, R. Freivalds, W. Gasarch, M. Kummer, S. Kurtz, C. Smith, and F. Stephan. On the relative sizes of learnable sets. Theoretical Computer Science, 197:139-156, 1998. (PostScript, 25 pages, 248114 bytes)

• H. Buhrman, S. Fenner, and L. Fortnow. Results on resource-bounded measure. In Proceedings of the 24th International Colloquium on Automata, Languages and Programming, volume 1256 of Lecture Notes in Computer Science, pages 188-194. Springer, 1997. (PostScript, 8 pages, 145018 bytes)

• H. Buhrman, L. Fortnow, and L. Torenvliet. Six hypotheses in search of a theorem. In Proceedings of the 12th IEEE Conference on Computational Complexity, pages 2-12. IEEE, New York, 1997. Survey. (PostScript, 11 pages, 207729 bytes)

• L. Fortnow. Counting complexity. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 81-107. Springer, 1997. Survey. (PostScript, 29 pages, 277846 bytes)

• S. Fenner, L. Fortnow, and W. Gasarch. Complexity theory newsflash. SIGACT News, 23(3):126, September 1996. Parody. (PostScript, 2 pages, 49944 bytes)

• S. Fenner, L. Fortnow, and S. Kurtz. The isomorphism conjecture holds relative to an oracle. SIAM Journal on Computing, 25(1):193-206, 1996. (PostScript, 17 pages, 231032 bytes)

• S. Fenner, L. Fortnow, and L. Li. Gap-definability as a closure property. Information and Computation, 130(1):1-17, 1996. (PostScript, 15 pages, 212653 bytes)

• L. Fortnow and M. Kummer. On resource-bounded instance complexity. Theoretical Computer Science A, 161:123-140, 1996. (PostScript, 18 pages, 252706 bytes)

• L. Fortnow and N. Reingold. PP is closed under truth-table reductions. Information and Computation, 124(1):1-6, 1996. (PostScript, 9 pages, 148554 bytes)

• L. Fortnow and T. Yamakami. Generic separations. Journal of Computer and System Sciences, 52(1):191-197, 1996. (PostScript, 18 pages, 204509 bytes)

• S. Fenner and L. Fortnow. Beyond P^NP=NEXP. In Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science, volume 900 of Lecture Notes in Computer Science, pages 619-627. Springer, Berlin, 1995. Journal version: Two Oracles that Force a Big Crunch.

• L. Fortnow and S. Laplante. Circuit lower bounds a la Kolmogorov. Information and Compuation, 123(1):121-126, 1995. (PostScript, 17 pages, 181103 bytes)

• J. Feigenbaum, L. Fortnow, C. Lund, and D. Spielman. The power of adaptiveness and additional queries in random-self-reductions. Computational Complexity, 4:158-174, 1994. (PostScript, 17 pages, 220322 bytes)

• S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48(1):116-148, 1994. Special issue for selected papers from the 6th IEEE Structure in Complexity Theory Conference. (PostScript, 34 pages, 307597 bytes)

• L. Fortnow. The internal and external algebraic structure of complexity classes. Technical report, IMSc, 1994. Collected papers of the Workshop on Algebraic Methods in Complexity Theory. Survey. (PostScript, 7 pages, 104813 bytes)

• L. Fortnow. My favorite ten complexity theorems of the past decade. In Proceedings of the 14th Conference on the Foundations of Software Technology and Theoretical Computer Science, volume 880 of Lecture Notes in Computer Science, pages 256-275. Springer, Berlin, 1994. Invited lecture. (PostScript, 20 pages, 179686 bytes)

• L. Fortnow. The role of relativization in complexity theory. Bulletin of the European Association for Theoretical Computer Science, 52:229-244, February 1994. Computational Complexity Column. (PostScript, 15 pages, 182569 bytes)

• L. Fortnow and D. Whang. Optimality and domination in repeated games with bounded players. In Proceedings of the 26th ACM Symposium on the Theory of Computing, pages 741-749. ACM, New York, 1994. (PostScript, 9 pages, 259255 bytes)

• L. Fortnow, W. Gasarch, S. Jain, E. Kinber, M. Kummer, S. Kurtz, M. Pleszkoch, T. Slaman, R. Solovay, and F. Stephan. Extremes in the degrees of inferability. Annals of Pure and Applied Logic, 66:231-276, 1994. (PostScript, 63 pages, 494796 bytes)

• L. Fortnow, S. Kurtz, and D. Whang. The infinite version of an open communication complexity problem is independent of the axioms of set theory. SIGACT News, 25(1):87-89, 1994. Survey. (PostScript, 3 pages, 92548 bytes)

• L. Fortnow, J. Rompel, and M. Sipser. On the power of multi-prover interactive protocols. Theoretical Computer Science A, 134:545-557, 1994. (PostScript, 11 pages, 156648 bytes)

• L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307-318, 1993. (PostScript, 12 pages, 176078 bytes)

• J. Feigenbaum and L. Fortnow. On the random-self-reducibility of complete sets. SIAM Journal on Computing, 22:994-1005, 1993. (PostScript, 13 pages, 207757 bytes)

• L. Fortnow and C. Lund. Interactive proof systems and alternating time-space complexity. Theoretical Computer Science A, 113:55-73, 1993. (PostScript, 23 pages, 259771 bytes)

• L. Fortnow and M. Szegedy. On the power of two-local random reductions. Information Processing Letters, 44(6):303-306, 1992. (PostScript, 5 pages, 105918 bytes)

• C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859-868, 1992. (PostScript, 10 pages, 145978 bytes)

• L. Babai and L. Fortnow. Arithmetization: A new method in structural complexity theory. Computational Complexity, 1(1):41-66, 1991. (PostScript, 26 pages, 276452 bytes)

• L. Babai, L. Fortnow, L. Levin, and M. Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd ACM Symposium on the Theory of Computing, pages 21-31. ACM, New York, 1991. (PostScript, 16 pages, 227605 bytes)

• L. Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover interactive protocols. Computational Complexity, 1(1):3-40, 1991. (PostScript, 39 pages, 370146 bytes)

• L. Fortnow. The complexity of perfect zero-knowledge. In S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 327-343. JAI Press, Greenwich, 1989. See also the appendix of Computational Complexity and Knowledge Complexity by Goldreich, Ostrovsky and Petrank. (PostScript, 10 pages, 170230 bytes)

• L. Fortnow. Complexity-theoretic aspects of interactive proof systems. PhD thesis, Massachusetts Institute of Technology, May 1989. Tech Report MIT/LCS/TR-447. (PostScript, 58 pages, 486261 bytes)

• L. Fortnow and M. Sipser. Are there interactive protocols for co-NP languages?. Information Processing Letters, 28:249-251, 1988. (PostScript, 3 pages, 74405 bytes)

• L. Fortnow and M. Sipser. Probabilistic computation and linear time. In Proceedings of the 21st ACM Symposium on the Theory of Computing, pages 148-156. ACM, New York, 1989. (PostScript, 17 pages, 229687 bytes) Retraction.

• The copyrights for journal and conference proceedings papers generally belong to the publisher of the journal or proceedings. All papers may be downloaded for personal or research purposes only.
• The postscript and PDF files are the most recent versions of each paper and may not correspond to the referenced version.
• Free gsview and ghostview viewers for postscript.
• Free Adobe PDF Reader
• If you have trouble downloading these papers, .

Back to Lance Fortnow Main Page.