\n\n \n\n \n\n \n \n\n \n\n \n \n\n \n\n \n

\n generated by\n \n $\"bibbase.org\"\n$ \n \n

\n \n\n

\n\n

\n \n Group by\n \n \n
- \n Year\n
- \n Author\n
- \n Type\n
- \n Keyword\n
- \n Downloads\n
\n
\n \n \n \n \n
- \n \n Expand/Collapse All\n \n
- \n \n Download BibTeX\n \n
- \n \n RSS Feed\n \n
\n

\n\n\n

\n\n Excellent! Next you can\n create a new website with this list, or\n embed it in an existing web page by copying & pasting\n any of the following snippets.\n\n

\n JavaScript\n (easiest)\n

\n            <script src=\"https://bibbase.org/show?bib=https://github.com/fortnow/pubs2/raw/master/pubs.bib&filter=show:1&jsonp=1&jsonp=1\"></script>\n

\n\n PHP\n

\n            <?php\n            $contents = file_get_contents(\"https://bibbase.org/show?bib=https://github.com/fortnow/pubs2/raw/master/pubs.bib&filter=show:1&jsonp=1\");\n            print_r($contents);\n            ?>\n

\n\n iFrame\n (not recommended)\n

\n            <iframe src=\"https://bibbase.org/show?bib=https://github.com/fortnow/pubs2/raw/master/pubs.bib&filter=show:1&jsonp=1\"></iframe>\n

\n\n

\n For more details see the documention.\n

\n\n

\n\n This is a preview! To use this list on your own web site\n or create a new web site from it,\n create a free account. The file will be added\n and you will be able to edit it in the File Manager.\n We will show you instructions once you've created your account.\n

\n\n

To the site owner:

\n\n

Action required! Mendeley is changing its\n API. In order to keep using Mendeley with BibBase past April\n 14th, you need to:\n

renew the authorization for BibBase on Mendeley, and
update the BibBase URL\n in your page the same way you did when you initially set up\n this page.\n

\n\n

\n \n \n Fix it now\n

\n\n

\n\n\n

\n \n \n

\n \n 2022\n \n \n (1)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Fifty Years of P vs. NP and the Possibility of the Impossible.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Communications of the ACM, 65(1): 76–85. January 2022.\n \n\n\n\n
\n\n\n\n \n \n $\"Fifty$ Paper\n \n \n \n $\"Fifty$ 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 abstract \n \n\n \n \n \n 41 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{pvnp50-O,\n\tshow = 1,\n\tauthor = {Fortnow, Lance},\n\ttitle = {Fifty Years of {P vs. NP} and the Possibility of the Impossible},\n\tyear = {2022},\n\tissue_date = {January 2022},\n\tpublisher = {Association for Computing Machinery},\n\taddress = {New York, NY, USA},\n\tvolume = {65},\n\tnumber = {1},\n\tissn = {0001-0782},\n\turl = {https://cacm.acm.org/magazines/2022/1/257448-fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/fulltext},\n\tdoi = {10.1145/3460351},\n\tabstract = {Advances in algorithms, machine learning, and hardware can help tackle many NP-hard problems once thought impossible.},\n\tjournal = {Communications of the ACM},\n\tmonth = jan,\n\tpages = {76–85},\n\tnumpages = {10},\n\turl_Paper = "https://lance.fortnow.com/papers/files/pvnp50.pdf"}\n

\n\n\n\n\n\n

\n\n

\n \n 2021\n \n \n (1)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Worlds to Die Harder For: Open Oracle Questions for the 21st Century.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n SIGACT News, 52(3). September 2021.\n Open Problems Column edited by William Gasarch\n\n\n\n
\n\n\n\n \n \n $\"Worlds$ Paper\n \n \n \n $\"Worlds$ 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 24 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{Oracles-open-O,\n\tshow = 1,\nauthor = "L. Fortnow",\njournal = sigact,\nvolume = 52,\nnumber = 3,\nmonth = sep,\nyear = 2021,\ntitle = "Worlds to Die Harder For: {O}pen Oracle Questions for the 21st Century",\nnote = "Open Problems Column edited by William Gasarch",\nurl = "https://dl.acm.org/doi/abs/10.1145/3494656.3494663",\ndoi = "10.1145/3494656.3494663",\nurl_Paper = "https://lance.fortnow.com/papers/files/open-oracle-survey.pdf"}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2018\n \n \n (3)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Quantized BvND: A Better Solution for Optical and Hybrid Switching in Data Center Networks.\n \n \n \n \n\n\n \n Liu, L.; Xu, J.; and Fortnow, L.\n\n\n \n\n\n\n In IEEE/ACM 11th International Conference on Utility and Cloud Computing, pages 237-246. IEEE, New York, 2018.\n \n\n\n\n
\n\n\n\n \n \n $\"Quantized$ Paper\n \n \n \n $\"Quantized$ 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 10 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{qbvnd-C,\nshow = 1,\nauthor = "L. Liu and J. Xu and L. Fortnow",\ntitle = "Quantized {BvND}: {A} Better Solution for Optical and Hybrid Switching in Data Center Networks",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = "IEEE/ACM 11th International Conference on Utility and Cloud Computing",\npages = "237-246",\nyear = 2018,\nurl = "https://dx.doi.org/10.1109/UCC.2018.00032",\ndoi = "10.1109/UCC.2018.00032",\nurl_Paper = "https://lance.fortnow.com/papers/files/qbvnd.pdf"}\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Best First Fit (BFF): An Approach to Partially Reconfigurable Hybrid Circuit and Packet Switching.\n \n \n \n \n\n\n \n Liu, L.; Gong, L.; Yang, S.; Xu, J.; and Fortnow, L.\n\n\n \n\n\n\n In 2018 IEEE 11th International Conference on Cloud Computing (CLOUD), pages 426-433. Jul 2018.\n \n\n\n\n
\n\n\n\n \n \n $\"Best$ Paper\n \n \n \n $\"Best$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n \n \n\n\n\n

@incollection{BFF-C,\nshow = 1,\nauthor = "L. Liu and L. Gong and S. Yang and J. Xu and L. Fortnow",\nbooktitle = {2018 IEEE 11th International Conference on Cloud Computing (CLOUD)},\ntitle = {Best First Fit ({BFF}): {An} Approach to Partially Reconfigurable Hybrid Circuit and Packet Switching},\nyear = {2018},\npages = {426-433},\nkeywords={Switching circuits;Optical switches;Scheduling;Task analysis;Schedules;Delays},\ndoi = {10.1109/CLOUD.2018.00060},\nurl = {https://dx.doi.org/10.1109/CLOUD.2018.00060},\nISSN = {2159-6190},\nmonth={Jul},\nurl_Paper = "https://lance.fortnow.com/papers/files/BFF.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n 2-Hop Eclipse: A Fast Algorithm for Bandwidth-Efficient Data Center Switching.\n \n \n \n \n\n\n \n Liu, L.; Gong, L.; Yang, S.; Xu, J.; and Fortnow, L.\n\n\n \n\n\n\n In Luo, M.; and Zhang, L., editor(s), Cloud Computing – CLOUD 2018, pages 69–83, 2018. Springer International Publishing\n Best Student Paper Award winner.\n\n\n\n
\n\n\n\n \n \n $\"2-Hop$ Paper\n \n \n \n $\"2-Hop$ 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 abstract \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

@InProceedings{2hop-C,\nshow = 1,\nauthor="Liu, Liang\nand Gong, Long\nand Yang, Sen\nand Xu, Jim\nand Fortnow, Lance",\neditor="Luo, Min\nand Zhang, Liang-Jie",\ntitle="{2-Hop Eclipse}: {A} Fast Algorithm for Bandwidth-Efficient Data Center Switching",\nbooktitle="Cloud Computing -- CLOUD 2018",\nyear="2018",\npublisher="Springer International Publishing",\npages="69--83",\nabstract="A hybrid-switched data center network interconnects its racks of servers with a combination of a fast circuit switch that a schedule can reconfigure at significant cost and a much slower packet switch that a schedule can reconfigure at negligible cost. Given a traffic demand matrix between the racks, how can we best compute a good circuit switch configuration schedule that meets most of the traffic demand, leaving as little as possible for the packet switch to handle?",\nisbn="978-3-319-94295-7",\nnote = "Best Student Paper Award winner.",\nurl = "https://doi.org/10.1007/978-3-319-94295-7_5",\ndoi = "10.1007/978-3-319-94295-7_5",\nurl_Paper = "https://lance.fortnow.com/papers/files/2hop.pdf"}\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2017\n \n \n (3)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Compression Complexity.\n \n \n \n \n\n\n \n Fenner, S.; and Fortnow, L.\n\n\n \n\n\n\n Technical Report 1702.04779, arXiv.org e-Print archive, February 2017.\n \n\n\n\n
\n\n\n\n \n \n $\"Compression$ paper\n \n \n \n $\"Compression$ Paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 21 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n \n \n\n\n\n

@techreport{compression-U,\nshow = 1,\n   author = {{Fenner}, S. and {Fortnow}, L.},\n    title = "{Compression Complexity}",\n  journal = {ArXiv e-prints},\narchivePrefix = "arXiv",\n   number = {1702.04779},\n   institution = arxiv,\n primaryClass = "cs.CC",\n keywords = {Computer Science - Computational Complexity},\n     year = 2017,\n    month = feb,\n   adsurl = {https://adsabs.harvard.edu/abs/2017arXiv170204779F},\n   url_Paper = "https://lance.fortnow.com/papers/files/compression.pdf",\n   url = "https://arxiv.org/abs/1702.04779",\n  adsnote = {Provided by the SAO/NASA Astrophysics Data System}\n}\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Robust simulations and significant separations.\n \n \n \n \n\n\n \n Fortnow, L.; and Santhanam, R.\n\n\n \n\n\n\n Information and Computation, 256(Supplement C): 149 - 159. 2017.\n \n\n\n\n
\n\n\n\n \n \n $\"Robust$ Paper\n \n \n \n $\"Robust$ 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 7 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{robust-J,\nshow = 1,\ntitle = "Robust simulations and significant separations",\njournal = "Information and Computation",\nvolume = "256",\nnumber = "Supplement C",\npages = "149 - 159",\nyear = "2017",\nissn = "0890-5401",\ndoi = "10.1016/j.ic.2017.07.002",\nurl = "https://www.sciencedirect.com/science/article/pii/S0890540117301037",\nauthor = "L. Fortnow and R. Santhanam",\nurl_Paper = "https://lance.fortnow.com/papers/files/robust.pdf"\n}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Complexity with Rod.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n In Day, A.; Fellows, M.; Greenberg, N.; Khoussainov, B.; Melnikov, A.; and Rosamond, F., editor(s), Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, pages 115–121. Springer International Publishing, Cham, 2017.\n \n\n\n\n
\n\n\n\n \n \n $\"Complexity$ Paper\n \n \n \n $\"Complexity$ 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

@Incollection{complexityrod-O,\nshow = 1,\nauthor="L. Fortnow",\neditor="A. Day and M. Fellows and N. Greenberg and B. Khoussainov and A. Melnikov and F. Rosamond",\ntitle="Complexity with {Rod}",\nbookTitle="Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday",\nyear="2017",\npublisher="Springer International Publishing",\naddress="Cham",\npages="115--121",\nisbn="978-3-319-50062-1",\ndoi="10.1007/978-3-319-50062-1_8",\nurl="https://dx.doi.org/10.1007/978-3-319-50062-1_8",\nurl_Paper = "https://lance.fortnow.com/papers/files/Downey.pdf"}\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2016\n \n \n (3)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Randomized Algorithms for Dynamic Storage Load-Balancing.\n \n \n \n \n\n\n \n Liu, L.; Wang, Y.; Fortnow, L.; Li, J.; and Xu, J.\n\n\n \n\n\n\n In Proceedings of the Seventh ACM Symposium on Cloud Computing, of SoCC '16, pages 210–222. ACM, New York, NY, USA, 2016.\n \n\n\n\n
\n\n\n\n \n \n $\"Randomized$ Paper\n \n \n \n $\"Randomized$ 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 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n \n \n \n \n \n \n\n\n\n

@incollection{dancing-socc,\nshow = 1,\nauthor = "L. Liu and Y. Wang and L. Fortnow and J. Li and J. Xu",\n  title = {{R}andomized Algorithms for Dynamic Storage Load-Balancing},\n booktitle = {Proceedings of the Seventh ACM Symposium on Cloud Computing},\n series = {SoCC '16},\n year = {2016},\n isbn = {978-1-4503-4525-5},\n location = {Santa Clara, CA, USA},\n pages = {210--222},\n numpages = {13},\n url = {https://doi.acm.org/10.1145/2987550.2987572},\n doi = {10.1145/2987550.2987572},\n acmid = {2987572},\n publisher = {ACM},\n address = {New York, NY, USA},\n keywords = {diversity requirement, load distribution, load-balancing},\n url_paper = {https://lance.fortnow.com/papers/files/loadbalancing.pdf}\n }\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Loopholes.\n \n \n \n \n\n\n \n Chung, K.; and Fortnow, L.\n\n\n \n\n\n\n The Economic Journal, 126(595): 1774–1797. 2016.\n \n\n\n\n
\n\n\n\n \n \n $\"Loopholes$ Paper\n \n \n \n $\"Loopholes$ 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 8 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{loopholes-J,\nauthor = "K. Chung and L. Fortnow",\ntitle = {Loopholes},\njournal = {The Economic Journal},\nvolume = {126},\nnumber = {595},\nissn = {1468-0297},\nurl = {https://dx.doi.org/10.1111/ecoj.12203},\ndoi = {10.1111/ecoj.12203},\npages = {1774--1797},\nyear = {2016},\nshow = 1,\nurl_Paper = "https://lance.fortnow.com/papers/files/loopholes.pdf",\n}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n New Non-Uniform Lower Bounds for Uniform Classes.\n \n \n \n \n\n\n \n Fortnow, L.; and Santhanam, R.\n\n\n \n\n\n\n In Raz, R., editor(s), 31st Conference on Computational Complexity (CCC 2016), volume 50, of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016.\n \n\n\n\n
\n\n\n\n \n \n $\"New$ paper\n \n \n \n $\"New$ 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

@incollection{sublinear-C,\n author = "L. Fortnow and Rahul Santhanam",\n  title =\t{{New Non-Uniform Lower Bounds for Uniform Classes}},\n  booktitle =\t{31st Conference on Computational Complexity (CCC 2016)},\n  pages =\t{19:1--19:14},\n  series =\t{Leibniz International Proceedings in Informatics (LIPIcs)},\n  ISBN =\t{978-3-95977-008-8},\n  ISSN =\t{1868-8969},\n  year =\t{2016},\n  volume =\t{50},\n  editor =\t{Ran Raz},\n  publisher =\t{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},\n  address =\t{Dagstuhl, Germany},\n  URN =\t\t{urn:nbn:de:0030-drops-58503},\nshow = 1,\nurl_Paper = "https://lance.fortnow.com/papers/files/sublinear.pdf",\nurl = "https://dx.doi.org/10.4230/LIPIcs.CCC.2016.19",\n  doi =\t\t{10.4230/LIPIcs.CCC.2016.19},\n  annote =\t{Keywords: Computational complexity, nondeterminism, nonuniform complexity}\n}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2013\n \n \n (4)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Learning Reductions to Sparse Sets.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; Hitchcock, J.; and Loff, B.\n\n\n \n\n\n\n In Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, volume 8087, of Lecture Notes in Computer Science, pages 243-253. Springer, Berlin, 2013.\n \n\n\n\n
\n\n\n\n \n \n $\"Learning$ Paper\n \n \n \n $\"Learning$ 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

@incollection{NPLT-C,\nauthor = "H. Buhrman and L. Fortnow and J. Hitchcock and B. Loff",\ntitle = "Learning Reductions to Sparse Sets",\nbooktitle = mfcs38,\nyear = 2013,\naddress = "Berlin",\nseries = lncs,\npublisher = springer,\nvolume = 8087,\npages = "243-253",\nshow = 1,\nurl = "https://dx.doi.org/10.1007/978-3-642-40313-2_23",\ndoi = "10.1007/978-3-642-40313-2_23",\nurl_Paper = "https://lance.fortnow.com/papers/files/NPLT1.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Turing's Dots.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n In Alan Turing: His Work and Impact, pages 227-228. Elsevier, Amsterdam, 2013.\n \n\n\n\n
\n\n\n\n \n \n $\"Turing's$ paper\n \n \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

@incollection{dots-O,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "Turing's Dots",\nbooktitle = "Alan Turing: His Work and Impact",\nyear = 2013,\naddress = "Amsterdam",\npublisher = "Elsevier",\npages = "227-228",\nurl_paper = {https://lance.fortnow.com/papers/files/Turing-Dots.pdf}\n}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Testing Closeness of Discrete Distributions.\n \n \n \n \n\n\n \n Batu, T.; Fortnow, L.; Rubinfeld, R.; Smith, W. D.; and White, P.\n\n\n \n\n\n\n Journal of the ACM, 60(1): 4:1–4:25. February 2013.\n \n\n\n\n
\n\n\n\n \n \n $\"Testing$ Paper\n \n \n \n $\"Testing$ 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 7 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n \n \n \n \n \n \n\n\n\n

@ARTICLE{closeness-J,\nshow = 1,\nauthor = {Batu, Tu\\u{g}kan and Fortnow, Lance and Rubinfeld, Ronitt and Smith, Warren D. and White, Patrick},\n title = {Testing Closeness of Discrete Distributions},\n journal = jacm,\n issue_date = {February 2013},\n volume = {60},\n number = {1},\n month = feb,\n year = {2013},\n issn = {0004-5411},\n pages = {4:1--4:25},\n articleno = {4},\n numpages = {25},\n url = {https://dl.acm.org/authorize?N09527},\n doi = {10.1145/2432622.2432626},\n acmid = {2432626},\n publisher = {ACM},\n address = {New York, NY, USA},\n keywords = {Testing properties of distributions, statistical distance, testing Markov chains for mixing},\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/closeness.pdf}}\n\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n The Golden Ticket: P, NP and the search for the impossible.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Princeton University Press, Princeton, 2013.\n \n\n\n\n
\n\n\n\n \n \n $\"The$ Paper\n \n \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

@BOOK{PNP-B,\n\tshow = 1,\n\tAUTHOR = "L. Fortnow",\n\tTITLE = "The Golden Ticket: {P}, {NP} and the search for the impossible",\n\tPUBLISHER = "Princeton University Press",\n\tADDRESS ="Princeton",\n\tYEAR = "2013",\n\turl = "https://goldenticket.fortnow.com" }\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2012\n \n \n (2)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Multi-outcome and Multidimensional Market Scoring Rules.\n \n \n \n \n\n\n \n Fortnow, L.; and Sami, R.\n\n\n \n\n\n\n Technical Report 1202.1712, arXiv.org e-Print archive, 2012.\n \n\n\n\n
\n\n\n\n \n \n $\"Multi-outcome$ Paper\n \n \n \n $\"Multi-outcome$ paper\n \n \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

@techreport{scoring2D-U,\nshow = 1,\ntitle = "Multi-outcome and Multidimensional Market Scoring Rules",\nauthor = "L. Fortnow and R. Sami",\nyear = 2012,\ninstitution = arxiv,\nurl = "https://arxiv.org/abs/1202.1712",\nnumber = "1202.1712",\nurl_Paper = "https://lance.fortnow.com/papers/files/scoring2d.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Inseparability and Strong Hypotheses for Disjoint NP Pairs.\n \n \n \n \n\n\n \n Fortnow, L.; Lutz, J.; and Mayordomo, E.\n\n\n \n\n\n\n Theory of Computing Systems, 51: 229-247. 2012.\n \n\n\n\n
\n\n\n\n \n \n $\"Inseparability$ Paper\n \n \n \n $\"Inseparability$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n \n \n\n\n\n

@article {insep-J,\nshow = 1,\n   author = {L. Fortnow and J. Lutz and E. Mayordomo},\n   title = {Inseparability and Strong Hypotheses for Disjoint {NP} Pairs},\n   journal = {Theory of Computing Systems},\n   publisher = {Springer New York},\n   issn = {1432-4350},\n   keyword = {Computer Science},\n   pages = {229-247},\n   volume = {51},\n   issue = {2},\n   url = {https://dx.doi.org/10.1007/s00224-011-9326-7},\n   doi = "10.1007/s00224-011-9326-7",\n   year = {2012},\nurl_Paper = "https://lance.fortnow.com/papers/files/insep.pdf"\n}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2011\n \n \n (4)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Complexity Classes of Equivalence Problems Revisited.\n \n \n \n \n\n\n \n Fortnow, L.; and Grochow, J.\n\n\n \n\n\n\n Information and Computation, 209(4): 748-763. April 2011.\n \n\n\n\n
\n\n\n\n \n \n $\"Complexity$ Paper\n \n \n \n $\"Complexity$ 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

@article{equiv-J,\nshow = 1,\nauthor = "L. Fortnow and J. Grochow",\ntitle = "Complexity Classes of Equivalence Problems Revisited",\njournal = iandcomp,\nvolume = 209,\nnumber = 4,\nmonth = apr,\nyear = 2011,\nurl = "https://dx.doi.org/10.1016/j.ic.2011.01.006",\ndoi = "10.1016/j.ic.2011.01.006",\npages = "748-763",\nurl_Paper = "https://lance.fortnow.com/papers/files/equiv.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws.\n \n \n \n \n\n\n \n Fortnow, L.; Hitchcock, J.; Pavan, A.; Vinodchandran, N.; and Wang, F.\n\n\n \n\n\n\n Information and Computation, 209(4): 627-636. April 2011.\n \n\n\n\n
\n\n\n\n \n \n $\"Extracting$ Paper\n \n \n \n $\"Extracting$ 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

@article{kex-J,\nshow = 1,\nauthor = "L. Fortnow and J. Hitchcock and\nA. Pavan and N.V. Vinodchandran and F. Wang",\ntitle = "Extracting Kolmogorov Complexity with Applications to Dimension\nZero-One Laws",\njournal = iandcomp,\nvolume = 209,\nnumber = 4,\nmonth = apr,\nyear = 2011,\npages = "627-636",\nissn = "0890-5401",\ndoi = "10.1016/j.ic.2010.09.006",\nurl = "https://dx.doi.org/10.1016/j.ic.2010.09.006",\nurl_Paper = "https://lance.fortnow.com/papers/files/kex.pdf"\n}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Repeated Matching Pennies with Limited Randomness.\n \n \n \n \n\n\n \n Fortnow, L.; and Budinich, M.\n\n\n \n\n\n\n In Proceedings of the 12th ACM Conference on Electronic Commerce, pages 111-118. ACM, New York, 2011.\n \n\n\n\n
\n\n\n\n \n \n $\"Repeated$ Paper\n \n \n \n $\"Repeated$ 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

@incollection{mprand-C,\nshow = 1,\nauthor = "L. Fortnow and M. Budinich",\ntitle = "Repeated Matching Pennies with Limited Randomness",\nyear = 2011,\npublisher = "ACM",\naddress = "New York",\nbooktitle = ec12,\nurl = "https://dl.acm.org/authorize?N09528",\ndoi = "10.1145/1993574.1993592",\npages = "111-118",\nurl_Paper = "https://lance.fortnow.com/papers/files/mprand.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Infeasibility of Instance Compression and Succinct PCPs for NP.\n \n \n \n \n\n\n \n Fortnow, L.; and Santhanam, R.\n\n\n \n\n\n\n Journal of Computer and System Sciences, 77(1): 91-106. January 2011.\n Co-winner of the 2014 EATCS-IPEC Nerode Prize. JCSS Special issue celebrating Karp's Kyoto Prize.\n\n\n\n
\n\n\n\n \n \n $\"Infeasibility$ Paper\n \n \n \n $\"Infeasibility$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{compress-J,\nshow = 1,\nauthor = "L. Fortnow and R. Santhanam",\ntitle = "Infeasibility of Instance Compression and Succinct {PCP}s for {NP}",\njournal = jcss,\nurl = "https://dx.doi.org/10.1016/j.jcss.2010.06.007",\ndoi = "10.1016/j.jcss.2010.06.007",\nurl_Paper = "https://lance.fortnow.com/papers/files/compress.pdf",\nvolume = 77,\nnumber = 1,\nmonth = jan,\nyear = 2011,\npages = "91-106",\nnote = "Co-winner of the 2014 EATCS-IPEC Nerode Prize. JCSS Special issue celebrating Karp's Kyoto Prize."}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2010\n \n \n (5)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Gaming Prediction Markets: Equilibrium Strategies with a Market Maker.\n \n \n \n \n\n\n \n Chen, Y.; Dimitrov, S.; Sami, R.; Reeves, D.; Pennock, D.; Hanson, R.; Fortnow, L.; and Gonen, R.\n\n\n \n\n\n\n Algorithmica, 58(4): 930-969. December 2010.\n \n\n\n\n
\n\n\n\n \n \n $\"Gaming$ Paper\n \n \n \n $\"Gaming$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{bluffing-J,\nshow = 1,\nauthor = "Y. Chen and S. Dimitrov and R. Sami and D. Reeves\nand D. Pennock and\nR. Hanson and L. Fortnow and R. Gonen",\ntitle = "Gaming Prediction Markets:\n{Equilibrium} Strategies with a Market Maker",\njournal = "Algorithmica",\nvolume = 58,\nnumber =4,\npages = "930-969",\nmonth = dec,\nyear = 2010,\nurl = "https://dx.doi.org/10.1007/s00453-009-9323-2",\ndoi = "10.1007/s00453-009-9323-2",\nurl_Paper = "https://lance.fortnow.com/papers/files/bluffing.pdf"}\n\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Derandomizing from Random Strings.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; Koucký, M.; and Loff, B.\n\n\n \n\n\n\n In Proceedings of the 25th IEEE Conference on Computational Complexity, pages 58-63. IEEE, 2010.\n \n\n\n\n
\n\n\n\n \n \n $\"Derandomizing$ Paper\n \n \n \n $\"Derandomizing$ 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 9 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{bppr-C,\nshow = 1,\nauthor = "H. Buhrman and L. Fortnow and M. Kouck\\'y and B. Loff",\ntitle = "Derandomizing from Random Strings",\nyear = 2010,\nurl = "https://dx.doi.org/10.1109/CCC.2010.15",\ndoi = "10.1109/CCC.2010.15",\npublisher = "IEEE",\nbooktitle = sict25,\nurl_Paper = "https://lance.fortnow.com/papers/files/bppr.pdf",\npages = "58-63"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; Koucký, M.; Rogers, J.; and Vereshchagin, N.\n\n\n \n\n\n\n Theory of Computing Systems, 46(1): 143-156. January 2010.\n \n\n\n\n
\n\n\n\n \n \n $\"Does$ paper\n \n \n \n $\"Does$ 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 10 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{phq-J,\nshow = 1,\nauthor = "H. Buhrman and L. Fortnow and M. Kouck\\'{y} and J. Rogers\nand N. Vereshchagin",\ntitle = "Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?",\nurl_Paper = "https://lance.fortnow.com/papers/files/phq.pdf",\njournal = tocs,\nurl = "https://dx.doi.org/10.1007/s00224-008-9160-8",\ndoi = "10.1007/s00224-008-9160-8",\nvolume = 46,\nnumber = 1,\nmonth = jan,\nyear = 2010,\npages = "143-156"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Bounding Rationality by Discounting Time.\n \n \n \n \n\n\n \n Fortnow, L.; and Santhanam, R.\n\n\n \n\n\n\n In Proceedings of The First Symposium on Innovations in Computer Science, pages 143-156. Tsinghua University Press, Beijing, 2010.\n \n\n\n\n
\n\n\n\n \n \n $\"Bounding$ paper\n \n \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

@incollection{factor-C,\nshow = 1,\nauthor = "L. Fortnow and R. Santhanam",\ntitle = "Bounding Rationality by Discounting Time",\nyear = 2010,\npublisher = tsinghua,\naddress = "Beijing",\nbooktitle = ics1,\npages = "143-156",\nurl_Paper = "https://lance.fortnow.com/papers/files/factor.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n The enduring legacy of the Turing machine.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Ubiquity, 2010. December 2010.\n Ubiquity Symposium on 'What is Computation?'\n\n\n\n
\n\n\n\n \n \n $\"The$ Paper\n \n \n \n $\"The$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{compute-O,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "The enduring legacy of the {T}uring machine",\njournal = "Ubiquity",\nvolume = 2010,\nmonth = dec,\nyear = 2010,\nissue = "December",\nnote = "Ubiquity Symposium on 'What is Computation?'",\nurl = "https://dl.acm.org/authorize?149889",\ndoi = "10.1145/1895419.1921573",\npublisher = "ACM",\nurl_Paper = "https://lance.fortnow.com/papers/files/compute.pdf"}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2009\n \n \n (11)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n A Simple Proof of Toda's Theorem.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Theory of Computing, 5(7): 135-140. 2009.\n \n\n\n\n
\n\n\n\n \n \n $\"A$ Paper\n \n \n \n $\"A$ 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 12 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{toda-o,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "A Simple Proof of {Toda}'s Theorem",\njournal = toc,\nvolume = 5,\nyear = 2009,\nnumber = 7,\npages = "135-140",\nurl = "https://dx.doi.org/10.4086/toc.2009.v005a007",\ndoi = "10.4086/toc.2009.v005a007",\nurl_Paper = "https://lance.fortnow.com/papers/files/toda.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Time for Computer Science to Grow Up.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Communications of the ACM, 52(8): 33-35. August 2009.\n Viewpoint Column\n\n\n\n
\n\n\n\n \n \n $\"Time$ paper\n \n \n \n $\"Time$ 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 7 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{growup-O,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "Time for Computer Science to Grow Up",\nvolume = 52,\nnumber = 8,\njournal = cacm,\nyear = 2009,\nmonth = aug,\npages = "33-35",\nnote = "Viewpoint Column",\nurl_Paper = "https://lance.fortnow.com/papers/files/growup.pdf",\ndoi = "10.1145/1536616.1536631",\nurl = "https://dl.acm.org/authorize?985319"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n The Status of the P versus NP problem.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Communications of the ACM, 52(9): 78-86. September 2009.\n Review Article\n\n\n\n
\n\n\n\n \n \n $\"The$ paper\n \n \n \n $\"The$ 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 16 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{pnp-cacm-O,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "The Status of the {P} versus {NP} problem",\nvolume = 52,\nnumber = 9,\njournal = cacm,\nyear = 2009,\nmonth = sep,\nnote = "Review Article",\npages = "78-86",\nurl_Paper = "https://lance.fortnow.com/papers/files/pnp-cacm.pdf",\ndoi = "10.1145/1562164.1562186",\nurl = "https://dl.acm.org/authorize?700314"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Program Equilibria and Discounted Computation Time.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge, pages 128-133. ACM, 2009.\n \n\n\n\n
\n\n\n\n \n \n $\"Program$ paper\n \n \n \n $\"Program$ 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

@incollection{discount-C,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "Program Equilibria and Discounted Computation Time",\nyear = 2009,\nbooktitle = tark12,\npublisher = "ACM",\nurl_Paper = "https://lance.fortnow.com/papers/files/discount.pdf",\nurl = "https://dl.acm.org/authorize?171102",\ndoi = "10.1145/1562814.1562833",\npages = "128-133"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Unconditional Lower Bounds Against Advice.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; and Santhanam, R.\n\n\n \n\n\n\n In Proceedings of the 36th International Colloquium on Automata, Languages and Programming, volume 5555, pages 195-209. Springer, 2009.\n \n\n\n\n
\n\n\n\n \n \n $\"Unconditional$ paper\n \n \n \n $\"Unconditional$ 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

@incollection{advice-C,\nshow = 1,\ntitle = "Unconditional Lower Bounds Against Advice",\nauthor = "H. Buhrman and L. Fortnow and R. Santhanam",\nbooktitle = icalp36,\npublisher = "Springer",\nyear = 2009,\nurl_Paper = "https://lance.fortnow.com/papers/files/advice.pdf",\nurl = "https://dx.doi.org/10.1007/978-3-642-02927-1_18",\ndoi = "10.1007/978-3-642-02927-1_18",\nvolume = 5555,\npages = "195-209"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Efficient Learning Algorithms Yield Circuit Lower Bounds.\n \n \n \n \n\n\n \n Fortnow, L.; and Klivans, A.\n\n\n \n\n\n\n Journal of Computer and System Sciences, 75: 27-36. January 2009.\n Special issue for selected papers from the 19th Annual Conference on Computational Learning Theory.\n\n\n\n
\n\n\n\n \n \n $\"Efficient$ Paper\n \n \n \n $\"Efficient$ 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 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{learnbound-J,\nshow = 1,\ntitle = "Efficient Learning Algorithms Yield Circuit Lower Bounds",\nauthor = "L. Fortnow and A. Klivans",\njournal = jcss,\nvolume = 75,\nissue = 1,\nmonth = jan,\nyear = 2009,\npages = "27-36",\nurl = "https://dx.doi.org/10.1016/j.jcss.2008.07.006",\ndoi = "10.1016/j.jcss.2008.07.006",\nnote = "Special issue for selected papers from the 19th\nAnnual Conference on Computational Learning Theory.",\nurl_Paper = "https://lance.fortnow.com/papers/files/fksub.pdf"}\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 Theory of Computing Systems, 45(1): 150-161. June 2009.\n \n\n\n\n
\n\n\n\n \n \n $\"Sophistication$ paper\n \n \n \n $\"Sophistication$ 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

@article{soph-J,\nshow = 1,\nauthor = "L. Antunes and L. Fortnow",\ntitle = "Sophistication Revisited",\nyear = 2009,\nvolume = 45,\nnumber =1,\nmonth = jun,\nurl_Paper = "https://lance.fortnow.com/papers/files/soph.pdf",\nurl = "https://dx.doi.org/10.1007/s00224-007-9095-5",\ndoi = "10.1007/s00224-007-9095-5",\npages = "150-161",\njournal = tocs}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Worst-Case Running Times for Average-Case Algorithms.\n \n \n \n \n\n\n \n Antunes, L.; and Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 24th IEEE Conference on Computational Complexity, pages 298-303. IEEE, 2009.\n \n\n\n\n
\n\n\n\n \n \n $\"Worst-Case$ Paper\n \n \n \n $\"Worst-Case$ 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 10 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{ud-C,\nshow = 1,\nauthor = "L. Antunes and L. Fortnow",\ntitle = "Worst-Case Running Times for Average-Case Algorithms",\nyear = 2009,\npublisher = "IEEE",\nurl = "https://dx.doi.org/10.1109/CCC.2009.12",\ndoi = "10.1109/CCC.2009.12",\nbooktitle = sict24,\nurl_Paper = "https://lance.fortnow.com/papers/files/ud.pdf",\npages = "298-303"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n The Complexity of Forecast Testing.\n \n \n \n \n\n\n \n Fortnow, L.; and Vohra, R.\n\n\n \n\n\n\n Econometrica, 77(1): 93-105. 2009.\n \n\n\n\n
\n\n\n\n \n \n $\"The$ Paper\n \n \n \n $\"The$ 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 8 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{forecast-J,\nshow = 1,\nauthor = "L. Fortnow and R. Vohra",\ntitle = "The Complexity of Forecast Testing",\nyear = 2009,\njournal = "Econometrica",\nurl = "https://dx.doi.org/10.3982/ECTA7163",\ndoi = "10.3982/ECTA7163",\nvolume = 77,\nnumber = 1,\npages = "93-105",\nurl_Paper = "https://lance.fortnow.com/papers/files/forecast.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n A Computational Theory of Awareness and Decision Making.\n \n \n \n \n\n\n \n Devanur, N.; and Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge, pages 99-107. ACM, 2009.\n \n\n\n\n
\n\n\n\n \n \n $\"A$ paper\n \n \n \n $\"A$ 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

@incollection{aware-C,\nshow = 1,\nauthor = "N. Devanur and L. Fortnow",\ntitle = "A Computational Theory of Awareness and Decision Making",\nyear = 2009,\npublisher = "ACM",\nbooktitle = tark12,\nurl_Paper = "https://lance.fortnow.com/papers/files/awareness.pdf",\nurl = "https://dl.acm.org/authorize?171109",\ndoi = "10.1145/1562814.1562830",\npages = "99-107"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Fixed-Polynomial Size Circuit Bounds.\n \n \n \n \n\n\n \n Fortnow, L.; Santhanam, R.; and Williams, R.\n\n\n \n\n\n\n In Proceedings of the 24th IEEE Conference on Computational Complexity, pages 19-26. IEEE, 2009.\n \n\n\n\n
\n\n\n\n \n \n $\"Fixed-Polynomial$ Paper\n \n \n \n $\"Fixed-Polynomial$ 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 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{linear-C,\nshow = 1,\nauthor = "L. Fortnow and R. Santhanam and R. Williams",\ntitle = "Fixed-Polynomial Size Circuit Bounds",\nyear = 2009,\npublisher = "IEEE",\nbooktitle = sict24,\nurl = "https://dx.doi.org/10.1109/CCC.2009.21",\ndoi = "10.1109/CCC.2009.21",\nurl_Paper = "https://lance.fortnow.com/papers/files/linearcircuit.pdf",\npages = "19-26"}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2008\n \n \n (4)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n On the complexity of succinct zero-sum games.\n \n \n \n \n\n\n \n Fortnow, L.; Impagliazzo, R.; Kabanets, V.; and Umans, C.\n\n\n \n\n\n\n Computational Complexity, 17(3): 353-376. October 2008.\n \n\n\n\n
\n\n\n\n \n \n $\"On$ Paper\n \n \n \n $\"On$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{succinct-J,\nshow = 1,\nauthor = "L. Fortnow and R. Impagliazzo and\nV. Kabanets and C. Umans",\ntitle = "On the complexity of succinct zero-sum games",\nurl = "https://dx.doi.org/10.1007/s00037-008-0252-2",\ndoi = "10.1007/s00037-008-0252-2",\njournal = compcomp,\nvolume = 17,\nnumber = 3,\nmonth = oct,\nyear = 2008,\npages = "353-376",\nurl_Paper = "https://lance.fortnow.com/papers/files/succinct.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Complexity of Combinatorial Market Makers.\n \n \n \n \n\n\n \n Chen, Y.; Fortnow, L.; Lambert, N.; Pennock, D.; and Wortman, J.\n\n\n \n\n\n\n In Proceedings of the 9th ACM Conference on Electronic Commerce, pages 190-199. ACM, New York, 2008.\n \n\n\n\n
\n\n\n\n \n \n $\"Complexity$ Paper\n \n \n \n $\"Complexity$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{lmsr-C,\nshow = 1,\nauthor = "Y. Chen and L. Fortnow and N. Lambert and D. Pennock and J. Wortman",\ntitle = "Complexity of Combinatorial Market Makers",\nyear = 2008,\npublisher = "ACM",\naddress = "New York",\nbooktitle = ec9,\npages = "190-199",\nurl = "https://dl.acm.org/authorize?074392",\ndoi = "10.1145/1386790.1386822",\nurl_Paper = "https://lance.fortnow.com/papers/files/LMSR.pdf"}\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 SIAM Journal on Computing, 37(5): 1387-1400. 2008.\n \n\n\n\n
\n\n\n\n \n \n $\"Quantum$ paper\n \n \n \n $\"Quantum$ 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

@article{qprop-J,\nshow = 1,\ntitle = "Quantum Property Testing",\nauthor = "H. Buhrman and L. Fortnow and I. Newman and H. R{\\"{o}}hrig",\njournal = sicomp,\nvolume = 37,\nnumber = 5,\nyear = 2008,\npages = "1387-1400",\nurl_Paper = "https://lance.fortnow.com/papers/files/qprop.pdf",\nurl = "dx.doi.org/10.1137/S0097539704442416",\ndoi = "10.1137/S0097539704442416"}\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 Journal of Computer and System Sciences, 74(3): 358-363. May 2008.\n Special issue for selected papers from the 18th IEEE Conference on Computational Complexity\n\n\n\n
\n\n\n\n \n \n $\"Proving$ Paper\n \n \n \n $\"Proving$ 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

@article{satcirc-J,\nshow = 1,\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",\njournal = jcss,\nyear = 2008,\nmonth = may,\nvolume = 74,\nnumber = 3,\npages = "358-363",\nurl = "https://dx.doi.org/10.1016/j.jcss.2007.06.017",\ndoi = "10.1016/j.jcss.2007.06.017",\nnote = "Special issue for selected papers from the 18th IEEE\nConference on Computational Complexity",\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 2007\n \n \n (3)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Combinatorial Betting.\n \n \n \n \n\n\n \n Chen, Y.; Fortnow, L.; Nikolova, E.; and Pennock, D.\n\n\n \n\n\n\n SIGecom Exchanges, 7(1). December 2007.\n Survey.\n\n\n\n
\n\n\n\n \n \n $\"Combinatorial$ Paper\n \n \n \n $\"Combinatorial$ 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

@article{combbet-O,\nshow = 1,\nauthor = "Y. Chen and L. Fortnow and E. Nikolova and D. Pennock",\ntitle = "Combinatorial Betting",\njournal = sigecom,\nnote = {Survey.},\nvolume = 7,\nnumber = 1,\nyear = 2007,\nmonth = dec,\nurl = "https://dl.acm.org/authorize?056592",\ndoi = "10.1145/1345037.1345053",\nurl_Paper = "https://lance.fortnow.com/papers/files/combbet.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Low-Depth Witnesses are Easy to Find.\n \n \n \n \n\n\n \n Antunes, L.; Fortnow, L.; Pinto, A.; and Souto, A.\n\n\n \n\n\n\n In Proceedings of the 22nd IEEE Conference on Computational Complexity, pages 46-51. IEEE, New York, 2007.\n \n\n\n\n
\n\n\n\n \n \n $\"Low-Depth$ Paper\n \n \n \n $\"Low-Depth$ 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

@incollection{witness-C,\nshow = 1,\nauthor = "L. Antunes and L. Fortnow and A. Pinto and A. Souto",\ntitle = "Low-Depth Witnesses are Easy to Find",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict22,\nyear = 2007,\npages = "46-51",\nurl = "https://dx.doi.org/10.1109/CCC.2007.13",\ndoi = "10.1109/CCC.2007.13",\nurl_Paper = "https://lance.fortnow.com/papers/files/witness.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Betting on Permutations.\n \n \n \n \n\n\n \n Chen, Y.; Fortnow, L.; Nikolova, E.; and Pennock, D.\n\n\n \n\n\n\n In Proceedings of the 8th ACM Conference on Electronic Commerce, pages 326-335. ACM, New York, 2007.\n \n\n\n\n
\n\n\n\n \n \n $\"Betting$ Paper\n \n \n \n $\"Betting$ 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

@incollection{pairbetting-C,\nshow = 1,\nauthor = "Y. Chen and L. Fortnow and E. Nikolova and D. Pennock",\ntitle = "Betting on Permutations",\nyear = 2007,\npublisher = "ACM",\naddress = "New York",\nbooktitle = ec8,\nurl = "https://dl.acm.org/authorize?974888",\ndoi = "10.1145/1250910.1250957",\nurl_Paper = "https://lance.fortnow.com/papers/files/pairbetting.pdf",\npages = "326-335"}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2006\n \n \n (9)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Very Sparse Leaf Languages.\n \n \n \n \n\n\n \n Fortnow, L.; and Ogihara, M.\n\n\n \n\n\n\n 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.\n \n\n\n\n
\n\n\n\n \n \n $\"Very$ Paper\n \n \n \n $\"Very$ 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

@incollection{vsll-C,\nshow = 1,\nauthor = "L. Fortnow and M. Ogihara",\ntitle = "Very Sparse Leaf Languages",\nbooktitle = mfcs31,\nyear = 2006,\naddress = "Berlin",\nseries = lncs,\npublisher = springer,\nvolume = 4162,\npages = "375-386",\nurl = "https://dx.doi.org/10.1007/11821069_33",\ndoi = "10.1007/11821069_33",\nurl_Paper = "https://lance.fortnow.com/papers/files/vsll.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Tolerant Versus Intolerant Testing for Boolean Properties.\n \n \n \n \n\n\n \n Fischer, E.; and Fortnow, L.\n\n\n \n\n\n\n Theory of Computing, 2(9): 173-183. 2006.\n \n\n\n\n
\n\n\n\n \n \n $\"Tolerant$ Paper\n \n \n \n $\"Tolerant$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{tolerant-J,\nshow = 1,\nauthor = "E. Fischer and L. Fortnow",\ntitle = "Tolerant Versus Intolerant Testing for {Boolean} Properties",\njournal = toc,\nvolume = 2,\nnumber = 9,\nyear = 2006,\npages = "173-183",\nurl = "https://dx.doi.org/10.4086/toc.2006.v002a009",\ndoi = "10.4086/toc.2006.v002a009",\nurl_Paper = "https://lance.fortnow.com/papers/files/ttg.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Enumerations of the Kolmogorov Function.\n \n \n \n \n\n\n \n Beigel, R.; Buhrman, H.; Fejer, P.; Fortnow, L.; Grabowski, P.; Longpré, L.; Muchnik, A.; Stephan, F.; and Torenvliet, L.\n\n\n \n\n\n\n Journal of Symbolic Logic, 71(2): 501-528. June 2006.\n \n\n\n\n
\n\n\n\n \n \n $\"Enumerations$ Paper\n \n \n \n $\"Enumerations$ 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

@article{enumerations-J,\nshow = 1,\ntitle = "Enumerations of the {Kolmogorov} Function",\nauthor = "R. Beigel and H. Buhrman and P. Fejer and L. Fortnow and\nP. Grabowski and\nL. Longpr\\'e and\nA. Muchnik and\nF. Stephan and L. Torenvliet",\nyear = 2006,\njournal = jsl,\nvolume = 71,\nnumber = 2,\nmonth = jun,\npages = "501-528",\nurl = "https://dx.doi.org/10.2178/jsl/1146620156",\ndoi = "10.2178/jsl/1146620156",\nurl_Paper = "https://lance.fortnow.com/papers/files/enumerations.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 SIAM Journal on Computing, 6(3): 595-608. 2006.\n \n\n\n\n
\n\n\n\n \n \n $\"Infinitely-often$ Paper\n \n \n \n $\"Infinitely-often$ 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

@article{ioauto-J,\nshow = 1,\ntitle = "Infinitely-often Autoreducible Sets",\nauthor = "R. Beigel and L. Fortnow and F. Stephan",\njournal = sicomp,\nyear = 2006,\nvolume = 6,\nnumber = 3,\npages = "595-608",\nurl = "https://dx.doi.org/10.1137/S0097539704441630",\ndoi = "10.1137/S0097539704441630",\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 Kolmogorov Complexity with Error.\n \n \n \n \n\n\n \n Fortnow, L.; Lee, T.; and Vereshchagin, N.\n\n\n \n\n\n\n In Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science, of Lecture Notes in Computer Science, pages 137-148. Springer, Berlin, 2006.\n \n\n\n\n
\n\n\n\n \n \n $\"Kolmogorov$ Paper\n \n \n \n $\"Kolmogorov$ 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 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{error-C,\nshow = 1,\ntitle = "Kolmogorov Complexity with Error",\nauthor = "L. Fortnow and T. Lee and N. Vereshchagin",\nbooktitle = stacs23,\nyear = 2006,\naddress = "Berlin",\npublisher = springer,\nseries = lncs,\npages = "137-148",\nnumber = 3884,\nurl = "https://dx.doi.org/10.1007/11672142_10",\ndoi = "10.1007/11672142_10",\nurl_Paper = "https://lance.fortnow.com/papers/files/error.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Linear Advice for Randomized Logarithmic Space.\n \n \n \n \n\n\n \n Fortnow, L.; and Klivans, A.\n\n\n \n\n\n\n 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.\n \n\n\n\n
\n\n\n\n \n \n $\"Linear$ Paper\n \n \n \n $\"Linear$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{rll-C,\nshow = 1,\ntitle = "Linear Advice for Randomized Logarithmic Space",\nauthor = "L. Fortnow and A. Klivans",\nbooktitle = stacs23,\nyear = 2006,\naddress = "Berlin",\npublisher = springer,\nseries = lncs,\nvolume = 3884,\npages = "469-476",\nurl = "https://dx.doi.org/10.1007/11672142_38",\ndoi = "10.1007/11672142_38",\nurl_Paper = "https://lance.fortnow.com/papers/files/rll.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Computational depth: Concept and applications.\n \n \n \n \n\n\n \n Antunes, L.; Fortnow, L.; van Melkebeek, D.; and Vinodchandran, N.\n\n\n \n\n\n\n Theoretical Computer Science, 354(3): 391-404. April 2006.\n Special issue of selected papers from Foundations of Computation Theory (FCT 2003)\n\n\n\n
\n\n\n\n \n \n $\"Computational$ Paper\n \n \n \n $\"Computational$ 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

@article{depth-J,\nshow = 1,\nauthor = "L. Antunes and L. Fortnow and D. van Melkebeek and N. Vinodchandran",\ntitle = "Computational depth: {Concept} and applications",\njournal = tcs,\nurl = "https://dx.doi.org/10.1016/j.tcs.2005.11.033",\ndoi = "10.1016/j.tcs.2005.11.033",\nvolume = 354,\nnumber = 3,\nmonth = apr,\nyear = 2006,\npages = "391-404",\nurl_Paper = "https://lance.fortnow.com/papers/files/depth-j.pdf",\nnote = "Special issue of selected papers from\nFoundations of Computation Theory (FCT 2003)"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Recent Work on Hierarchies for Semantic Classes.\n \n \n \n \n\n\n \n Fortnow, L.; and Santhanam, R.\n\n\n \n\n\n\n SIGACT News, 37(3): 36-54. September 2006.\n \n\n\n\n
\n\n\n\n \n \n $\"Recent$ Paper\n \n \n \n $\"Recent$ 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

@article{hier-O,\nshow = 1,\nauthor = "L. Fortnow and R. Santhanam",\ntitle = "Recent Work on Hierarchies for Semantic Classes",\njournal = sigact,\nvolume = 37,\nnumber = 3,\nmonth = sep,\nyear = 2006,\npages = "36-54",\nurl = "https://doi.acm.org/10.1145/1165555.1165565",\ndoi = "10.1145/1165555.1165565",\nurl_Paper = "https://lance.fortnow.com/papers/files/HierSurvey.pdf"}\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n A Tight Lower Bound for Restricted PIR Protocols.\n \n \n \n \n\n\n \n Beigel, R.; Fortnow, L.; and Gasarch, W.\n\n\n \n\n\n\n Computational Complexity, 15(1): 82-91. May 2006.\n \n\n\n\n
\n\n\n\n \n \n $\"A$ Paper\n \n \n \n $\"A$ 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

@article{pir-J,\nshow = 1,\ntitle = "A Tight Lower Bound for Restricted {PIR} Protocols",\nauthor = "R. Beigel and L. Fortnow and W. Gasarch",\njournal = compcomp,\nurl = "https://dx.doi.org/10.1007/s00037-006-0208-3",\ndoi = "10.1007/s00037-006-0208-3",\nyear = 2006,\nurl_Paper = "https://lance.fortnow.com/papers/files/pir.pdf",\nvolume = 15,\nnumber = 1,\nmonth = may,\npages = "82-91"}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2005\n \n \n (10)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n NP with Small Advice.\n \n \n \n \n\n\n \n Fortnow, L.; and Klivans, A.\n\n\n \n\n\n\n In Proceedings of the 20th IEEE Conference on Computational Complexity, pages 228-234. IEEE, New York, 2005.\n \n\n\n\n
\n\n\n\n \n \n $\"NP$ Paper\n \n \n \n $\"NP$ 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 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{npsmall-C,\nshow = 1,\nauthor = "L. Fortnow and A. Klivans",\ntitle = "{NP} with Small Advice",\nyear = 2005,\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict20,\nurl = "https://dx.doi.org/10.1109/CCC.2005.15",\ndoi = "10.1109/CCC.2005.15",\npages = "228-234",\nurl_Paper = "https://lance.fortnow.com/papers/files/fk.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Hierarchies for Semantic Classes.\n \n \n \n \n\n\n \n Fortnow, L.; Santhanam, R.; and Trevisan, L.\n\n\n \n\n\n\n In Proceedings of the 37th ACM Symposium on the Theory of Computing, pages 348-355. ACM, New York, 2005.\n \n\n\n\n
\n\n\n\n \n \n $\"Hierarchies$ Paper\n \n \n \n $\"Hierarchies$ 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

@incollection{promise-C,\nshow = 1,\nauthor = "L. Fortnow and R. Santhanam and L. Trevisan",\ntitle = "Hierarchies for Semantic Classes",\nurl = "https://dl.acm.org/authorize?862702",\nyear = 2005,\npublisher = "ACM",\naddress = "New York",\nbooktitle = stoc37,\npages = "348-355",\ndoi = "10.1145/1060590.1060642",\nurl_Paper = "https://lance.fortnow.com/papers/files/promise.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Beyond NP: The Work and Legacy of Larry Stockmeyer.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 37th ACM Symposium on the Theory of Computing, pages 120-127. ACM, New York, 2005.\n Keynote address.\n\n\n\n
\n\n\n\n \n \n $\"Beyond$ Paper\n \n \n \n $\"Beyond$ 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

@incollection{beyondnp,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "Beyond {NP}: {T}he Work and Legacy of {Larry Stockmeyer}",\nurl = "https://dl.acm.org/authorize?862786",\ndoi = "10.1145/1060590.1060609",\nyear = 2005,\npublisher = "ACM",\naddress = "New York",\nbooktitle = stoc37,\npages = "120-127",\nurl_Paper = "https://lance.fortnow.com/papers/files/beyondnp.pdf",\nnote = "Keynote address."}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Increasing Kolmogorov Complexity.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; Newman, I.; and Vereshchagin, N.\n\n\n \n\n\n\n In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science, of Lecture Notes in Computer Science, pages 412-421. Springer, Berlin, 2005.\n \n\n\n\n
\n\n\n\n \n \n $\"Increasing$ Paper\n \n \n \n $\"Increasing$ 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

@incollection{flipping-C,\nshow = 1,\ntitle = "Increasing {K}olmogorov Complexity",\nauthor = "H. Buhrman and L. Fortnow and I. Newman and N. Vereshchagin",\nbooktitle = stacs22,\nyear = 2005,\naddress = "Berlin",\npublisher = springer,\nseries = lncs,\nnumber = 3404,\nurl = "https://dx.doi.org/10.1007/b106485",\ndoi = "10.1007/b106485",\nurl_Paper = "https://lance.fortnow.com/papers/files/flipping.pdf",\npages = "412-421"\n}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.\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 SIAM Journal on Computing, 35(1): 91-109. 2005.\n \n\n\n\n
\n\n\n\n \n \n $\"Approximating$ Paper\n \n \n \n $\"Approximating$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{emst-J,\nshow = 1,\ntitle = "Approximating the Weight of the Euclidean Minimum\nSpanning Tree in Sublinear Time",\nauthor = "Artur Czumaj and Funda Erg{\\"{u}}n and Lance Fortnow and\nAvner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler",\nurl = "https://dx.doi.org/10.1137/S0097539703435297",\ndoi = "10.1137/S0097539703435297",\njournal = sicomp,\nyear = 2005,\nvolume = 35,\nnumber = 1,\npages = "91-109",\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 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 Theory of Computing Systems, 38(2): 211-227. February 2005.\n Special issue on the 20th Symposium on Theoretical Aspects of Computer Science\n\n\n\n
\n\n\n\n \n \n $\"Some$ Paper\n \n \n \n $\"Some$ 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 8 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{BF-derand-J,\nshow = 1,\ntitle = "Some Results on Derandomization",\nauthor = "H. Buhrman and L. Fortnow and A. Pavan",\njournal = tocs,\nvolume = 38,\nnumber = 2,\nmonth = feb,\nyear = 2005,\npages = "211-227",\nurl = "https://dx.doi.org/10.1007/s00224-004-1194-y",\ndoi = "10.1007/s00224-004-1194-y",\nnote = "Special issue on the 20th Symposium on\nTheoretical Aspects of Computer Science",\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 Prediction and Dimension.\n \n \n \n \n\n\n \n Fortnow, L.; and Lutz, J.\n\n\n \n\n\n\n Journal of Computer and System Sciences, 70(4): 570-589. June 2005.\n Special issue for selected papers from the 15th Annual Conference on Computational Learning Theory.\n\n\n\n
\n\n\n\n \n \n $\"Prediction$ Paper\n \n \n \n $\"Prediction$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{predict-J,\nshow = 1,\ntitle = "Prediction and Dimension",\nauthor = "L. Fortnow and J. Lutz",\nurl = "https://dx.doi.org/10.1016/j.jcss.2004.10.007",\ndoi = "10.1016/j.jcss.2004.10.007",\nurl_Paper = "https://lance.fortnow.com/papers/files/predict.pdf",\njournal = jcss,\nvolume = 70,\nnumber = 4,\nmonth = jun,\nyear = 2005,\npages = "570-589",\nnote = "Special issue for selected papers from the 15th\nAnnual Conference on Computational Learning Theory."}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Time-space lower bounds for satisfiability.\n \n \n \n \n\n\n \n Fortnow, L.; Lipton, R.; van Melkebeek, D.; and Viglas, A.\n\n\n \n\n\n\n Journal of the ACM, 52(6): 835-865. November 2005.\n \n\n\n\n
\n\n\n\n \n \n $\"Time-space$ Paper\n \n \n \n $\"Time-space$ 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

@article{tst-J,\nshow = 1,\nauthor = "L. Fortnow and R. Lipton and D. van Melkebeek and A. Viglas",\ntitle = "Time-space lower bounds for satisfiability",\nurl = "https://dl.acm.org/authorize?886005",\ndoi = "10.1145/1101821.1101822",\njournal = jacm,\nyear = 2005,\nmonth = nov,\nvolume = 52,\nnumber = 6,\npages = "835-865",\nurl_Paper = "https://lance.fortnow.com/papers/files/tst.pdf"}\n\n\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Computation in a Distributed Information Market.\n \n \n \n \n\n\n \n Feigenbaum, J.; Fortnow, L.; Pennock, D.; and Sami, R.\n\n\n \n\n\n\n Theoretical Computer Science, 343(1-2): 114-132. October 2005.\n Special issue on Game Theory Meets Theoretical Computer Science.\n\n\n\n
\n\n\n\n \n \n $\"Computation$ Paper\n \n \n \n $\"Computation$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{infomarkets-J,\nshow = 1,\ntitle = "Computation in a Distributed Information Market",\nauthor = "J. Feigenbaum and L. Fortnow and\nD. Pennock and R. Sami",\nurl = "https://dx.doi.org/10.1016/j.tcs.2005.05.010",\ndoi = "10.1016/j.tcs.2005.05.010",\njournal = tcs,\nnote = "Special issue on Game Theory Meets Theoretical\nComputer Science.",\nvolume = 343,\nnumber = "1-2",\npages = "114-132",\nyear = 2005,\nmonth = oct,\nurl_Paper = "https://lance.fortnow.com/papers/files/infomarkets.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Betting Boolean-style: A Framework for Trading in Securities Based on Logical Formulas.\n \n \n \n \n\n\n \n Fortnow, L.; Kilian, J.; Pennock, D.; and Wellman, M.\n\n\n \n\n\n\n Decision Support Systems, 39(1): 87-104. 2005.\n Special Issue on the Fourth ACM Conference on Electronic Commerce.\n\n\n\n
\n\n\n\n \n \n $\"Betting$ Paper\n \n \n \n $\"Betting$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{logicalsecurities-J,\nshow = 1,\ntitle = "Betting {Boolean}-style: A Framework for Trading in\nSecurities Based on Logical Formulas",\nurl = "https://dx.doi.org/10.1016/j.dss.2004.08.010",\ndoi = "10.1016/j.dss.2004.08.010",\njournal = dss,\nauthor = "L. Fortnow and J. Kilian and D. Pennock and M. Wellman",\nyear = 2005,\nvolume = 39,\nnumber = 1,\npages = "87-104",\nnote = "Special Issue on the Fourth ACM Conference on Electronic Commerce.",\nurl_Paper = "https://lance.fortnow.com/papers/files/logicalsecurities.pdf"}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2004\n \n \n (2)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Hierarchy Theorems for Probabilistic Polynomial Time.\n \n \n \n \n\n\n \n Fortnow, L.; and Santhanam, R.\n\n\n \n\n\n\n In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pages 316-324. IEEE, New York, 2004.\n \n\n\n\n
\n\n\n\n \n \n $\"Hierarchy$ Paper\n \n \n \n $\"Hierarchy$ 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 7 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{probhier-C,\nshow = 1,\ntitle = "Hierarchy Theorems for Probabilistic Polynomial Time",\nauthor = "L. Fortnow and R. Santhanam",\nyear = 2004,\nurl = "https://dx.doi.org/10.1109/FOCS.2004.33",\ndoi = "10.1109/FOCS.2004.33",\nurl_Paper = "https://lance.fortnow.com/papers/files/probhier.pdf",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = focs45,\npages = "316-324"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Kolmogorov complexity and computational complexity.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n In Karjíček, J., editor(s), Complexity of Computations and Proofs, volume 13, of Quaderni di Matematica, pages 229-248. Dipartimento di Matematica della Seconda Universitá Napoli, 2004.\n \n\n\n\n
\n\n\n\n \n \n $\"Kolmogorov$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{quaderni,\nshow = 1,\nauthor = "L. Fortnow",\nbooktitle = "Complexity of Computations and Proofs",\nseries = quaderni,\nyear = 2004,\nvolume = 13,\neditor = "Jan Karj\\'{\\i}\\v{c}ek",\npublisher = "Dipartimento di Matematica della Seconda Universit\\'{a} Napoli",\npages = "229-248",\ntitle = "{Kolmogorov} complexity and computational complexity",\nurl_Paper = "https://lance.fortnow.com/papers/files/quaderni.pdf"}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2003\n \n \n (8)\n \n \n

\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 $\"One$ Paper\n \n \n \n $\"One$ 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 4 downloads\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 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 $\"Using$ 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

@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 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 $\"Are$ Paper\n \n \n \n $\"Are$ 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

@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 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 $\"One$ Paper\n \n \n \n $\"One$ 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

@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 Uniformly Hard Languages.\n \n \n \n \n\n\n \n Downey, R.; and Fortnow, L.\n\n\n \n\n\n\n Theoretical Computer Science, 298(2): 303-315. 2003.\n \n\n\n\n
\n\n\n\n \n \n $\"Uniformly$ Paper\n \n \n \n $\"Uniformly$ 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

@article{uniform-J,\nshow = 1,\nauthor = "R. Downey and L. Fortnow",\ntitle = "Uniformly Hard Languages",\nurl = "https://dx.doi.org/10.1016/S0304-3975(02)00810-1",\ndoi = "10.1016/S0304-3975(02)00810-1",\njournal = tcs,\nvolume = 298,\nnumber = 2,\nyear = 2003,\npages = "303-315",\nurl_paper = {https://lance.fortnow.com/papers/files/uniform.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n An Oracle Builder's Toolkit.\n \n \n \n \n\n\n \n Fenner, S.; Fortnow, L.; Kurtz, S.; and Li, L.\n\n\n \n\n\n\n Information and Computation, 182(2): 95-136. 2003.\n \n\n\n\n
\n\n\n\n \n \n $\"An$ Paper\n \n \n \n $\"An$ 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

@article{FFKL-J,\nshow = 1,\nauthor = "Fenner, S. and L. Fortnow and S. Kurtz and L. Li",\ntitle = "An Oracle Builder's Toolkit",\nurl = "https://dx.doi.org/10.1016/S0890-5401(03)00018-X",\ndoi = "10.1016/S0890-5401(03)00018-X",\nyear = 2003,\njournal = iandcomp,\nvolume = 182,\nnumber = 2,\npages = "95-136",\nurl_Paper = "https://lance.fortnow.com/papers/files/obt.pdf"}\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 $\"Inverting$ Paper\n \n \n \n $\"Inverting$ 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

@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 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 $\"A$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 4 downloads\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 2002\n \n \n (5)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Theory of Quantum Computing and Communication: A report from the NSF sponsored workshop held January 17-18, 2002 in Elmsford, New York.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Technical Report physics.quant-ph/0203074, arXiv.org e-Print archive, 2002.\n \n\n\n\n
\n\n\n\n \n \n $\"Theory$ Paper\n \n \n \n $\"Theory$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@techreport{ccr-quantum,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "Theory of\nQuantum Computing and Communication: A report from the {NSF} sponsored\nworkshop held {January} 17-18, 2002 in {Elmsford}, {New York}",\ninstitution = arxiv,\nyear = 2002,\nurl = "https://arxiv.org/abs/quant-ph/0203074",\nnumber = "physics.quant-ph/0203074",\nurl_Paper = "https://lance.fortnow.com/papers/files/ccr-quantum.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Membership comparable and p-selective sets.\n \n \n \n \n\n\n \n Beigel, R.; Fortnow, L.; and Pavan, A.\n\n\n \n\n\n\n Technical Report 2002-006N, NEC Research Institute, 2002.\n \n\n\n\n
\n\n\n\n \n \n $\"Membership$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@techreport{mc-U,\nshow = 1,\ntitle = "Membership comparable and {p}-selective sets",\nauthor = "R. Beigel and L. Fortnow and A. Pavan",\ninstitution = neci,\nyear = "2002",\nnumber = "2002-006N",\nurl_Paper = "https://lance.fortnow.com/papers/files/app-sel.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Computational Identification of Operons in Microbial Genomes.\n \n \n \n \n\n\n \n Zheng, Y.; Szustakowski, J.; Fortnow, L.; Roberts, R.; and Kasif, S.\n\n\n \n\n\n\n Genome Research, 12(8): 1221-1230. August 2002.\n \n\n\n\n
\n\n\n\n \n \n $\"Computational$ Paper\n \n \n \n $\"Computational$ 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

@article{operons-J,\nshow = 1,\nauthor = "Y. Zheng and J. Szustakowski and\nL. Fortnow and R. Roberts and S. Kasif",\ntitle = "Computational Identification of Operons in Microbial Genomes",\njournal = genome,\nvolume = 12,\nnumber = 8,\nmonth = aug,\nyear = 2002,\npages = "1221-1230",\nurl = "https://doi.org/10.1101/gr.200602",\ndoi = "10.1101/gr.200602",\nurl_Paper = "https://lance.fortnow.com/papers/files/operons.pdf"}\n\n\n\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Resource-Bounded Kolmogorov Complexity Revisited.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; and Laplante, S.\n\n\n \n\n\n\n SIAM Journal on Computing, 31(3): 887-905. 2002.\n \n\n\n\n
\n\n\n\n \n \n $\"Resource-Bounded$ Paper\n \n \n \n $\"Resource-Bounded$ 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

@article{cd-J,\nshow = 1,\nauthor = "H. Buhrman and L. Fortnow and S. Laplante",\ntitle = "Resource-Bounded {Kolmogorov} Complexity Revisited",\njournal = sicomp,\nurl = "https://dx.doi.org/10.1137/S009753979834388X",\ndoi = "10.1137/S009753979834388X",\nyear = 2002,\nvolume = 31,\nnumber = 3,\npages = "887-905",\nurl_Paper = "https://lance.fortnow.com/papers/files/cd.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Separability and One-Way Functions.\n \n \n \n \n\n\n \n Fortnow, L.; and Rogers, J.\n\n\n \n\n\n\n Computational Complexity, 11(3-4): 137-157. June 2002.\n \n\n\n\n
\n\n\n\n \n \n $\"Separability$ Paper\n \n \n \n $\"Separability$ 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

@article{FoRo-J,\nshow = 1,\nauthor = "L. Fortnow and J. Rogers",\ntitle = "Separability and One-Way Functions",\nyear = 2002,\njournal = compcomp,\nurl = "https://dx.doi.org/10.1007/s00037-002-0173-4",\ndoi = "10.1007/s00037-002-0173-4",\nvolume = 11,\nnumber = "3-4",\nmonth = jun,\npages = "137-157",\nurl_paper = {https://lance.fortnow.com/papers/files/sep.pdf}}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2001\n \n \n (8)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Distributionally Hard Languages.\n \n \n \n \n\n\n \n Fortnow, L.; Pavan, A.; and Selman, A.\n\n\n \n\n\n\n Theory of Computing Systems, 34(3): 245-262. 2001.\n \n\n\n\n
\n\n\n\n \n \n $\"Distributionally$ Paper\n \n \n \n $\"Distributionally$ 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 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{disthard-J,\nshow = 1,\nauthor = "L. Fortnow and A. Pavan and A. Selman",\ntitle = "Distributionally Hard Languages",\njournal = tocs,\nvolume = 34,\nnumber = 3,\nurl = "https://doi.org/10.1007/s00224-001-0003-0",\ndoi = "10.1007/s00224-001-0003-0",\npages = "245-262",\nyear = 2001,\nurl_Paper = "https://lance.fortnow.com/papers/files/disthard.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Computational Depth.\n \n \n \n \n\n\n \n Antunes, L.; Fortnow, L.; and van Melkebeek, D.\n\n\n \n\n\n\n In Proceedings of the 16th IEEE Conference on Computational Complexity, pages 266-273. IEEE, New York, 2001.\n Journal Version merged into Computational depth: Concept and applications.\n\n\n\n
\n\n\n\n \n \n $\"Computational$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{depth-CH,\nshow = 1,\nauthor = "L. Antunes and L. Fortnow and D. van Melkebeek",\ntitle = "Computational Depth",\nyear = 2001,\nurl = "https://dx.doi.org/10.1109/CCC.2001.933893",\ndoi = "10.1109/CCC.2001.933893",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict16,\npages = "266-273",\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 Testing random variables for independence and identity.\n \n \n \n \n\n\n \n Batu, T.; Fischer, E.; Fortnow, L.; Kumar, R.; Rubinfeld, R.; and White, P.\n\n\n \n\n\n\n In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pages 442-451. IEEE, New York, 2001.\n \n\n\n\n
\n\n\n\n \n \n $\"Testing$ paper\n \n \n \n $\"Testing$ 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

@incollection{independence-C,\nshow = 1,\ntitle = "Testing random variables for independence and identity",\nauthor = "T. Batu and E. Fischer and L. Fortnow\n          and R. Kumar and R. Rubinfeld and P. White",\nyear = 2001,\nurl_Paper = "https://lance.fortnow.com/papers/files/independence.pdf",\npublisher = "IEEE",\nurl = "https://dx.doi.org/10.1109/SFCS.2001.959920",\ndoi = "10.1109/SFCS.2001.959920",\naddress = "New York",\nbooktitle = focs42,\npages = "442-451"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Comparing Notions of Full Derandomization.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 16th IEEE Conference on Computational Complexity, pages 28-34. IEEE, New York, 2001.\n \n\n\n\n
\n\n\n\n \n \n $\"Comparing$ Paper\n \n \n \n $\"Comparing$ 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 14 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{hsg-C,\nshow = 1,\ntitle = "Comparing Notions of Full Derandomization",\nauthor = "L. Fortnow",\nyear = 2001,\nurl = "https://dx.doi.org/10.1109/CCC.2001.933869",\ndoi = "10.1109/CCC.2001.933869",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict16,\npages = "28-34",\nurl_Paper = "https://lance.fortnow.com/papers/files/hsg.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n An optimal procedure for gap closing in whole genome shotgun sequences.\n \n \n \n \n\n\n \n Beigel, R.; Alon, N.; Apaydin, M. S.; Fortnow, L.; and Kasif, S.\n\n\n \n\n\n\n In Proceedings of the 5th Annual International Conference on Computational Molecular Biology, pages 22-30. ACM, New York, 2001.\n \n\n\n\n
\n\n\n\n \n \n $\"An$ Paper\n \n \n \n $\"An$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{pipetting-C,\nshow = 1,\nauthor = "R. Beigel and N. Alon and M. S. Apaydin and L. Fortnow and S. Kasif",\ntitle = "An optimal procedure for gap closing in whole genome shotgun sequences",\nbooktitle = recomb5,\nurl = "https://dl.acm.org/authorize?05973",\ndoi = "10.1145/369133.369152",\nyear = 2001,\npublisher = "ACM",\naddress = "New York",\npages = "22-30",\nurl_Paper = "https://lance.fortnow.com/papers/files/pipetting.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Two Oracles that Force a Big Crunch.\n \n \n \n \n\n\n \n Buhrman, H.; Fenner, S.; Fortnow, L.; and Torenvliet, L.\n\n\n \n\n\n\n Computational Complexity, 10(2): 93-116. 2001.\n \n\n\n\n
\n\n\n\n \n \n $\"Two$ Paper\n \n \n \n $\"Two$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{BFFT-J,\nshow = 1,\nauthor = "H. Buhrman and S. Fenner and L. Fortnow and L. Torenvliet",\ntitle = "Two Oracles that Force a Big Crunch",\njournal = compcomp,\nyear = 2001,\nvolume = 10,\nnumber = 2,\nurl = "https://dx.doi.org/10.1007/s00037-001-8190-2",\ndoi = "10.1007/s00037-001-8190-2",\npages = "93-116",\nurl_Paper ="https://lance.fortnow.com/papers/files/nexp.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Kolmogorov Complexity.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n In Downey, R.; and Hirschfeldt, D., editor(s), 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.\n \n\n\n\n
\n\n\n\n \n \n $\"Kolmogorov$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 7 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{Kaikoura-J,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "Kolmogorov Complexity",\nseries = "{de Gruyter} Series in Logic and Its Applications",\nvolume = 4,\nyear = 2001,\npublisher = "{de Gruyter}",\neditor = "R. Downey and D. Hirschfeldt",\nbooktitle = "Aspects of Complexity, Minicourses in Algorithmics,\nComplexity, and\nComputational Algebra, NZMRI Mathematics Summer Meeting, Kaikoura, New\nZealand, January 7--15, 2000",\nurl_Paper = "https://lance.fortnow.com/papers/files/kaikoura.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Special Issue for the 1999 Conference on Computational Complexity.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Journal of Computer and System Sciences, 62(2). March 2001.\n Guest Editor.\n\n\n\n
\n\n\n\n \n \n $\"Special$ 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

@article{complexity99,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "Special Issue for the 1999 {Conference on Computational Complexity}",\njournal = jcss,\nyear = 2001,\nvolume = 62,\nnumber = 2,\nmonth = mar,\nURL = "https://dx.doi.org/10.1006/jcss.2000.1724",\ndoi = "10.1006/jcss.2000.1724",\nnote = "Guest Editor."}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 2000\n \n \n (4)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Time-Space Tradeoffs for Satisfiability.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Journal of Computer and System Sciences, 60(2): 337-353. April 2000.\n Special issue for selected papers from the 12th IEEE Conference on Computational Complexity.\n\n\n\n
\n\n\n\n \n \n $\"Time-Space$ Paper\n \n \n \n $\"Time-Space$ 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 9 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{npvsnl-J,\nshow = 1,\nauthor = {L. Fortnow},\ntitle = {Time-Space Tradeoffs for Satisfiability},\n\t\t  year = 2000,\nurl = "https://dx.doi.org/10.1006/jcss.1999.1671",\ndoi = "10.1006/jcss.1999.1671",\njournal = jcss,\nnote = {Special issue for selected papers from the 12th IEEE\nConference on Computational Complexity.},\nvolume = 60,\nnumber = 2,\nmonth = apr,\npages = "337-353",\nurl_Paper = "https://lance.fortnow.com/papers/files/npvsnl.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Diagonalization.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Bulletin of the European Association for Theoretical Computer Science, 71: 102-112. June 2000.\n Computational Complexity Column.\n\n\n\n
\n\n\n\n \n \n $\"Diagonalization$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{diag-O,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "Diagonalization",\njournal = beatcs,\nyear = 2000,\nvolume = 71,\nmonth = jun,\nnote = "Computational Complexity Column.",\nurl_Paper = "https://lance.fortnow.com/papers/files/diag.pdf",\npages = "102-112"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Separating Complexity Classes Using Autoreducibility.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; van Melkebeek, D.; and Torenvliet, L.\n\n\n \n\n\n\n SIAM Journal on Computing, 29(5): 1497-1520. 2000.\n \n\n\n\n
\n\n\n\n \n \n $\"Separating$ Paper\n \n \n \n $\"Separating$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{auto-J,\nshow = 1,\ntitle = "Separating Complexity Classes Using Autoreducibility",\nauthor = "H. Buhrman and L. Fortnow and D. van Melkebeek\nand L. Torenvliet",\nurl = "https://dx.doi.org/10.1137/S0097539798334736",\ndoi = "10.1137/S0097539798334736",\njournal = sicomp,\nyear = 2000,\nurl_paper = {https://lance.fortnow.com/papers/files/auto.pdf},\nvolume = 29,\nnumber = 5,\npages = "1497-1520"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Optimal Proof Systems and Sparse Sets.\n \n \n \n \n\n\n \n Buhrman, H.; Fenner, S.; Fortnow, L.; and van Melkebeek, D.\n\n\n \n\n\n\n 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.\n \n\n\n\n
\n\n\n\n \n \n $\"Optimal$ Paper\n \n \n \n $\"Optimal$ 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

@incollection{npsparse-C,\nshow = 1,\nauthor = "H. Buhrman and S. Fenner and L. Fortnow and D. van Melkebeek",\ntitle = "Optimal Proof Systems and Sparse Sets",\nyear = 2000,\npublisher = springer,\nbooktitle = stacs17,\naddress = "Berlin",\nseries = lncs,\nvolume = 1770,\npages = "407-418",\nurl = "https://dx.doi.org/10.1007/3-540-46541-3_34",\ndoi = "10.1007/3-540-46541-3_34",\nurl_Paper = "https://lance.fortnow.com/papers/files/npsparse.pdf"}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 1999\n \n \n (5)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n One-Sided Versus Two-Sided Error in Probabilistic Computation.\n \n \n \n \n\n\n \n Buhrman, H.; and Fortnow, L.\n\n\n \n\n\n\n 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.\n \n\n\n\n
\n\n\n\n \n \n $\"One-Sided$ Paper\n \n \n \n $\"One-Sided$ 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 7 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{rpvsbpp-C,\nshow = 1,\nauthor = "H. Buhrman and L. Fortnow",\ntitle = "One-Sided Versus Two-Sided Error in Probabilistic Computation",\nbooktitle = stacs16,\nyear = 1999,\naddress = "Berlin",\nseries = lncs,\npublisher = springer,\nvolume = 1563,\npages = {100-109},\nurl = "https://dx.doi.org/10.1007/3-540-49116-3_9",\ndoi = "dx.doi.org/10.1007/3-540-49116-3_9",\nurl_Paper = "https://lance.fortnow.com/papers/files/rpvsbpp.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Complexity limitations on quantum computation.\n \n \n \n \n\n\n \n Fortnow, L.; and Rogers, J.\n\n\n \n\n\n\n Journal of Computer and System Sciences, 59(2): 240–252. 1999.\n Special issue for selected papers from the 13th IEEE Conference on Computational Complexity\n\n\n\n
\n\n\n\n \n \n $\"Complexity$ Paper\n \n \n \n $\"Complexity$ 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 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{quantum-J,\nshow = 1,\nauthor = "L. Fortnow and J. Rogers",\ntitle = "Complexity limitations on quantum computation",\njournal = jcss,\nurl = "https://dx.doi.org/10.1006/jcss.1999.1651",\ndoi = "10.1006/jcss.1999.1651",\nvolume = 59,\nnumber = 2,\nyear = 1999,\npages = "240--252",\nnote = {Special issue for selected papers from the 13th IEEE\nConference on Computational Complexity},\nurl_Paper = "https://lance.fortnow.com/papers/files/quantum.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Two Queries.\n \n \n \n \n\n\n \n Buhrman, H.; and Fortnow, L.\n\n\n \n\n\n\n Journal of Computer and System Sciences, 59(2): 182-194. 1999.\n Special issue for selected papers from the 13th IEEE Conference on Computational Complexity\n\n\n\n
\n\n\n\n \n \n $\"Two$ Paper\n \n \n \n $\"Two$ 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

@article{queries-J,\nshow = 1,\nauthor = {H. Buhrman and L. Fortnow},\ntitle = {Two Queries},\n\t\t  year = 1999,\njournal = jcss,\nurl = "https://dx.doi.org/10.1006/jcss.1999.1647",\ndoi = "10.1006/jcss.1999.1647",\nnote = {Special issue for selected papers from the 13th IEEE\nConference on Computational Complexity},\nvolume = 59,\nnumber = 2,\npages = "182-194",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/queries.pdf}}\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Relativized Worlds with an Infinite Hierarchy.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Information Processing Letters, 69(6): 309-313. 1999.\n \n\n\n\n
\n\n\n\n \n \n $\"Relativized$ Paper\n \n \n \n $\"Relativized$ 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

@article{sppph-J,\nshow = 1,\nauthor = {L. Fortnow},\ntitle = "Relativized Worlds with an Infinite Hierarchy",\nurl = "https://dx.doi.org/10.1016/S0020-0190(99)00034-4",\ndoi = "10.1016/S0020-0190(99)00034-4",\njournal = ipl,\nvolume = 69,\nnumber = 6,\nyear = 1999,\npages = "309-313",\nurl_paper = {https://lance.fortnow.com/papers/files/sppph.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n L-Printable sets.\n \n \n \n \n\n\n \n Fortnow, L.; Goldsmith, J.; Levy, M.; and Mahaney, S.\n\n\n \n\n\n\n SIAM Journal on Computing, 28(1): 137-151. 1999.\n \n\n\n\n
\n\n\n\n \n \n $\"L-Printable$ Paper\n \n \n \n $\"L-Printable$ 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

@article{logprint-J,\nshow = 1,\nauthor = "L. Fortnow and J. Goldsmith and M. Levy and S. Mahaney",\ntitle = "{L}-Printable sets",\nurl = "https://dx.doi.org/10.1137/S0097539796300441",\ndoi = "10.1137/S0097539796300441",\njournal = sicomp,\nvolume = 28,\nnumber = 1,\nyear = 1999,\npages = "137-151",\nurl_paper = {https://lance.fortnow.com/papers/files/logprint.pdf}}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 1998\n \n \n (6)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n NP Might Not Be As Easy As Detecting Unique Solutions.\n \n \n \n \n\n\n \n Beigel, R.; Buhrman, H.; and Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 30th ACM Symposium on the Theory of Computing, pages 203-208. ACM, New York, 1998.\n \n\n\n\n
\n\n\n\n \n \n $\"NP$ Paper\n \n \n \n $\"NP$ 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

@incollection{newiso-C,\nshow = 1,\nauthor={R. Beigel and H. Buhrman and L. Fortnow},\ntitle = {{NP} Might Not Be As Easy As Detecting Unique\n     Solutions},\nurl = "https://dl.acm.org/authorize?80994",\ndoi = "10.1145/276698.276737",\npublisher = "ACM",\naddress = "New York",\nbooktitle = stoc30,\nyear = 1998,\npages = "203-208",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/newiso.pdf}}\t\t\n\t\t\n\t\t

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Nonrelativizing Separations.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; and Thierauf, T.\n\n\n \n\n\n\n In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 8-12. IEEE, New York, 1998.\n \n\n\n\n
\n\n\n\n \n \n $\"Nonrelativizing$ Paper\n \n \n \n $\"Nonrelativizing$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{nonrel-C,\nshow = 1,\nauthor={H. Buhrman and L. Fortnow and T. Thierauf},\ntitle = {Nonrelativizing Separations},\n\t\t  year = 1998,\nurl = "https://dx.doi.org/10.1109/CCC.1998.694585",\ndoi = "10.1109/CCC.1998.694585",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict13,\n\t\t  pages = {8-12},\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/nonrel.pdf}}\n\t\t\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Nearly Optimal Language Compression Using Extractors.\n \n \n \n \n\n\n \n Fortnow, L.; and Laplante, S.\n\n\n \n\n\n\n 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.\n Journal Version merged into Resource-Bounded Kolmogorov Complexity Revisited.\n\n\n\n
\n\n\n\n \n \n $\"Nearly$ 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

@incollection{extr-CH,\nshow = 1,\nauthor = {L. Fortnow and S. Laplante},\ntitle = {Nearly Optimal Language Compression Using Extractors},\nbooktitle = stacs15,\nyear = 1998,\naddress = "Berlin",\nseries = lncs,\npublisher = springer,\nurl = "https://dx.doi.org/10.1007/BFb0028551",\ndoi = "10.1007/BFb0028551",\nvolume = 1373,\n\t\t  pages = {84-93},\nnote = {Journal Version merged into\n<a href="https://bibbase.org/network/publication/buhrman-fortnow-laplante-resourceboundedkolmogorovcomplexityrevisited-2002">Resource-Bounded Kolmogorov Complexity Revisited</a>.}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Beating a finite automaton in the big match.\n \n \n \n \n\n\n \n Fortnow, L.; and Kimmel, P.\n\n\n \n\n\n\n In Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge, pages 225-234. Morgan Kaufmann, San Francisco, 1998.\n \n\n\n\n
\n\n\n\n \n \n $\"Beating$ Paper\n \n \n \n $\"Beating$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{bigmatch-C,\nshow = 1,\nauthor = "L. Fortnow and P. Kimmel",\ntitle = "Beating a finite automaton in the big match",\nbooktitle = tark7,\nurl = "https://portal.acm.org/citation.cfm?id=645876.671886",\nyear = 1998,\npages = "225-234",\npublisher = {Morgan Kaufmann},\naddress = {San Francisco},\nurl_paper = {https://lance.fortnow.com/papers/files/bigmatch.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n On the Relative Sizes of Learnable Sets.\n \n \n \n \n\n\n \n Fortnow, L.; Freivalds, R.; Gasarch, W.; Kummer, M.; Kurtz, S.; Smith, C.; and Stephan, F.\n\n\n \n\n\n\n Theoretical Computer Science, 197: 139-156. 1998.\n \n\n\n\n
\n\n\n\n \n \n $\"On$ Paper\n \n \n \n $\"On$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{measure-J,\nshow = 1,\nauthor = "L. Fortnow and R. Freivalds and W. Gasarch and M. Kummer\n          and S. Kurtz and C. Smith and F. Stephan",\ntitle = "On the Relative Sizes of Learnable Sets",\nurl = "https://dx.doi.org/10.1016/S0304-3975(97)00175-8",\ndoi = "10.1016/S0304-3975(97)00175-8",\njournal = tcs,\nvolume = 197,\npages = "139-156",\nyear = 1998,\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/measure.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n On Coherence, Random-self-reducibility, and Self-correction.\n \n \n \n \n\n\n \n Feigenbaum, J.; Fortnow, L.; Laplante, S.; and Naik, A.\n\n\n \n\n\n\n Computational Complexity, 7(2): 174-191. 1998.\n \n\n\n\n
\n\n\n\n \n \n $\"On$ Paper\n \n \n \n $\"On$ 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

@article{crsra-J,\nshow = 1,\nauthor = "J. Feigenbaum and L. Fortnow and S. Laplante and A. Naik",\ntitle = "On Coherence, Random-self-reducibility, and Self-correction",\njournal = compcomp,\nvolume = 7,\nnumber = 2,\nyear = 1998,\nurl = "https://dx.doi.org/10.1007/s000370050009",\ndoi = "10.1007/s000370050009",\nurl_paper = {https://lance.fortnow.com/papers/files/crsra.pdf},\npages = "174-191"}\n\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 1997\n \n \n (3)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Six hypotheses in search of a theorem.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; and Torenvliet, L.\n\n\n \n\n\n\n In Proceedings of the 12th IEEE Conference on Computational Complexity, pages 2-12. IEEE, New York, 1997.\n Survey.\n\n\n\n
\n\n\n\n \n \n $\"Six$ Paper\n \n \n \n $\"Six$ 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 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{sixhyp-O,\nshow = 1,\nauthor = {H. Buhrman and L. Fortnow and L. Torenvliet},\ntitle = {Six hypotheses in search of a theorem},\nurl = "https://dx.doi.org/10.1109/CCC.1997.612295",\ndoi = "10.1109/CCC.1997.612295",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict12,\nyear = 1997,\npages = {2-12},\n\t\t  note = {Survey.},\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/six.pdf}}\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Results on Resource-Bounded Measure.\n \n \n \n \n\n\n \n Buhrman, H.; Fenner, S.; and Fortnow, L.\n\n\n \n\n\n\n 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.\n \n\n\n\n
\n\n\n\n \n \n $\"Results$ Paper\n \n \n \n $\"Results$ 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

@incollection{oracle-C,\nshow = 1,\nauthor = {H. Buhrman and S. Fenner and L. Fortnow},\ntitle = {Results on Resource-Bounded Measure},\nbooktitle = icalp24,\nyear = 1997,\npublisher = springer,\nseries = lncs,\nurl = "https://dx.doi.org/10.1007/3-540-63165-8_176",\ndoi = "10.1007/3-540-63165-8_176",\nvolume = 1256,\npages = {188-194},\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/oracle.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Counting Complexity.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n In Hemaspaandra, L.; and Selman, A., editor(s), Complexity Theory Retrospective II, pages 81-107. Springer, 1997.\n Survey\n\n\n\n
\n\n\n\n \n \n $\"Counting$ paper\n \n \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

@incollection{counting-O,\nshow = 1,\n\tauthor={L. Fortnow},\n\ttitle={Counting Complexity},\n\tbooktitle = "Complexity Theory Retrospective II",\n\teditor={L. Hemaspaandra and A. Selman},\n        publisher = springer,\n\tyear = 1997,\npages = {81-107},\n\t\t  note = {Survey},\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/counting.pdf}}\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 1996\n \n \n (6)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n On Resource-Bounded Instance Complexity.\n \n \n \n \n\n\n \n Fortnow, L.; and Kummer, M.\n\n\n \n\n\n\n Theoretical Computer Science A, 161: 123-140. 1996.\n \n\n\n\n
\n\n\n\n \n \n $\"On$ Paper\n \n \n \n $\"On$ 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

@article{instance-J,\nshow = 1,\nauthor = "L. Fortnow and M. Kummer",\ntitle = "On Resource-Bounded Instance Complexity",\nurl = "https://dx.doi.org/10.1016/0304-3975(95)00097-6",\ndoi = "10.1016/0304-3975(95)00097-6",\njournal = tcsa,\nyear = 1996,\nvolume = 161,\npages = "123-140",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/instance.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Complexity Theory Newsflash.\n \n \n \n \n\n\n \n Fenner, S.; Fortnow, L.; and Gasarch, W.\n\n\n \n\n\n\n SIGACT News, 23(3): 126. September 1996.\n Parody.\n\n\n\n
\n\n\n\n \n \n $\"Complexity$ Paper\n \n \n \n $\"Complexity$ 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

@article{FFG-O,\nshow = 1,\nauthor = {S. Fenner and L. Fortnow and W. Gasarch},\ntitle = {Complexity Theory Newsflash},\nnote = {Parody.},\nurl = "https://dl.acm.org/authorize?37386",\ndoi = "10.1145/235666.571629",\njournal = sigact,\nvolume = 23,\nnumber = 3,\nmonth = sep,\nyear = 1996,\npages = {126},\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/p=np.pdf}}\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n The isomorphism conjecture holds relative to an oracle.\n \n \n \n \n\n\n \n Fenner, S.; Fortnow, L.; and Kurtz, S.\n\n\n \n\n\n\n SIAM Journal on Computing, 25(1): 193-206. 1996.\n \n\n\n\n
\n\n\n\n \n \n $\"The$ Paper\n \n \n \n $\"The$ 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 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{FFK2-J,\nshow = 1,\nauthor = "Fenner, S. and L. Fortnow and S. Kurtz",\ntitle = "The isomorphism conjecture holds relative to an oracle",\njournal = sicomp,\nurl = "https://dx.doi.org/10.1137/S0097539793248305",\ndoi = "10.1137/S0097539793248305",\nyear = 1996,\nvolume = 25,\nnumber = 1,\npages = "193-206",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/iso.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n PP is Closed Under Truth-Table Reductions.\n \n \n \n \n\n\n \n Fortnow, L.; and Reingold, N.\n\n\n \n\n\n\n Information and Computation, 124(1): 1-6. 1996.\n \n\n\n\n
\n\n\n\n \n \n $\"PP$ Paper\n \n \n \n $\"PP$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{FR-J,\nshow = 1,\nauthor = "L. Fortnow and N. Reingold",\ntitle = "{PP} is Closed Under Truth-Table Reductions",\nurl = "https://dx.doi.org/10.1006/inco.1996.0001",\ndoi = "10.1006/inco.1996.0001",\njournal = iandcomp,\nvolume = 124,\nnumber = 1,\npages = "1-6",\nyear = 1996,\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/pptt.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Generic Separations.\n \n \n \n \n\n\n \n Fortnow, L.; and Yamakami, T.\n\n\n \n\n\n\n Journal of Computer and System Sciences, 52(1): 191-197. 1996.\n \n\n\n\n
\n\n\n\n \n \n $\"Generic$ Paper\n \n \n \n $\"Generic$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{FY-J,\nshow = 1,\nauthor = "L. Fortnow and T. Yamakami",\ntitle = "Generic Separations",\nurl = "https://dx.doi.org/10.1006/jcss.1996.0015",\ndoi = "10.1006/jcss.1996.0015",\njournal = jcss,\nvolume = 52,\nnumber = 1,\nyear = 1996,\npages = "191-197",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/gensep.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Gap-Definability as a Closure Property.\n \n \n \n \n\n\n \n Fenner, S.; Fortnow, L.; and Li, L.\n\n\n \n\n\n\n Information and Computation, 130(1): 1–17. 1996.\n \n\n\n\n
\n\n\n\n \n \n $\"Gap-Definability$ Paper\n \n \n \n $\"Gap-Definability$ 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

@Article{FFL-J,\nshow = 1,\ntitle={Gap-Definability as a Closure Property},\nauthor={S. Fenner and L. Fortnow and L. Li},\nurl = "https://dx.doi.org/10.1006/inco.1996.0080",\ndoi = "10.1006/inco.1996.0080",\npages={1--17},\njournal=iandcomp,\nyear=1996,\nvolume=130,\nnumber=1,\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/gaps2.pdf}\n}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 1995\n \n \n (2)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Circuit Lower Bounds \\em a la Kolmogorov.\n \n \n \n \n\n\n \n Fortnow, L.; and Laplante, S.\n\n\n \n\n\n\n Information and Compuation, 123(1): 121-126. 1995.\n \n\n\n\n
\n\n\n\n \n \n $\"Circuit$ Paper\n \n \n \n $\"Circuit$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{switch-J,\nshow = 1,\nauthor = "L. Fortnow and S. Laplante",\ntitle = "Circuit Lower Bounds {\\em a la} {K}olmogorov",\nurl = "https://dx.doi.org/10.1006/inco.1995.1161",\ndoi = "10.1006/inco.1995.1161",\nyear = 1995,\njournal = infcmp,\nvolume = 123,\nnumber = 1,\npages = "121-126",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/switch.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Beyond $P^{NP}=NEXP$.\n \n \n \n \n\n\n \n Fenner, S.; and Fortnow, L.\n\n\n \n\n\n\n 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.\n Journal version: Two Oracles that Force a Big Crunch\n\n\n\n
\n\n\n\n \n \n $\"Beyond$ 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

@incollection{Fenner-Fortnow-CH,\nshow = 1,\nauthor = "S. Fenner and L. Fortnow",\ntitle = "Beyond {$P^{NP}=NEXP$}",\nbooktitle = stacs12,\nyear = 1995,\naddress = "Berlin",\nseries = lncs,\nvolume = 900,\npublisher = springer,\npages = "619-627",\nurl = "https://dx.doi.org/10.1007/3-540-59042-0_110",\ndoi = "10.1007/3-540-59042-0_110",\nnote = {Journal version:\n<a href="https://bibbase.org/network/publication/buhrman-fenner-fortnow-torenvliet-twooraclesthatforceabigcrunch-2001"><it>Two Oracles that Force a Big Crunch</it></a>}\n}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 1994\n \n \n (9)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n The Infinite Version of an Open Communication Complexity Problem is Independent of the Axioms of Set Theory.\n \n \n \n \n\n\n \n Fortnow, L.; Kurtz, S.; and Whang, D.\n\n\n \n\n\n\n SIGACT News, 25(1): 87-89. 1994.\n Survey.\n\n\n\n
\n\n\n\n \n \n $\"The$ Paper\n \n \n \n $\"The$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{FKW-O,\nshow = 1,\nauthor = "L. Fortnow and S. Kurtz and D. Whang",\ntitle = "The Infinite Version of an Open Communication Complexity\n         Problem is Independent of the Axioms of Set Theory",\njournal = sigact,\nvolume = 25,\nnumber = 1,\nurl = "https://dl.acm.org/authorize?715174",\ndoi = "10.1145/181773.181778",\nyear = 1994,\npages = "87-89",\n\t\t  note = {Survey.},\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/ccind.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Gap-Definable Counting Classes.\n \n \n \n \n\n\n \n Fenner, S.; Fortnow, L.; and Kurtz, S.\n\n\n \n\n\n\n Journal of Computer and System Sciences, 48(1): 116-148. 1994.\n Special issue for selected papers from the 6th IEEE Structure in Complexity Theory Conference.\n\n\n\n
\n\n\n\n \n \n $\"Gap-Definable$ Paper\n \n \n \n $\"Gap-Definable$ 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

@article{FFK-J,\nshow = 1,\nauthor = "Fenner, S. and L. Fortnow and S. Kurtz",\ntitle = "Gap-Definable Counting Classes",\nurl = "https://dx.doi.org/10.1016/S0022-0000(05)80024-8",\ndoi = "10.1016/S0022-0000(05)80024-8",\njournal = jcss,\nyear = 1994,\nvolume = 48,\nnumber = 1,\npages = "116-148",\nnote = {Special issue for selected papers from the 6th IEEE Structure in\n                 Complexity Theory Conference.},\n\t\t  \t\t  url_paper = {https://lance.fortnow.com/papers/files/gaps.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n The Power of Adaptiveness and Additional Queries in Random-Self-Reductions.\n \n \n \n \n\n\n \n Feigenbaum, J.; Fortnow, L.; Lund, C.; and Spielman, D.\n\n\n \n\n\n\n Computational Complexity, 4: 158-174. 1994.\n \n\n\n\n
\n\n\n\n \n \n $\"The$ Paper\n \n \n \n $\"The$ 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

@ARTICLE{FFLS-J,\nshow = 1,\nAUTHOR = "J. Feigenbaum and L. Fortnow and C. Lund and D. Spielman",\nTITLE = "The Power of Adaptiveness and Additional Queries in\n         Random-Self-Reductions",\nJournal = compcomp,\nurl = "https://dx.doi.org/10.1007/BF01202287",\ndoi = "10.1007/BF01202287",\nYear = 1994,\nvolume = 4,\npages = "158-174",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/rsr2.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n My Favorite Ten Complexity Theorems of the Past Decade.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n 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.\n Invited lecture.\n\n\n\n
\n\n\n\n \n \n $\"My$ Paper\n \n \n \n $\"My$ 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 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{topten-O,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "My Favorite Ten Complexity Theorems of the Past Decade",\nyear = 1994,\nvolume = 880,\npages = "256-275",\nseries = lncs,\naddress = "Berlin",\npublisher = springer,\nbooktitle = fsttcs14,\nurl = "https://dx.doi.org/10.1007/3-540-58715-2_130",\ndoi = "10.1007/3-540-58715-2_130",\nnote = "Invited lecture.",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/topten.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n On the Power of Multi-Prover Interactive Protocols.\n \n \n \n \n\n\n \n Fortnow, L.; Rompel, J.; and Sipser, M.\n\n\n \n\n\n\n Theoretical Computer Science A, 134: 545-557. 1994.\n \n\n\n\n
\n\n\n\n \n \n $\"On$ Paper\n \n \n \n $\"On$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{FRS-J,\nshow = 1,\nAUTHOR = "Fortnow, L. and J. Rompel and M. Sipser",\nTITLE = "On the Power of Multi-Prover Interactive Protocols",\nurl = "https://dx.doi.org/10.1016/0304-3975(94)90251-8",\ndoi = "10.1016/0304-3975(94)90251-8",\njournal = tcsa,\nyear = 1994,\nvolume = 134,\npages = "545-557",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/mip.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Extremes in the Degrees of Inferability.\n \n \n \n \n\n\n \n Fortnow, L.; Gasarch, W.; Jain, S.; Kinber, E.; Kummer, M.; Kurtz, S.; Pleszkoch, M.; Slaman, T.; Solovay, R.; and Stephan, F.\n\n\n \n\n\n\n Annals of Pure and Applied Logic, 66: 231-276. 1994.\n \n\n\n\n
\n\n\n\n \n \n $\"Extremes$ Paper\n \n \n \n $\"Extremes$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{extremes-J,\nshow = 1,\nauthor = "L. Fortnow and W. Gasarch and S. Jain and E. Kinber and\n          M. Kummer and S. Kurtz and M. Pleszkoch and T. Slaman\n          and R. Solovay and F. Stephan",\ntitle = "Extremes in the Degrees of Inferability",\nurl = "https://dx.doi.org/10.1016/0168-0072(94)90035-3",\ndoi = "10.1016/0168-0072(94)90035-3",\njournal = apal,\nyear = 1994,\nvolume = 66,\npages = "231-276",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/extremes.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n The Role of Relativization in Complexity Theory.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Bulletin of the European Association for Theoretical Computer Science, 52: 229-244. February 1994.\n Computational Complexity Column.\n\n\n\n
\n\n\n\n \n \n $\"The$ 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

@article{relative-O,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "The Role of Relativization in Complexity Theory",\njournal = beatcs,\nyear = 1994,\nvolume = 52,\npages = "229-244",\nmonth = feb,\nnote = "Computational Complexity Column.",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/relative.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n The Internal and External Algebraic Structure of Complexity Classes.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Technical Report IMSc, 1994.\n Collected papers of the Workshop on Algebraic Methods in Complexity Theory. Survey.\n\n\n\n
\n\n\n\n \n \n $\"The$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@techreport{alg-O,\nshow = 1,\nauthor = "L. Fortnow",\ntitle = "The Internal and External Algebraic Structure of Complexity\nClasses",\ninstitution = "IMSc",\nyear = 1994,\nnote = "Collected papers of the Workshop on Algebraic Methods in Complexity\nTheory. Survey.",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/alg.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Optimality and Domination in Repeated Games with Bounded Players.\n \n \n \n \n\n\n \n Fortnow, L.; and Whang, D.\n\n\n \n\n\n\n In Proceedings of the 26th ACM Symposium on the Theory of Computing, pages 741-749. ACM, New York, 1994.\n \n\n\n\n
\n\n\n\n \n \n $\"Optimality$ Paper\n \n \n \n $\"Optimality$ 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

@incollection{FW-C,\nshow = 1,\nauthor = "L. Fortnow and D. Whang",\ntitle = "Optimality and Domination in Repeated Games with Bounded Players",\nurl = "https://dl.acm.org/authorize?72098",\ndoi = "10.1145/195058.195448",\npublisher = "ACM",\naddress = "New York",\nbooktitle = stoc26,\nyear = 1994,\npages = "741-749",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/games.pdf}}\n\t\t\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 1993\n \n \n (3)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n BPP has subexponential simulations unless EXPTIME has publishable proofs.\n \n \n \n \n\n\n \n Babai, L.; Fortnow, L.; Nisan, N.; and Wigderson, A.\n\n\n \n\n\n\n Computational Complexity, 3: 307-318. 1993.\n \n\n\n\n
\n\n\n\n \n \n $\"BPP$ Paper\n \n \n \n $\"BPP$ 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

@article{BFNW-J,\nshow = 1,\nauthor = "L. Babai and L. Fortnow and N. Nisan and A. Wigderson",\ntitle = "{BPP} has subexponential simulations unless {EXPTIME}\n         has publishable proofs",\njournal = compcomp,\nurl = "https://dx.doi.org/10.1007/BF01275486",\ndoi = "10.1007/BF01275486",\nyear = 1993,\nvolume = 3,\npages = "307-318",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/bppexp.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n On the Random-Self-Reducibility of Complete Sets.\n \n \n \n \n\n\n \n Feigenbaum, J.; and Fortnow, L.\n\n\n \n\n\n\n SIAM Journal on Computing, 22: 994-1005. 1993.\n \n\n\n\n
\n\n\n\n \n \n $\"On$ Paper\n \n \n \n $\"On$ 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

@article{FF-J,\nshow = 1,\nauthor = "Feigenbaum, J. and L. Fortnow",\ntitle = "On the Random-Self-Reducibility of Complete Sets",\njournal = sicomp,\nurl = "https://dx.doi.org/10.1137/0222061",\ndoi = "10.1137/0222061",\nvolume = 22,\nyear = 1993,\npages = "994-1005",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/rsr.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Interactive Proof Systems and Alternating Time-Space Complexity.\n \n \n \n \n\n\n \n Fortnow, L.; and Lund, C.\n\n\n \n\n\n\n Theoretical Computer Science A, 113: 55-73. 1993.\n \n\n\n\n
\n\n\n\n \n \n $\"Interactive$ Paper\n \n \n \n $\"Interactive$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{FL-J,\nshow = 1,\nAUTHOR = "Fortnow, L. and C. Lund",\nTITLE = "Interactive Proof Systems and Alternating Time-Space Complexity",\nurl = "https://dx.doi.org/10.1016/0304-3975(93)90210-K",\ndoi = "10.1016/0304-3975(93)90210-K",\njournal = tcsa,\nvolume = 113,\npages = "55-73",\nyear = 1993,\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/ipspace.pdf}}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 1992\n \n \n (2)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n On the power of two-local random reductions.\n \n \n \n \n\n\n \n Fortnow, L.; and Szegedy, M.\n\n\n \n\n\n\n Information Processing Letters, 44(6): 303-306. 1992.\n \n\n\n\n
\n\n\n\n \n \n $\"On$ Paper\n \n \n \n $\"On$ 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 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{FSz-J,\nshow = 1,\nauthor = "L. Fortnow and M. Szegedy",\ntitle = "On the power of two-local random reductions",\nurl = "https://dx.doi.org/10.1016/0020-0190(92)90104-4",\ndoi = "10.1016/0020-0190(92)90104-4",\njournal = ipl,\nvolume = 44,\nnumber = 6,\nyear = 1992,\npages = "303-306",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/lrr.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Algebraic Methods for Interactive Proof Systems.\n \n \n \n \n\n\n \n Lund, C.; Fortnow, L.; Karloff, H.; and Nisan, N.\n\n\n \n\n\n\n Journal of the ACM, 39(4): 859-868. 1992.\n FOCS 2020 Test of Time Award for 1990 conference paper\n\n\n\n
\n\n\n\n \n \n $\"Algebraic$ Paper\n \n \n \n $\"Algebraic$ 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 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@ARTICLE{LFKN-J,\nshow = 1,\nAUTHOR = "Lund, C. and Fortnow, L. and Karloff, H. and Nisan, N.",\nTITLE = "Algebraic Methods for Interactive Proof Systems",\nurl = "https://dl.acm.org/authorize?87697",\ndoi = "10.1145/146585.146605",\nJournal = jacm,\nYear = 1992,\nvolume = 39,\nnumber = 4,\npages = "859-868",\nnote = "FOCS 2020 Test of Time Award for 1990 conference paper",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/ip.pdf}}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 1991\n \n \n (3)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Nondeterministic Exponential Time has Two-Prover Interactive Protocols.\n \n \n \n \n\n\n \n Babai, L.; Fortnow, L.; and Lund, C.\n\n\n \n\n\n\n Computational Complexity, 1(1): 3-40. 1991.\n 2020 FOCS Test of Time Award for 1990 conference paper\n\n\n\n
\n\n\n\n \n \n $\"Nondeterministic$ Paper\n \n \n \n $\"Nondeterministic$ 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 11 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@ARTICLE{BFL-J,\nshow = 1,\nAUTHOR = "Babai, L. and L. Fortnow and C. Lund",\nTITLE = "Nondeterministic Exponential Time has Two-Prover Interactive\nProtocols",\njournal = compcomp,\nurl = "https://dx.doi.org/10.1007/BF01200056",\ndoi = "10.1007/BF01200056",\nYEAR = "1991",\nVolume = 1,\nnumber = 1,\npages = "3-40",\nnote = "2020 FOCS Test of Time Award for 1990 conference paper", \nurl_paper = {https://lance.fortnow.com/papers/files/mip2.pdf}}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Checking Computations in Polylogarithmic Time.\n \n \n \n \n\n\n \n Babai, L.; Fortnow, L.; Levin, L.; and Szegedy, M.\n\n\n \n\n\n\n In Proceedings of the 23rd ACM Symposium on the Theory of Computing, pages 21-31. ACM, New York, 1991.\n \n\n\n\n
\n\n\n\n \n \n $\"Checking$ Paper\n \n \n \n $\"Checking$ 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 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{BFLS-C,\nshow = 1,\nauthor = "L. Babai and L. Fortnow and L. Levin and M. Szegedy",\ntitle = "Checking Computations in Polylogarithmic Time",\nurl = "https://dl.acm.org/authorize?80692",\npublisher = "ACM",\naddress = "New York",\nbooktitle = stoc23,\nyear = 1991,\npages = "21-31",\ndoi = "10.1145/103418.103428",\nurl_paper = {https://lance.fortnow.com/papers/files/check.pdf}}\n\t\t\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Arithmetization: A new method in structural complexity theory.\n \n \n \n \n\n\n \n Babai, L.; and Fortnow, L.\n\n\n \n\n\n\n Computational Complexity, 1(1): 41-66. 1991.\n \n\n\n\n
\n\n\n\n \n \n $\"Arithmetization:$ Paper\n \n \n \n $\"Arithmetization:$ 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 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@ARTICLE{BaFo-J,\nshow = 1,\nAUTHOR = "Babai, L. and L. Fortnow",\nTITLE = "Arithmetization: A new method in structural complexity theory",\njournal = compcomp,\nurl = "https://dx.doi.org/10.1007/BF01200057",\ndoi = "10.1007/BF01200057",\nYEAR = "1991",\nVolume = 1,\nnumber = 1,\npages = "41-66",\n\turl_paper = {https://lance.fortnow.com/papers/files/sharpp.pdf}}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 1989\n \n \n (3)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Complexity-theoretic aspects of interactive proof systems.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Ph.D. Thesis, Massachusetts Institute of Technology, May 1989.\n Tech Report MIT/LCS/TR-447.\n\n\n\n
\n\n\n\n \n \n $\"Complexity-theoretic$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 7 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@PHDTHESIS{phd-U,\nshow = 1,\nAUTHOR = "Fortnow, L.",\nTITLE = "Complexity-theoretic aspects of interactive proof systems",\nSCHOOL = "Massachusetts Institute of Technology",\nMonth = may,\nNOTE = "Tech Report MIT/LCS/TR-447.",\nYEAR = "1989",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/thesis.pdf}}\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n The Complexity of Perfect Zero-Knowledge.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n In Micali, S., editor(s), Randomness and Computation, volume 5, of Advances in Computing Research, pages 327–343. JAI Press, Greenwich, 1989.\n See also the appendix of Computational Complexity and Knowledge Complexity by Goldreich, Ostrovsky and Petrank.\n\n\n\n
\n\n\n\n \n \n $\"The$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{Fo-JH,\nshow = 1,\nAUTHOR = "Fortnow, L.",\nTITLE = "The Complexity of Perfect Zero-Knowledge",\nEDITOR = "S. Micali",\nbooktitle = "Randomness and Computation",\nSERIES = acr,\nVOLUME = "5",\nYEAR = "1989",\naddress = "Greenwich",\nPUBLISHER = "JAI Press",\nPAGES = "327--343",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/pzk.pdf},\nnote = "See also the appendix of <a\nhref=https://www.argreenhouse.com/papers/rafail/18.html>Computational\nComplexity and Knowledge Complexity</a> by Goldreich, Ostrovsky and\nPetrank."}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Probabilistic Computation and Linear Time.\n \n \n \n \n\n\n \n Fortnow, L.; and Sipser, M.\n\n\n \n\n\n\n In Proceedings of the 21st ACM Symposium on the Theory of Computing, pages 148–156. ACM, New York, 1989.\n \n\n\n\n
\n\n\n\n \n \n $\"Probabilistic$ Paper\n \n \n \n $\"Probabilistic$ 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 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@INCOLLECTION{FoSi-C,\nshow = 1,\nAUTHOR = "Fortnow, L. and M. Sipser",\nTITLE = "Probabilistic Computation and Linear Time",\nurl = "https://dl.acm.org/authorize?61974",\ndoi = "10.1145/73007.73021",\npublisher = "ACM",\naddress = "New York",\nbooktitle = stoc21,\nYEAR = "1989",\nPAGES = "148--156",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/pcltj.pdf}}\n\n

\n\n\n\n

\n\n\n\n\n\n

\n\n

\n \n 1988\n \n \n (1)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Are there interactive protocols for co-NP languages?.\n \n \n \n \n\n\n \n Fortnow, L.; and Sipser, M.\n\n\n \n\n\n\n Information Processing Letters, 28: 249–251. 1988.\n \n\n\n\n
\n\n\n\n \n \n $\"Are$ Paper\n \n \n \n $\"Are$ 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 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@ARTICLE{FS-J,\nshow = 1,\nAUTHOR = "Fortnow, L. and M. Sipser",\nTITLE = {{Are there interactive protocols for co-NP languages?}},\nurl = "https://dx.doi.org/10.1016/0020-0190(88)90199-8",\ndoi = "10.1016/0020-0190(88)90199-8",\nJOURNAL = ipl,\nVOLUME = "28",\nYEAR = "1988",\nPAGES = "249--251",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/conpipl.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 \n\n