\n \n \n
\n
\n\n \n \n \n \n \n \n One Bit of Advice.\n \n \n \n \n\n\n \n Buhrman, H.; Chang, R.; and Fortnow, L.\n\n\n \n\n\n\n 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.\n
\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n \n
paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 6 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@incollection{np1,\nshow = 1,\ntitle = "One Bit of Advice",\nauthor = "H. Buhrman and R. Chang and L. Fortnow",\nbooktitle = stacs20,\nvolume = 2607,\nyear = 2003,\naddress = "Berlin",\npublisher = springer,\nseries = lncs,\npages = "547-558",\nurl = "https://dx.doi.org/10.1007/3-540-36494-3_48",\ndoi = "10.1007/3-540-36494-3_48",\nurl_Paper = "https://lance.fortnow.com/papers/files/np1.pdf"}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Infinitely-often Autoreducible Sets.\n \n \n \n \n\n\n \n Beigel, R.; Fortnow, L.; and Stephan, F.\n\n\n \n\n\n\n In
Proceedings of the 14th Annual International Symposium on Algorithms and Computation, volume 2906, of Lecture Notes in Computer Science, pages 98-107. Springer, Berlin, 2003.\n
\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n \n
paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@incollection{ioauto-C,\ntitle = "Infinitely-often Autoreducible Sets",\nauthor = "R. Beigel and L. Fortnow and F. Stephan",\nbooktitle = isaac14,\nseries = lncs,\naddress = "Berlin",\npublisher = springer,\nurl = "https://www.springerlink.com/link.asp?id=pbprbxp2mmnk5cnq",\nyear = 2003,\npages = "98-107",\nvolume = 2906,\nurl_Paper = "https://lance.fortnow.com/papers/files/ioauto.pdf"}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Quantum Property Testing.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; Newman, I.; and Röhrig, H.\n\n\n \n\n\n\n In
Proceedings of the Fourteenth ACM-SIAM Symposium on Discrete Algorithms, pages 480-488. ACM, New York, 2003.\n
\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n \n
paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@incollection{qprop-C,\ntitle = "Quantum Property Testing",\nauthor = "H. Buhrman and L. Fortnow and I. Newman and H. R{\\"{o}}hrig",\npublisher = "ACM",\naddress = "New York",\nbooktitle = soda14,\npages = "480-488",\nyear = 2003,\nurl = "https://portal.acm.org/citation.cfm?id=644108.644188",\nurl_Paper = "https://lance.fortnow.com/papers/files/qprop.pdf"}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Sublinear approximation of Euclidean minimum spanning tree.\n \n \n \n \n\n\n \n Czumaj, A.; Ergün, F.; Fortnow, L.; Magen, A.; Newman, I.; Rubinfeld, R.; and Sohler, C.\n\n\n \n\n\n\n In
Proceedings of the Fourteenth ACM-SIAM Symposium on Discrete Algorithms, pages 813-822. ACM, New York, 2003.\n
\n\n
\n\n
\n\n
\n\n \n \n
paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@incollection{emst-C,\ntitle = "Sublinear approximation of {Euclidean} minimum spanning tree",\nauthor = "Artur Czumaj and Funda Erg{\\"{u}}n and Lance Fortnow and\nAvner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler",\npublisher = "ACM",\naddress = "New York",\nbooktitle = soda14,\npages = "813-822",\nyear = 2003,\nurl_Paper = "https://lance.fortnow.com/papers/files/emst.pdf"}\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Using Depth to Capture Average-Case Complexity.\n \n \n \n \n\n\n \n Antunes, L.; Fortnow, L.; and Vinodchandran, V.\n\n\n \n\n\n\n In
14th International Symposium on Fundamentals of Computation Theory, volume 2751, of Lecture Notes in Computer Science, pages 303-310. Springer, Berlin, 2003.\n
Journal Version merged into Computational depth: Concept and applications.\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@incollection{depth2-CH,\nshow = 1,\ntitle = "Using Depth to Capture Average-Case Complexity",\nauthor = "L. Antunes and L. Fortnow and V. Vinodchandran",\nbooktitle = fct14,\npublisher= "Springer",\naddress = "Berlin",\nseries = lncs,\nvolume = 2751,\nyear = 2003,\npages = "303-310",\nurl = "https://dx.doi.org/10.1007/b11926",\ndoi = "10.1007/b11926",\nnote = {Journal Version merged into\n<a href="https://bibbase.org/network/publication/antunes-fortnow-vanmelkebeek-vinodchandran-computationaldepthconceptandapplications-2006">Computational depth: Concept and applications</a>.}}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n Using Depth to Capture Average-Case Complexity.\n \n \n \n\n\n \n Antunes, L.; Fortnow, L.; and Vinodchandran, V.\n\n\n \n\n\n\n In
14th International Symposium on Fundamentals of Computation Theory, volume 2751, of Lecture Notes in Computer Science, pages 303-310. Springer, Berlin, 2003.\n
\n\n
\n\n
\n\n
\n\n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@incollection{depth2-C,\ntitle = "Using Depth to Capture Average-Case Complexity",\nauthor = "L. Antunes and L. Fortnow and V. Vinodchandran",\nbooktitle = fct14,\npublisher= "Springer",\naddress = "Berlin",\nseries = lncs,\nvolume = 2751,\nyear = 2003,\npages = "303-310"}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Are Cook and Karp Ever the Same?.\n \n \n \n \n\n\n \n Beigel, R.; and Fortnow, L.\n\n\n \n\n\n\n In
Proceedings of the 18th IEEE Conference on Computational Complexity, pages 333-336. IEEE, New York, 2003.\n
\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n \n
paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 2 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@incollection{BF-turing,\nshow = 1,\ntitle = "Are {Cook} and {Karp} Ever the Same?",\nauthor = "R. Beigel and L. Fortnow",\nurl = "https://dx.doi.org/10.1109/CCC.2003.1214431",\ndoi = "10.1109/CCC.2003.1214431",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict18,\npages = "333-336",\nyear = 2003,\nurl_Paper = "https://lance.fortnow.com/papers/files/turing.pdf"}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Some Results on Derandomization.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; and Pavan, A.\n\n\n \n\n\n\n In
Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science, volume 2607, of Lecture Notes in Computer Science, pages 212-222. Springer, Berlin, 2003.\n
\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n \n
paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@incollection{BF-derand,\ntitle = "Some Results on Derandomization",\nauthor = "H. Buhrman and L. Fortnow and A. Pavan",\nbooktitle = stacs20,\nvolume = 2607,\nseries = lncs,\nyear = 2003,\naddress = "Berlin",\npublisher = springer,\npages = "212-222",\nurl = "https://www.springerlink.com/link.asp?id=3vwf47nau7r108ww",\nurl_Paper = "https://lance.fortnow.com/papers/files/derand.pdf"}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n One Complexity Theorist's View of Quantum Computing.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n
Theoretical Computer Science, 292(3): 597-610. 2003.\n
Special Issue of papers presented at the second workshop on Algorithms in Quantum Information Processing.\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n \n
paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 3 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@article{quantview-O,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "One Complexity Theorist's View of Quantum Computing",\nurl = "https://dx.doi.org/10.1016/S0304-3975(01)00377-2",\ndoi = "10.1016/S0304-3975(01)00377-2",\njournal = tcs,\nyear = 2003,\nvolume = 292,\nnumber = 3,\npages = "597-610",\nnote = "Special Issue of papers presented at the second workshop on Algorithms\nin Quantum Information Processing.",\nurl_Paper = "https://lance.fortnow.com/papers/files/quantview.pdf"}\n\n
\n
\n\n\n\n
\n\n\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Inverting onto functions.\n \n \n \n \n\n\n \n Fenner, S.; Fortnow, L.; Naik, A.; and Rogers, J.\n\n\n \n\n\n\n
Information and Computation, 186(1): 90-103. October 2003.\n
\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n \n
paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@article{Q-J,\nshow = 1,\ntitle = "Inverting onto functions",\nauthor = "S. Fenner and L. Fortnow and A. Naik and J. Rogers",\njournal = iandcomp,\nurl = "https://dx.doi.org/10.1016/S0890-5401(03)00119-6",\ndoi = "10.1016/S0890-5401(03)00119-6",\nyear = 2003,\nvolume = 186,\nnumber = 1,\nmonth = oct,\npages = "90-103",\nURL_PAPER = "https://lance.fortnow.com/papers/files/q.pdf"}\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n A Short History of Computational Complexity.\n \n \n \n \n\n\n \n Fortnow, L.; and Homer, S.\n\n\n \n\n\n\n
Bulletin of the European Association for Theoretical Computer Science, 80. June 2003.\n
Computational Complexity Column.\n\n
\n\n
\n\n
\n\n \n \n
paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@article{history,\nshow = 1,\nauthor = "L. Fortnow and S. Homer",\ntitle = "A Short History of Computational Complexity",\nyear = 2003,\nmonth = jun,\njournal = beatcs,\nvolume = 80,\nnote = "Computational Complexity Column.",\nurl_Paper = "https://lance.fortnow.com/papers/files/history.pdf" }\n%booktitle = "The History of Mathematical Logic",\n%editor = "D. van Dalen and J. Dawson and A. Kanamori",\n%address = "Amsterdam",\n\n
\n
\n\n\n\n
\n\n\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Proving SAT does not have Small Circuits with an Application to the Two Queries Problem.\n \n \n \n \n\n\n \n Fortnow, L.; Pavan, A.; and Sengupta, S.\n\n\n \n\n\n\n In
Proceedings of the 18th IEEE Conference on Computational Complexity, pages 347-350. IEEE, New York, 2003.\n
\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n \n
paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@incollection{satcirc,\ntitle = "Proving {SAT} does not have Small Circuits with\nan Application to the Two Queries Problem",\nauthor = "L. Fortnow and A. Pavan and S. Sengupta",\nurl = "https://dx.doi.org/10.1109/CCC.2003.1214433",\ndoi = "10.1109/CCC.2003.1214433",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict18,\npages = "347-350",\nyear = 2003,\nurl_Paper = "https://lance.fortnow.com/papers/files/2q.pdf"}\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Sophistication Revisited.\n \n \n \n \n\n\n \n Antunes, L.; and Fortnow, L.\n\n\n \n\n\n\n In
Proceedings of the 30th International Colloquium on Automata, Languages and Programming, volume 2719, of Lecture Notes in Computer Science, pages 267-277. Springer, 2003.\n
\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n \n
paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@incollection{soph,\nauthor = "L. Antunes and L. Fortnow",\ntitle = "Sophistication Revisited",\nbooktitle = icalp30,\nyear = 2003,\npublisher = springer,\nseries = lncs,\nurl = "https://www.springerlink.com/link.asp?id=qj45fepf4l5fhv7w",\nurl_Paper = "https://lance.fortnow.com/papers/files/soph.pdf",\nvolume = 2719,\npages = "267-277"}\n\n
\n
\n\n\n\n
\n\n\n\n\n\n