H. Buhrman, L. Fortnow,
M. Koucky, and B. Loff.
Derandomizing from random strings.
In Proceedings of the 25th IEEE Conference on Computational
Complexity, pages 58-63. IEEE, 2010.
(PDF, 189516 bytes)
L. Fortnow and
R. Santhanam.
Bounding rationality by discounting time.
In Proceedings of The First Symposium on Innovations in Computer
Science. Tsinghua University Press, Beijing, 2010.
To appear.
(PDF, 164479 bytes)
L. Fortnow, J. Lutz, and
E. Mayordomo.
Inseparability and
strong hypotheses for disjoint NP pairs.
In Jean-Yves Marion and Thomas Schwentick, editors, Proceedings of the
27th Symposium on Theoretical Aspects of Computer Science, volume 5 of
Leibniz International Proceedings in Informatics (LIPIcs), pages
395-404. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl,
Germany, 2010.
(PDF, 2302800 bytes)
L. Antunes and
L. Fortnow.
Sophistication
revisited.
Theory of Computing Systems, 45(1):150-161, June 2009.
(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, pages 298-303. IEEE, 2009.
(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, volume 5555, pages 195-209. Springer,
2009.
(PDF, 237327 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, pages 19-26. IEEE, 2009.
(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.
(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.
(PDF, 152939 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.
(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).
(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.
(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.
(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.
(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.
(PDF, 195177 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.
(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.
(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.
(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.
(PDF, 176082 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.
(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.
(PDF, 258739 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.
(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.
(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.
(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.
(PDF, 151351 bytes)
R. Downey and
L. Fortnow.
Uniformly hard
languages.
Theoretical Computer Science, 298(2):303-315, 2003.
(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.
(PDF, 426986 bytes)
S. Fenner, L. Fortnow, A. Naik,
and J. Rogers.
Inverting onto
functions.
Information and Computation, 186(1):90-103, October 2003.
(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.
(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.
(PDF, 230775 bytes)
R. Beigel, L. Fortnow, and
A. Pavan.
Membership comparable and p-selective sets.
Technical Report 2002-006N, NEC Research Institute, 2002.
(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.
(PDF, 185644 bytes)
H. Buhrman, S. Fenner,
L. Fortnow, and L. Torenvliet.
Two oracles that force a
big crunch.
Computational Complexity, 10(2):93-116, 2001.
(PDF, 318933 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.
(PDF, 180038 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.
(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.
(PDF, 203232 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.
(PDF, 240829 bytes)
L. Fortnow.
Diagonalization.
Bulletin of the European Association for Theoretical Computer
Science, 71:102-112, June 2000.
Computational Complexity Column.
(PDF, 208760 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.
(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.
(PDF, 201485 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.
(PDF, 125736 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.
(PDF, 186171 bytes)
L. Fortnow,
J. Goldsmith, M. Levy, and S. Mahaney.
L-printable sets.
SIAM Journal on Computing, 28(1):137-151, 1999.
(PDF, 271049 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.
(PDF, 77696 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.
(PDF, 169220 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.
(PDF, 267410 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.
(PDF, 189465 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.
(PDF, 229745 bytes)
L. Fortnow.
Counting complexity.
In L. Hemaspaandra and A. Selman, editors, Complexity Theory
Retrospective II, pages 81-107. Springer, 1997.
Survey.
(PDF, 307710 bytes)
S. Fenner, L. Fortnow, and
W. Gasarch.
Complexity theory
newsflash.
SIGACT News, 23(3):126, September 1996.
Parody.
(PDF, 72530 bytes)
L. Fortnow and
T. Yamakami.
Generic separations.
Journal of Computer and System Sciences, 52(1):191-197, 1996.
(PDF, 240463 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.
(PDF, 358459 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.
(PDF, 119753 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.
(PDF, 232137 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.
(PDF, 214869 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.
(PDF, 456901 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.
(PDF, 274887 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.
(PDF, 213919 bytes)
L. Fortnow.
Complexity-theoretic aspects of interactive proof systems.
PhD thesis, Massachusetts Institute of Technology, May 1989.
Tech Report MIT/LCS/TR-447.
(PDF, 443878 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 PDF files are the most recent versions of each paper
and may not correspond to the referenced version.