DBLP
Google
Scholar
ACM
DL Microsoft
Academic Search
Publications
- Tugkan Batu, Lance
Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White.
Testing closeness of
discrete distributions.
Journal of the ACM, 60(1):4:1-4:25, February 2013.
(PDF, 340776 bytes)
- L. Fortnow.
The Golden Ticket: P, NP
and the search for the impossible.
Princeton University Press, Princeton, 2013.
- L. Fortnow and
R. Sami.
Multi-outcome and multidimensional
market scoring rules.
Technical Report 1202.1712, arXiv.org e-Print archive, 2012.
(PDF, 170983 bytes)
- L. Fortnow, J. Lutz, and
E. Mayordomo.
Inseparability and strong
hypotheses for disjoint NP pairs.
Theory of Computing Systems, 51:229-247, 2012.
(PDF, 217956 bytes)
- L. Fortnow and
M. Budinich.
Repeated matching pennies
with limited randomness.
In Proceedings of the 12th ACM Conference on Electronic Commerce,
pages 111-118. ACM, New York, 2011.
(PDF, 214971 bytes)
- L. Fortnow and
J. Grochow.
Complexity classes of
equivalence problems revisited.
Information and Computation, 209(4):748-763, April 2011.
(PDF, 265990 bytes)
- L. Fortnow and
R. Santhanam.
Infeasibility of
instance compression and succinct PCPs for NP.
Journal of Computer and System Sciences, 77(1):91-106, January
2011.
Special issues celebrating Karp's Kyoto Prize.
(PDF, 240198 bytes)
- L. Fortnow and
R. Santhanam.
Robust simulations and
significant separations.
In L. Aceto, M. Henzinger, and J. Sgall, editors, Proceedings of the 38th
International Colloquium on Automata, Languages and Programming,
volume 6755 of Lecture Notes in Computer Science, pages
569-580. Springer Berlin / Heidelberg, 2011.
(PDF, 222845 bytes)
- L. Fortnow, J. Hitchcock,
A. Pavan, N.V. Vinodchandran, and F. Wang.
Extracting kolmogorov
complexity with applications to dimension zero-one laws.
Information and Computation, 209(4):627-636, April 2011.
(PDF, 196082 bytes)
- 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)
- H. Buhrman, L. Fortnow,
M. Koucky, J. Rogers, and N. Vereshchagin.
Does the polynomial
hierarchy collapse if onto functions are invertible?.
Theory of Computing Systems, 46(1):143-156, January 2010.
(PDF, 207830 bytes)
- Y. Chen, S. Dimitrov,
R. Sami, D. Reeves, D. Pennock, R. Hanson, L. Fortnow, and R. Gonen.
Gaming prediction
markets: Equilibrium strategies with a market maker.
Algorithmica, 58(4):930-969, December 2010.
(PDF, 311188 bytes)
- L. Fortnow.
The enduring legacy of the
Turing machine.
Ubiquity, 2010, December 2010.
Ubiquity Symposium on 'What is Computation?'.
(PDF, 136234 bytes)
- L. Fortnow and
R. Santhanam.
Bounding rationality by discounting time.
In Proceedings of The First Symposium on Innovations in Computer
Science, pages 143-156. Tsinghua University Press, Beijing, 2010.
(PDF, 164479 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)
- 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, pages 99-107. ACM, 2009.
(PDF, 145848 bytes)
- L. Fortnow.
Program equilibria and discounted
computation time.
In Proceedings of the 12th Conference on Theoretical Aspects of
Rationality and Knowledge, pages 128-133. ACM, 2009.
(PDF, 122118 bytes)
- L. Fortnow.
A simple proof of
Toda's theorem.
Theory of Computing, 5(7):135-140, 2009.
(PDF, 153987 bytes)
- L. Fortnow.
The status of the P versus NP
problem.
Communications of the ACM, 52(9):78-86, September 2009.
Review Article.
(PDF, 121989 bytes)
- L. Fortnow.
Time for computer science to grow
up.
Communications of the ACM, 52(8):33-35, August 2009.
Viewpoint Column.
(PDF, 66703 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. 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. Fortnow,
R. Impagliazzo, V. Kabanets, and C. Umans.
On the complexity of
succinct zero-sum games.
Computational Complexity, 17(3):353-376, October 2008.
(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.
(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.
(PDF, 329488 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)
- R. Beigel, L. Fortnow, and
W. Gasarch.
A tight lower bound for
restricted PIR protocols.
Computational Complexity, 15(1):82-91, May 2006.
(PDF, 173585 bytes)
- R. Beigel, L. Fortnow, and
F. Stephan.
Infinitely-often
autoreducible sets.
SIAM Journal on Computing, 6(3):595-608, 2006.
(PDF, 226040 bytes)
- E. Fischer and
L. Fortnow.
Tolerant versus
intolerant testing for Boolean properties.
Theory of Computing, 2(9):173-183, 2006.
(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.
(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 and
R. Santhanam.
Recent work on hierarchies
for semantic classes.
SIGACT News, 37(3):36-54, September 2006.
(PDF, 219493 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)
- 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.
(PDF, 166729 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.
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.
(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.
(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,
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.
(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.
(PDF, 288647 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)
- 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.
(PDF, 315749 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.
(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)
- H. Buhrman, L. Fortnow, and
S. Laplante.
Resource-bounded
Kolmogorov complexity revisited.
SIAM Journal on Computing, 31(3):887-905, 2002.
(PDF, 330983 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 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.
(PDF, 246100 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.
(PDF, 185644 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.
(PDF, 200261 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)
- 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.
(PDF, 124830 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)
- H. Buhrman, L. Fortnow,
D. van Melkebeek, and L. Torenvliet.
Separating complexity
classes using autoreducibility.
SIAM Journal on Computing, 29(5):1497-1520, 2000.
(PDF, 359060 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.
Relativized worlds
with an infinite hierarchy.
Information Processing Letters, 69(6):309-313, 1999.
(PDF, 167454 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)
- 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.
(PDF, 134707 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)
- J. Feigenbaum,
L. Fortnow, S. Laplante, and A. Naik.
On coherence,
random-self-reducibility, and self-correction.
Computational Complexity, 7(2):174-191, 1998.
(PDF, 286613 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 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.
(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)
- S. Fenner, L. Fortnow, and
S. Kurtz.
The isomorphism
conjecture holds relative to an oracle.
SIAM Journal on Computing, 25(1):193-206, 1996.
(PDF, 261915 bytes)
- S. Fenner, L. Fortnow, and
L. Li.
Gap-definability as a
closure property.
Information and Computation, 130(1):1-17, 1996.
(PDF, 245175 bytes)
- L. Fortnow and
M. Kummer.
On resource-bounded
instance complexity.
Theoretical Computer Science A, 161:123-140, 1996.
(PDF, 277574 bytes)
- L. Fortnow and
N. Reingold.
PP is closed under
truth-table reductions.
Information and Computation, 124(1):1-6, 1996.
(PDF, 182944 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.
- L. Fortnow and
S. Laplante.
Circuit lower bounds a
la Kolmogorov.
Information and Compuation, 123(1):121-126, 1995.
(PDF, 206774 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.
(PDF, 253191 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.
(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 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.
(PDF, 207194 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. 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.
(PDF, 128883 bytes)
- L. Fortnow, J. Rompel, and
M. Sipser.
On the power of
multi-prover interactive protocols.
Theoretical Computer Science A, 134:545-557, 1994.
(PDF, 187372 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.
(PDF, 206125 bytes)
- J. Feigenbaum and
L. Fortnow.
On the random-self-reducibility of
complete sets.
SIAM Journal on Computing, 22:994-1005, 1993.
(PDF, 256669 bytes)
- L. Fortnow and C. Lund.
Interactive proof
systems and alternating time-space complexity.
Theoretical Computer Science A, 113:55-73, 1993.
(PDF, 281930 bytes)
- L. Fortnow and
M. Szegedy.
On the power of
two-local random reductions.
Information Processing Letters, 44(6):303-306, 1992.
(PDF, 138968 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.
(PDF, 190234 bytes)
- L. Babai and L. Fortnow.
Arithmetization: A new method in
structural complexity theory.
Computational Complexity, 1(1):41-66, 1991.
(PDF, 311617 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. Babai, L. Fortnow, and
C. Lund.
Nondeterministic exponential
time has two-prover interactive protocols.
Computational Complexity, 1(1):3-40, 1991.
(PDF, 399398 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)
- L. Fortnow and M. Sipser.
Are there interactive
protocols for co-NP languages?.
Information Processing Letters, 28:249-251, 1988.
(PDF, 105622 bytes)
Important Notes:
- 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.
- Free Adobe
PDF Reader
- Postscript links have been removed and converted to PDFs as
necessary. Old postscript files are still available but no longer
maintained.
- If you have trouble downloading these
papers, .
Back to Lance Fortnow Main Page.