L. Antunes and
L. Fortnow.
Sophistication
revisited.
Theory of Computing Systems, 45(1):150-161, June 2009.
(PostScript, 9 pages, 323800 bytes)
(PDF, 184684 bytes)
L. Antunes and
L. Fortnow.
Worst-case running times for average-case algorithms.
In Proceedings of the 24th IEEE Conference on Computational
Complexity. 2009.
To appear.
(PostScript, 5 pages, 198155 bytes)
(PDF, 172561 bytes)
H. Buhrman, L. Fortnow,
and R. Santhanam.
Unconditional lower bounds against advice.
In Proceedings of the 36th International Colloquium on Automata,
Languages and Programming. 2009.
To appear.
(PostScript, 11 pages, 404255 bytes)
(PDF, 237327 bytes)
N. Devanur and
L. Fortnow.
A computational theory of awareness and decision making.
In Proceedings of the 12th Conference on Theoretical Aspects of
Rationality and Knowledge. 2009.
To appear.
(PostScript, 12 pages, 296108 bytes)
(PDF, 145848 bytes)
L. Fortnow.
Program equilibria and discounted computation time.
In Proceedings of the 12th Conference on Theoretical Aspects of
Rationality and Knowledge. ACM, 2009.
To appear.
(PDF, 122118 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, R. Santhanam,
and R. Williams.
Fixed-polynomial size circuit bounds.
In Proceedings of the 24th IEEE Conference on Computational
Complexity. 2009.
To appear.
(PostScript, 8 pages, 236984 bytes)
(PDF, 196423 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)
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, 15 pages, 280526 bytes)
(PDF, 163671 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)
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)
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, 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)
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)
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 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,
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)
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)
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)
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)
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)
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 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)
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)
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, 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)
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
PNP=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.
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, 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. 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. 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)
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.