\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%3A%2F%2Fgithub.com%2Ffortnow%2Fpubs2%2Fraw%2Fmaster%2Fpubs.bib&jsonp=1&jsonp=1\"></script>\n

\n\n PHP\n

\n            <?php\n            $contents = file_get_contents(\"https://bibbase.org/show?bib=https%3A%2F%2Fgithub.com%2Ffortnow%2Fpubs2%2Fraw%2Fmaster%2Fpubs.bib&jsonp=1\");\n            print_r($contents);\n            ?>\n

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

\n            <iframe src=\"https://bibbase.org/show?bib=https%3A%2F%2Fgithub.com%2Ffortnow%2Fpubs2%2Fraw%2Fmaster%2Fpubs.bib&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 2024\n \n \n (3)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Biography of Avi Wigderson: A. M. Turing Award Winner.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n 2024.\n \n\n\n\n
\n\n\n\n \n \n $\"Biography$ 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

@misc{Avi-bio-O,\nshow = 1,\nauthor       = {Lance Fortnow},\n  title        = {Biography of Avi Wigderson: A. M. Turing Award Winner},\n  year         = {2024},\n  url          = {https://amturing.acm.org/award_winners/wigderson_3844537.cfm},\npublisher = "ACM"}\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Computation Is All Around Us, and You Can See It If You Try.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Quanta Magazine. June 2024.\n Republished on wired.com, July 2024\n\n\n\n
\n\n\n\n \n \n $\"Computation$ Paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 13 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{quanta-computation,\n\tshow=1,\n\ttitle={Computation Is All Around Us, and You Can See It If You Try},\n\tauthor={Fortnow, Lance},\n\tjournal={Quanta Magazine},\n\tissue_date = "June 12, 2024",\n\tmonth = jun,\n\tyear={2024},\n\turl={https://www.quantamagazine.org/computation-is-all-around-us-and-you-can-see-it-if-you-try-20240612/},\n\tnote = "Republished on wired.com, July 2024"\n}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Contract and Commercial Law Challenges with AI Products and Services.\n \n \n \n \n\n\n \n Fortnow, L.; and Kim, N.\n\n\n \n\n\n\n In Elvy, S.; and Kim, N. S., editor(s), The Cambridge Handbook of Emerging Issues at the Intersection of Commercial Law and Technology, of Cambridge Law Handbooks. Cambridge University Press, Cambridge, December 2024.\n Not yet published. Preprint in SSRN\n\n\n\n
\n\n\n\n \n \n $\"Contract$ 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{Kim-Fortnow,\n\tshow = 1,\n\tauthor    = {L. Fortnow and N. Kim},\n\tnote      = {Not yet published. Preprint in SSRN},\n\turl = "http://dx.doi.org/10.2139/ssrn.4947104",\n\tdoi = "10.2139/ssrn.4947104",\n\ttitle     = {Contract and Commercial Law Challenges with {AI} Products and Services},\n\tbooktitle = {The Cambridge Handbook of Emerging Issues at the Intersection of Commercial Law and Technology},\n\teditor    = {Stacy-Ann Elvy and Nancy S. Kim},\n\tyear      = {2024},\n\tmonth     = dec,\n\tpublisher = {Cambridge University Press},\n\taddress   = {Cambridge},\n\tseries    = {Cambridge Law Handbooks},\n\tisbn      = {9781009279109}\n}

\n\n\n\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 54 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 28 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 22 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 (4)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Freestyle Dancing: 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 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, of SIGMETRICS '16, pages 381–382. ACM, New York, NY, USA, 2016.\n Poster.\n\n\n\n
\n\n\n\n \n \n $\"Freestyle$ Paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n \n \n \n \n \n \n \n \n\n\n\n

@incollection{dancing-C,\nnote = "Poster.",\nauthor = "L. Liu and Y. Wang and L. Fortnow and J. Li and J. Xu",\n  title = {Freestyle Dancing: {R}andomized Algorithms for Dynamic Storage Load-Balancing},\n booktitle = {Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science},\n series = {SIGMETRICS '16},\n year = {2016},\n isbn = {978-1-4503-4266-7},\n location = {Antibes Juan-les-Pins, France},\n pages = {381--382},\n numpages = {2},\n url = {https://dl.acm.org/authorize?N15266},\n doi = {10.1145/2896377.2901481},\n acmid = {2901481},\n publisher = {ACM},\n address = {New York, NY, USA},\n keywords = {birkhoff decomposition, capacity distribution, load balance, load distribution},\n}\n\n

\n\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 10 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 5 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 3 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 (6)\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 9 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 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 In Aceto, L.; Henzinger, M.; and Sgall, J., editor(s), Proceedings of the 38th International Colloquium on Automata, Languages and Programming, volume 6755, of Lecture Notes in Computer Science, pages 569-580. Springer Berlin / Heidelberg, 2011.\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 \n \n \n \n \n \n\n \n \n \n \n \n\n\n\n

@incollection{robust-C,\nauthor = "L. Fortnow and R. Santhanam",\n   affiliation = {Northwestern University, USA},\n   title = {Robust Simulations and Significant Separations},\n   editor = {L. Aceto and M. Henzinger and J. Sgall},\n   publisher = {Springer Berlin / Heidelberg},\n   isbn = {978-3-642-22005-0},\n   keyword = {Computer Science},\n   pages = {569-580},\n   volume = {6755},\n   url = {https://dx.doi.org/10.1007/978-3-642-22006-7_48},\n   doi = "10.1007/978-3-642-22006-7_48",\n   year = {2011},\nbooktitle = icalp38,\nseries = lncs,\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 Repeated Matching Pennies with Limited Randomness.\n \n \n \n \n\n\n \n Budinich, M.; and Fortnow, L.\n\n\n \n\n\n\n Technical Report 1102.1096 [cs.CC], arXiv.org e-Print archive, 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 \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

@techreport{mprand-U,\nauthor = "M. Budinich and L. Fortnow",\ntitle = "Repeated Matching Pennies with Limited Randomness",\nyear = 2011,\nurl = "https://arxiv.org/abs/1102.1096",\ninstitution = arxiv,\nnumber = "1102.1096 [cs.CC]",\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 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 4 downloads\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 (8)\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 12 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 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 Technical Report 1012.2034 [cs.CC], arXiv.org e-Print archive, 2010.\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 \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

@techreport{robust-U,\nauthor = "L. Fortnow and R. Santhanam",\ntitle = "Robust Simulations and Significant Separations",\nyear = 2010,\nurl = "https://arxiv.org/abs/1012.2034",\ninstitution = arxiv,\nnumber = "1012.2034 [cs.CC]",\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 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 In Marion, J.; and Schwentick, T., editor(s), Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science, volume 5, of Leibniz International Proceedings in Informatics (LIPIcs), pages 395–404. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2010.\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 \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{insep-C,\nauthor = "L. Fortnow and J. Lutz and E. Mayordomo",\ntitle = "Inseparability and Strong Hypotheses for Disjoint {NP} Pairs",\nurl        = {https://dx.doi.org/10.4230/LIPIcs.STACS.2010.2471},\nbooktitle =\tstacs27,\n  pages =\t{395--404},\n  series =\t{Leibniz International Proceedings in Informatics (LIPIcs)},\n  ISBN =\t{978-3-939897-16-3},\n  ISSN =\t{1868-8969},\n  year =\t{2010},\n  volume =\t{5},\n  editor =\t{Jean-Yves Marion and Thomas Schwentick},\n  publisher =\t{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},\n  address =\t{Dagstuhl, Germany},\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 \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 4 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 P and NP.\n \n \n \n \n\n\n \n Fortnow, L.; Fortnow, M.; and Gliksman, D.\n\n\n \n\n\n\n 2010.\n YouTube video. https://www.youtube.com/watch?v=HjUEEHTyhdA\n\n\n\n
\n\n\n\n \n \n $\"P$ Paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@misc{pnp-youtube-O,\nauthor = "L. Fortnow and M. Fortnow and D. Gliksman",\ntitle = "{P} and {NP}",\nurl = "https://www.youtube.com/watch?v=HjUEEHTyhdA",\nyear = 2010,\nnote = "YouTube video. https://www.youtube.com/watch?v=HjUEEHTyhdA"}\n\n\n% Also published in Computer Journal\n%https://comjnl.oxfordjournals.org/content/55/7/830.abstract?keytype=ref&ijkey=ffHtHazIHReTfgQ\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 2 downloads\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 (15)\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 18 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 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 Technical Report 0907.4775, arXiv.org e-Print archive, 2009.\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 \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

@techreport{equiv-U,\nauthor = "L. Fortnow and J. Grochow",\ntitle = "Complexity Classes of Equivalence Problems Revisited",\ninstitution = arxiv,\nyear = 2009,\nurl = "https://arxiv.org/abs/0907.4775",\nnumber = "0907.4775",\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 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 Technical Report 0912.3162, arXiv.org e-Print archive, 2009.\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 \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

@techreport{bppr-U,\nauthor = "H. Buhrman and L. Fortnow and M. Kouck\\'y and B. Loff",\ntitle = "Derandomizing from Random Strings",\ninstitution = arxiv,\nyear = 2009,\nurl = "https://arxiv.org/abs/0912.3162",\nnumber = "0912.3162",\nurl_Paper = "https://lance.fortnow.com/papers/files/bppr.pdf"}\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 6 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 5 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 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 Technical Report TR09-022, Electronic Colloquium on Computational Complexity, 2009.\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 \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

@techreport{insep-U,\nauthor = "L. Fortnow and J. Lutz and E. Mayordomo",\ntitle = "Inseparability and Strong Hypotheses for Disjoint {NP} Pairs",\nyear = 2009,\nurl = "https://eccc.hpi-web.de/report/2009/022/",\ninstitution = eccc,\nnumber = "TR09-022",\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 \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 16 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 \n \n Editor's Foreword.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n ACM Trans. Comput. Theory, 1: 1:1–1:2. February 2009.\n \n\n\n\n
\n\n\n\n \n \n $\"Editor's$ 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{Fortnow:2009:EF:1490270.1490271,\n author = {Fortnow, Lance},\n title = {Editor's Foreword},\n journal = {ACM Trans. Comput. Theory},\n volume = {1},\n issue = {1},\n month = {February},\n year = {2009},\n issn = {1942-3454},\n pages = {1:1--1:2},\n articleno = {1},\n numpages = {2},\n url = "https://dl.acm.org/authorize?010644",\n doi = "10.1145/1490270.1490271",\n acmid = {1490271},\n publisher = {ACM},\n address = {New York, NY, USA},\n}\n\n

\n\n\n\n

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

\n\n

\n \n 2008\n \n \n (8)\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 Technical Report 1473, Center for Mathematical Studies in Economics and Management Science Discussion Paper, 2008.\n \n\n\n\n
\n\n\n\n \n \n $\"Program$ Paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@techreport{discount-U,\nauthor = "L. Fortnow",\ntitle = "Program Equilibria and Discounted Computation Time",\ninstitution = cmsems,\nyear = 2008,\nurl = "https://www.kellogg.northwestern.edu/research/math/papers/1473.pdf",\nnumber = "1473"}\n\n

\n\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 2 downloads\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 3 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 \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 In Proceedings of the 9th ACM Conference on Electronic Commerce, pages 139. ACM, New York, 2008.\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

@incollection{forecast-C,\nauthor = "L. Fortnow and R. Vohra",\ntitle = "The Complexity of Forecast Testing",\nyear = 2008,\npublisher = "ACM",\naddress = "New York",\nurl = "https://dl.acm.org/authorize?074396",\ndoi = "10.1145/1386790.1386814",\nbooktitle = ec9,\npages = 139,\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 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 In Proceedings of the 40th ACM Symposium on the Theory of Computing, pages 133-142. ACM, New York, 2008.\n \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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{compress-C,\nauthor = "L. Fortnow and R. Santhanam",\ntitle = "Infeasibility of Instance Compression and Succinct {PCP}s for {NP}",\nyear = 2008,\npublisher = "ACM",\naddress = "New York",\nbooktitle = stoc40,\npages = "133-142",\nurl = "https://dl.acm.org/authorize?087314",\ndoi = "10.1145/1374376.1374398",\nurl_Paper = "https://lance.fortnow.com/papers/files/compress.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 Technical Report TR08-046, Electronic Colloquium on Computational Complexity, 2008.\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 \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

@techreport{aware-U,\nauthor = "N. Devanur and L. Fortnow",\ntitle = "A Computational Theory of Awareness and Decision Making",\nyear = 2008,\nurl = "https://eccc.hpi-web.de/eccc-reports/2008/TR08-046/index.html",\ninstitution = eccc,\nnumber = "TR08-046",\nurl_Paper = "https://lance.fortnow.com/papers/files/awareness.pdf"}\n\n

\n\n\n\n

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

\n\n

\n \n 2007\n \n \n (6)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Bluffing and Strategic Reticence in Prediction Markets.\n \n \n \n \n\n\n \n Chen, Y.; Reeves, D.; Pennock, D.; Hanson, R.; Fortnow, L.; and Gonen, R.\n\n\n \n\n\n\n In The 3rd International Workshop On Internet And Network Economics, volume 4858, of Lecture Notes in Computer Science, pages 70-81. Springer, Berlin, 2007.\n \n\n\n\n
\n\n\n\n \n \n $\"Bluffing$ Paper\n \n \n \n $\"Bluffing$ 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{bluffing-C,\nauthor = "Y. Chen and D. Reeves and D. Pennock and\nR. Hanson and L. Fortnow and R. Gonen",\ntitle = "Bluffing and Strategic Reticence\nin Prediction Markets",\nbooktitle = wine3,\npublisher = "Springer",\naddress = "Berlin",\nseries = lncs,\nyear = 2007,\nvolume = 4858,\npages = "70-81",\nurl = "https://dx.doi.org/10.1007/978-3-540-77105-0_10",\ndoi = "10.1007/978-3-540-77105-0_10",\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 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 Inverting Onto Functions and The Polynomial Hierarchy.\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 In Proceedings of the 2nd International Computer Science Symposium in Russia, of Lecture Notes in Computer Science, pages 92-103. Springer, 2007.\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

@incollection{phq-C,\nauthor = "H. Buhrman and L. Fortnow and M. Kouck\\'{y} and J. Rogers\nand N. Vereshchagin",\ntitle = "Inverting Onto Functions and The Polynomial Hierarchy",\nbooktitle = csr2,\nyear = 2007,\npublisher = springer,\nseries = lncs,\nurl_Paper = "https://lance.fortnow.com/papers/files/phq.pdf",\nurl = "https://dx.doi.org/10.1007/978-3-540-74510-5_12",\ndoi = "10.1007/978-3-540-74510-5_12",\npages = "92-103"}\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 Technical Report TR07-096, Electronic Colloquium on Computational Complexity, 2007.\n \n\n\n\n
\n\n\n\n \n \n $\"Infeasibility$ Paper\n \n \n \n $\"Infeasibility$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@techreport{compress-U,\nauthor = "L. Fortnow and R. Santhanam",\ntitle = "Infeasibility of Instance Compression and Succinct {PCP}s for {NP}",\nyear = 2007,\nurl = "https://eccc.hpi-web.de/eccc-reports/2007/TR07-096/index.html",\ninstitution = eccc,\nnumber = "TR07-096",\nurl_Paper = "https://lance.fortnow.com/papers/files/compress.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 1 download\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 (15)\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 3 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 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 In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, of Lecture Notes in Computer Science, pages 335-345. Springer, Berlin, 2006.\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{kex-C,\nauthor = "L. Fortnow and J. Hitchcock and A. Pavan\nand N.V. Vinodchandran and F. Wang",\ntitle = "Extracting Kolmogorov Complexity with Applications\nto Dimension Zero-One Laws",\nyear = 2006,\nbooktitle = icalp33,\npublisher = springer,\naddress = "Berlin",\nseries = lncs,\nnumber = 4051,\npages = "335-345",\nurl = "https://dx.doi.org/10.1007/11786986_30",\ndoi = "10.1007/11786986_30",\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 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 In Proceedings of the Nineteenth Annual Conference on Computational Learning Theory, volume 4005, of Lecture Notes in Computer Science, pages 350-363. Springer, Berlin, 2006.\n \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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{learnbound-C,\ntitle = "Efficient Learning Algorithms Yield Circuit Lower Bounds",\nauthor = "L. Fortnow and A. Klivans",\nbooktitle = colt19,\nyear = 2006,\nvolume = 4005,\npages = "350-363",\npublisher= "Springer",\naddress = "Berlin",\nseries = lncs,\nurl = "https://dx.doi.org/10.1007/11776420_27",\ndoi = "10.1007/11776420_27",\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 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 \n Legal Implications of Awareness of Unawareness.\n \n \n \n\n\n \n Chung, K.; and Fortnow, L.\n\n\n \n\n\n\n 2006.\n Manuscript\n\n\n\n
\n\n\n\n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@unpublished{loopholes-U,\nauthor = "K. Chung and L. Fortnow",\ntitle = "Legal Implications of Awareness of Unawareness",\nyear = 2006,\nnote = "Manuscript"}\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.; and Santhanam, R.\n\n\n \n\n\n\n Technical Report TR06-157, Electronic Colloquium on Computational Complexity, 2006.\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 \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

@techreport{linear-U,\nauthor = "L. Fortnow and R. Santhanam",\ntitle = "Fixed-Polynomial Size Circuit Bounds",\nyear = 2006,\nurl = "https://eccc.hpi-web.de/eccc-reports/2006/TR06-157/index.html",\ninstitution = eccc,\nnumber = "TR06-157",\nurl_Paper = "https://lance.fortnow.com/papers/files/linearcircuit.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 Technical Report TR06-125, Electronic Colloquium on Computational Complexity, 2006.\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 \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

@techreport{witness-U,\nauthor = "L. Antunes and L. Fortnow and A. Pinto and A. Souto",\ntitle = "Low-Depth Witnesses are Easy to Find",\nyear = 2006,\nurl = "https://eccc.hpi-web.de/eccc-reports/2006/TR06-125",\ninstitution = eccc,\nnumber = "TR06-125",\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 Betting on Permutations.\n \n \n \n\n\n \n Chen, Y.; Fortnow, L.; Nikolova, E.; and Pennock, D.\n\n\n \n\n\n\n 2006.\n Manuscript.\n\n\n\n
\n\n\n\n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@unpublished{pairbetting-U,\nauthor = "Y. Chen and L. Fortnow and E. Nikolova and D. Pennock",\ntitle = "Betting on Permutations",\nyear = 2006,\nnote = "Manuscript."}\n\n

\n\n\n\n

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

\n\n

\n \n 2005\n \n \n (13)\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 In Proceedings of the 20th IEEE Conference on Computational Complexity, pages 135-140. IEEE, New York, 2005.\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{tolerant-C,\nauthor = "E. Fischer and L. Fortnow",\ntitle = "Tolerant Versus Intolerant Testing for {Boolean} Properties",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict20,\npages = "135-140",\nyear = 2005,\nurl = "https://dx.doi.org/10.1109/CCC.2005.30",\ndoi = "10.1109/CCC.2005.30",\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 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 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 In Proceedings of the 20th IEEE Conference on Computational Complexity, pages 323-332. IEEE, New York, 2005.\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

@incollection{succinct-C,\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.1109/CCC.2005.18",\ndoi = "10.1109/CCC.2005.18",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict20,\npages = "323-332",\nyear = 2005,\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 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 4 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 4 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 10 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 1 download\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 \n \n Time-Bounded Universal Distributions.\n \n \n \n \n\n\n \n Antunes, L.; and Fortnow, L.\n\n\n \n\n\n\n Technical Report TR05-144, Electronic Colloquium on Computational Complexity, 2005.\n Current Title: Worst-Case Running Times for Average-Case Algorithms.\n\n\n\n
\n\n\n\n \n \n $\"Time-Bounded$ Paper\n \n \n \n $\"Time-Bounded$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@techreport{ud-U,\nauthor = "L. Antunes and L. Fortnow",\ntitle = "Time-Bounded Universal Distributions",\nyear = 2005,\nurl = "https://eccc.hpi-web.de/eccc-reports/2005/TR05-144/index.html",\ninstitution = eccc,\nnumber = "TR05-144",\nnote = "Current Title: Worst-Case Running Times for Average-Case Algorithms.",\nurl_Paper = "https://lance.fortnow.com/papers/files/ud.pdf"}\n\n

\n\n\n\n

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

\n\n

\n \n 2004\n \n \n (3)\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 8 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 Review of \\em Theory of semi-feasible algorithms by Lane Hemaspaandra and Leen Torenvliet.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n SIGACT News, 35(2): 16-18. June 2004.\n \n\n\n\n
\n\n\n\n \n \n $\"Review$ Paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{Lanereview-O,\nauthor = "L. Fortnow",\ntitle = "Review of {\\em Theory of semi-feasible algorithms}\nby Lane Hemaspaandra and Leen Torenvliet",\njournal = sigact,\nvolume = 35,\nnumber = 2,\nmonth = jun,\nyear = 2004,\npages = "16-18",\nurl = "https://doi.acm.org/10.1145/992287.992294"}\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 (17)\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 6 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 Infinitely-often Autoreducible Sets.\n \n \n \n \n\n\n \n Beigel, R.; Fortnow, L.; and Stephan, F.\n\n\n \n\n\n\n In Proceedings of the 14th Annual International Symposium on Algorithms and Computation, volume 2906, of Lecture Notes in Computer Science, pages 98-107. Springer, Berlin, 2003.\n \n\n\n\n
\n\n\n\n \n \n $\"Infinitely-often$ Paper\n \n \n \n $\"Infinitely-often$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{ioauto-C,\ntitle = "Infinitely-often Autoreducible Sets",\nauthor = "R. Beigel and L. Fortnow and F. Stephan",\nbooktitle = isaac14,\nseries = lncs,\naddress = "Berlin",\npublisher = springer,\nurl = "https://www.springerlink.com/link.asp?id=pbprbxp2mmnk5cnq",\nyear = 2003,\npages = "98-107",\nvolume = 2906,\nurl_Paper = "https://lance.fortnow.com/papers/files/ioauto.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Quantum Property Testing.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; Newman, I.; and Röhrig, H.\n\n\n \n\n\n\n In Proceedings of the Fourteenth ACM-SIAM Symposium on Discrete Algorithms, pages 480-488. ACM, New York, 2003.\n \n\n\n\n
\n\n\n\n \n \n $\"Quantum$ Paper\n \n \n \n $\"Quantum$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{qprop-C,\ntitle = "Quantum Property Testing",\nauthor = "H. Buhrman and L. Fortnow and I. Newman and H. R{\\"{o}}hrig",\npublisher = "ACM",\naddress = "New York",\nbooktitle = soda14,\npages = "480-488",\nyear = 2003,\nurl = "https://portal.acm.org/citation.cfm?id=644108.644188",\nurl_Paper = "https://lance.fortnow.com/papers/files/qprop.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Sublinear approximation of Euclidean minimum spanning tree.\n \n \n \n \n\n\n \n Czumaj, A.; Ergün, F.; Fortnow, L.; Magen, A.; Newman, I.; Rubinfeld, R.; and Sohler, C.\n\n\n \n\n\n\n In Proceedings of the Fourteenth ACM-SIAM Symposium on Discrete Algorithms, pages 813-822. ACM, New York, 2003.\n \n\n\n\n
\n\n\n\n \n \n $\"Sublinear$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{emst-C,\ntitle = "Sublinear approximation of {Euclidean} minimum spanning tree",\nauthor = "Artur Czumaj and Funda Erg{\\"{u}}n and Lance Fortnow and\nAvner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler",\npublisher = "ACM",\naddress = "New York",\nbooktitle = soda14,\npages = "813-822",\nyear = 2003,\nurl_Paper = "https://lance.fortnow.com/papers/files/emst.pdf"}\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n 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 Using Depth to Capture Average-Case Complexity.\n \n \n \n\n\n \n Antunes, L.; Fortnow, L.; and Vinodchandran, V.\n\n\n \n\n\n\n In 14th International Symposium on Fundamentals of Computation Theory, volume 2751, of Lecture Notes in Computer Science, pages 303-310. Springer, Berlin, 2003.\n \n\n\n\n
\n\n\n\n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{depth2-C,\ntitle = "Using Depth to Capture Average-Case Complexity",\nauthor = "L. Antunes and L. Fortnow and V. Vinodchandran",\nbooktitle = fct14,\npublisher= "Springer",\naddress = "Berlin",\nseries = lncs,\nvolume = 2751,\nyear = 2003,\npages = "303-310"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n 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 Some Results on Derandomization.\n \n \n \n \n\n\n \n Buhrman, H.; Fortnow, L.; and Pavan, A.\n\n\n \n\n\n\n In Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science, volume 2607, of Lecture Notes in Computer Science, pages 212-222. Springer, Berlin, 2003.\n \n\n\n\n
\n\n\n\n \n \n $\"Some$ Paper\n \n \n \n $\"Some$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{BF-derand,\ntitle = "Some Results on Derandomization",\nauthor = "H. Buhrman and L. Fortnow and A. Pavan",\nbooktitle = stacs20,\nvolume = 2607,\nseries = lncs,\nyear = 2003,\naddress = "Berlin",\npublisher = springer,\npages = "212-222",\nurl = "https://www.springerlink.com/link.asp?id=3vwf47nau7r108ww",\nurl_Paper = "https://lance.fortnow.com/papers/files/derand.pdf"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n 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 3 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 9 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 5 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 \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 In Proceedings of the 4th ACM Conference on Electronic Commerce, pages 156-165. ACM, New York, 2003.\n \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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{infomarkets,\ntitle = "Computation in a Distributed Information Market",\nauthor = "J. Feigenbaum and L. Fortnow and\nD. Pennock and R. Sami",\nurl = "https://dl.acm.org/authorize?600693",\ndoi = "10.1145/779928.779947",\nyear = 2003,\npages = "156-165",\npublisher = "ACM",\naddress = "New York",\nbooktitle = ec4,\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 In Proceedings of the 4th ACM Conference on Electronic Commerce, pages 144-155. ACM, New York, 2003.\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{logicalsecurities,\ntitle = "Betting {Boolean}-style: A Framework for Trading in\nSecurities Based on Logical Formulas",\nauthor = "L. Fortnow and J. Kilian and D. Pennock and M. Wellman",\nurl = "https://dl.acm.org/authorize?600692",\ndoi = "10.1145/779928.779946",\nyear = 2003,\npages = "144-155",\npublisher = "ACM",\naddress = "New York",\nbooktitle = ec4,\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 \n \n Proving SAT does not have Small Circuits with an Application to the Two Queries Problem.\n \n \n \n \n\n\n \n Fortnow, L.; Pavan, A.; and Sengupta, S.\n\n\n \n\n\n\n In Proceedings of the 18th IEEE Conference on Computational Complexity, pages 347-350. IEEE, New York, 2003.\n \n\n\n\n
\n\n\n\n \n \n $\"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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{satcirc,\ntitle = "Proving {SAT} does not have Small Circuits with\nan Application to the Two Queries Problem",\nauthor = "L. Fortnow and A. Pavan and S. Sengupta",\nurl = "https://dx.doi.org/10.1109/CCC.2003.1214433",\ndoi = "10.1109/CCC.2003.1214433",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict18,\npages = "347-350",\nyear = 2003,\nurl_Paper = "https://lance.fortnow.com/papers/files/2q.pdf"}\n\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Sophistication Revisited.\n \n \n \n \n\n\n \n Antunes, L.; and Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 30th International Colloquium on Automata, Languages and Programming, volume 2719, of Lecture Notes in Computer Science, pages 267-277. Springer, 2003.\n \n\n\n\n
\n\n\n\n \n \n $\"Sophistication$ Paper\n \n \n \n $\"Sophistication$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{soph,\nauthor = "L. Antunes and L. Fortnow",\ntitle = "Sophistication Revisited",\nbooktitle = icalp30,\nyear = 2003,\npublisher = springer,\nseries = lncs,\nurl = "https://www.springerlink.com/link.asp?id=qj45fepf4l5fhv7w",\nurl_Paper = "https://lance.fortnow.com/papers/files/soph.pdf",\nvolume = 2719,\npages = "267-277"}\n\n

\n\n\n\n

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

\n\n

\n \n 2002\n \n \n (8)\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 2 downloads\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 Prediction and Dimension.\n \n \n \n \n\n\n \n Fortnow, L.; and Lutz, J.\n\n\n \n\n\n\n In Proceedings of the Fifteenth Annual Conference on Computational Learning Theory, volume 2375, of Lecture Notes in Computer Science, pages 380-395. Springer, Berlin, 2002.\n \n\n\n\n
\n\n\n\n \n \n $\"Prediction$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{predict-C,\ntitle = "Prediction and Dimension",\nauthor = "L. Fortnow and J. Lutz",\nbooktitle = colt15,\nyear = 2002,\npublisher= "Springer",\naddress = "Berlin",\nseries = lncs,\nvolume = 2375,\nurl_Paper = "https://lance.fortnow.com/papers/files/predict.pdf",\npages = "380-395"}\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 Review of Wegener, \\em Branching Programs and Binary Decision Diagrams: Theory and Applications.\n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n SIAM Review, 44(2): 284-285. 2002.\n \n\n\n\n
\n\n\n\n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{wegenerreview-O,\nauthor = "L. Fortnow",\ntitle = "{Review of\nWegener, {\\em Branching Programs and Binary Decision Diagrams: Theory\nand Applications}}",\njournal = "SIAM Review",\nyear = 2002,\nvolume = 44,\nnumber = 2,\npages = "284-285"}\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 \n \n Nearly Tight Bounds for Private Information Retrieval Systems.\n \n \n \n \n\n\n \n Beigel, R.; Fortnow, L.; and Gasarch, W.\n\n\n \n\n\n\n Technical Report 2002-L001N, NEC Laboratories America, 2002.\n \n\n\n\n
\n\n\n\n \n \n $\"Nearly$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@techreport{pir,\ntitle = "Nearly Tight Bounds for Private Information Retrieval Systems",\nauthor = "R. Beigel and L. Fortnow and W. Gasarch",\ninstitution = neclabs,\nnumber = "2002-L001N",\nyear = 2002,\nurl_Paper = "https://lance.fortnow.com/papers/files/pir.pdf"}\n\n

\n\n\n\n

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

\n\n

\n \n 2001\n \n \n (9)\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 5 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 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 \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-C,\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"}\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 16 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 10 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 (6)\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 10 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 Time-Space Tradeoffs for Nondeterministic Computation.\n \n \n \n \n\n\n \n Fortnow, L.; and van Melkebeek, D.\n\n\n \n\n\n\n In Proceedings of the 15th IEEE Conference on Computational Complexity, pages 2-13. IEEE, New York, 2000.\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

@incollection{tst-C,\nauthor = "L. Fortnow and D. van Melkebeek",\ntitle = "Time-Space Tradeoffs for Nondeterministic Computation",\nurl = "https://dx.doi.org/10.1109/CCC.2001.933869",\ndoi = "10.1109/CCC.2001.933869",\nyear = "2000",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict15,\npages = "2-13",\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 Testing that distributions are close.\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 In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, pages 259-269. IEEE, New York, 2000.\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{closeness-C,\nauthor = "T. Batu and L. Fortnow and R. Rubinfeld\n          and W. D. Smith and P. White",\ntitle = "Testing that distributions are close",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = focs41,\nurl = "https://dx.doi.org/10.1109/SFCS.2000.892113",\ndoi = "10.1109/SFCS.2000.892113",\nyear = 2000,\nurl_Paper = "https://lance.fortnow.com/papers/files/closeness.pdf",\npages = "259-269"}\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 2 downloads\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 (8)\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 12 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 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 In Proceedings of the 5th Annual International Computing and Combinatorics Conference, volume 1627, of Lecture Notes in Computer Science, pages 184-193. Springer, Berlin, 1999.\n \n\n\n\n
\n\n\n\n \n \n $\"Distributionally-Hard$ Paper\n \n \n \n $\"Distributionally-Hard$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{disthard-C,\nauthor = "L. Fortnow and A. Pavan and A. Selman",\nbooktitle = cocoon5,\ntitle = "Distributionally-Hard Languages",\nyear = 1999,\naddress = "Berlin",\nseries = lncs,\npublisher = springer,\nvolume = 1627,\nurl = "https://www.springerlink.com/link.asp?id=gx6yepbytr2p4965",\npages = "184-193",\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 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 Review of Gasarch and Martin, \\em Bounded Queries in Recursion Theory.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n SIGACT News, 30(3): 13-15. 1999.\n \n\n\n\n
\n\n\n\n \n \n $\"Review$ Paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{Gasarchreview-O,\nauthor = "L. Fortnow",\ntitle = "{Review of Gasarch and Martin, {\\em Bounded Queries in\nRecursion Theory}}",\njournal = sigact,\nvolume = 30,\nnumber = 3,\nyear = 1999,\npages = "13-15",\nurl = "https://doi.acm.org/10.1145/333623.1042132"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n Review of Sipser, \\em Introduction to the Theory of Computation.\n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Journal of Symbolic Logic, 64(1): 403. March 1999.\n \n\n\n\n
\n\n\n\n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{sipserr-O,\nauthor = "L. Fortnow",\ntitle = {{Review of Sipser, {\\em Introduction to the Theory of Computation}}},\njournal = jsl,\nvolume = 64,\nnumber = 1,\nmonth = mar,\nyear = 1999,\npages = "403"}\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 3 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 (12)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n One-sided Versus Two-sided Randomness.\n \n \n \n \n\n\n \n Buhrman, H.; and Fortnow, L.\n\n\n \n\n\n\n Technical Report CS 98-05, University of Chicago Department of Computer Science, 1998.\n \n\n\n\n
\n\n\n\n \n \n $\"One-sided$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@techreport{rpvsbpp-U,\nauthor = "H. Buhrman and L. Fortnow",\ntitle = "One-sided Versus Two-sided Randomness",\ninstitution = chics,\nyear = 1998,\nnumber = "CS 98-05",\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 Relativized Worlds with an Infinite Hierarchy.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Technical Report CS 98-03, University of Chicago Department of Computer Science, 1998.\n \n\n\n\n
\n\n\n\n \n \n $\"Relativized$ paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@techreport{sppph-U,\nauthor = {L. Fortnow},\ntitle = "Relativized Worlds with an Infinite Hierarchy",\ninstitution = chics,\nyear = 1998,\nnumber = "CS 98-03",\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 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 In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 202-209. IEEE, New York, 1998.\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{quantum-C,\nauthor = {L. Fortnow and J. Rogers},\n\t\t  title= {Complexity Limitations on Quantum\n\t\t  Computation},\nurl = "https://dx.doi.org/10.1109/CCC.1998.694606",\ndoi = "10.1109/CCC.1998.694606",\n\t\t  year = 1998,\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict13,\n\t\t  pages = {202-209},\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/quantum.pdf}}\n\t\t\n

\n\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 2 downloads\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 Nearly Optimal Language Compression Using Extractors.\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 \n\n\n\n
\n\n\n\n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{extr-C,\nauthor = {L. Fortnow and S. Laplante},\ntitle = {Nearly Optimal Language Compression Using Extractors},\nbooktitle = stacs15,\nyear = 1998,\naddress = "Berlin",\nseries = lncs,\npublisher = springer,\nvolume = 1373,\n\t\t  pages = {84-93}}\n\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 Two Queries.\n \n \n \n \n\n\n \n Buhrman, H.; and Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 13-19. IEEE, New York, 1998.\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{queries-C,\nauthor = {H. Buhrman and L. Fortnow},\ntitle = {Two Queries},\n\t\t  year = 1998,\nurl = "https://dx.doi.org/10.1109/CCC.1998.694586",\ndoi = "10.1109/CCC.1998.694586",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict13,\n\t\t  pages = {13-19},\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 Uniformly Hard Languages.\n \n \n \n \n\n\n \n Downey, R.; and Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 228-233. IEEE, New York, 1998.\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

@incollection{uniform-C,\nauthor = "R. Downey and L. Fortnow",\ntitle = "Uniformly Hard Languages",\n\t\t  year = 1998,\nurl = "https://dx.doi.org/10.1109/CCC.1998.694610",\ndoi = "10.1109/CCC.1998.694610",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict13,\n\t\t  pages = {228-233},\n\t\t  url_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 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 (6)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Nondeterministic Polynomial Time versus Nondeterministic Logartithmic Space: Time-Space Tradeoffs for Satisfiability.\n \n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 12th IEEE Conference on Computational Complexity, pages 52-60. IEEE, New York, 1997.\n \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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{npvsnl-C,\nauthor = {L. Fortnow},\ntitle = {Nondeterministic Polynomial Time versus Nondeterministic\n       Logartithmic Space: Time-Space Tradeoffs for\nSatisfiability},\nurl = "https://dx.doi.org/10.1109/CCC.1997.612300",\ndoi = "10.1109/CCC.1997.612300",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict12,\nyear = 1997,\npages = {52-60},\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 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 5 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 Retraction of 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 twenty-ninth annual ACM symposium on Theory of computing, of STOC '97, pages 750–, New York, NY, USA, 1997. ACM\n \n\n\n\n
\n\n\n\n \n \n $\"Retraction$ 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

@inproceedings{Fortnow:1997:RPC:258533.258677,\n author = {Fortnow, Lance and Sipser, Michael},\n title = {Retraction of probabilistic computation and linear time},\n booktitle = {Proceedings of the twenty-ninth annual ACM symposium on Theory of computing},\n series = {STOC '97},\n year = {1997},\n isbn = {0-89791-888-6},\n location = {El Paso, Texas, United States},\n pages = {750--},\nurl = "https://dl.acm.org/authorize?79202",\n doi = "10.1145/258533.258677",\n acmid = {258677},\n publisher = {ACM},\n address = {New York, NY, USA},\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.; and Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 14th Symposium on Theoretical Aspects of Computer Science, volume 1200, of Lecture Notes in Computer Science, pages 105-116. Springer, Berlin, 1997.\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{BuFo-C,\ntitle = "Resource-Bounded {Kolmogorov} Complexity Revisited",\nauthor = "H. Buhrman and L. Fortnow",\nbooktitle = stacs14,\nyear = 1997,\naddress = {Berlin},\nseries = lncs,\npublisher = springer,\nurl = "https://dx.doi.org/10.1007/BFb0023452",\ndoi = "10.1007/BFb0023452",\nvolume = 1200,\npages = {105-116},\n\t\t  url_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 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 4 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 (10)\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 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 In Proceedings of the 11th IEEE Conference on Computational Complexity, pages 213-222. IEEE, New York, 1996.\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

@incollection{Q-C,\ntitle = "Inverting onto functions",\nauthor = "S. Fenner and L. Fortnow and A. Naik and J. Rogers",\nurl = "https://dx.doi.org/10.1109/CCC.1996.507683",\ndoi = "10.1109/CCC.1996.507683",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict11,\nyear = 1996,\npages = "213-222",\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 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 In Proceedings of the 11th IEEE Conference on Computational Complexity, pages 59-67. IEEE, New York, 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

@incollection{crsra-C,\nauthor = "J. Feigenbaum and L. Fortnow and S. Laplante and A. Naik",\ntitle = "On Coherence, Random-self-reducibility, and Self-correction",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict11,\nurl = "https://dx.doi.org/10.1109/CCC.1996.507668",\ndoi = "10.1109/CCC.1996.507668",\nyear = 1996,\npages = "59-67",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/crsra.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 In Proceedings of the 11th IEEE Conference on Computational Complexity, pages 97-106. IEEE, New York, 1996.\n \n\n\n\n
\n\n\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

@incollection{logprint-C,\nauthor = "L. Fortnow and J. Goldsmith and M. Levy and S. Mahaney",\ntitle = "{L}-Printable sets",\nurl = "https://dx.doi.org/10.1109/CCC.1996.507673",\ndoi = "10.1109/CCC.1996.507673",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict11,\nyear = 1996,\npages = "97-106"}\n\t\t\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 2 downloads\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 \n Easy sets without easy small subsets.\n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 13th Symposium on Theoretical Aspects of Computer Science, of Lecture Notes in Computer Science. Springer, Berlin, 1996.\n Withdrawn.\n\n\n\n
\n\n\n\n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{Fortnow-sparse,\nauthor = "L. Fortnow",\ntitle = "Easy sets without easy small subsets",\npublisher = springer,\nbooktitle = stacs13,\naddress = "Berlin",\nseries = lncs,\nyear = 1996,\nnote = "Withdrawn."}\n\n

\n\n\n\n

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

\n\n

\n \n 1995\n \n \n (7)\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 Easy Sets Without Easy Small Subsets.\n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Technical Report CS 95-07, University of Chicago Department of Computer Science, 1995.\n \n\n\n\n
\n\n\n\n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@techreport{sparse-U,\nauthor = "L. Fortnow",\ntitle = "Easy Sets Without Easy Small Subsets",\ninstitution = chics,\nyear = 1995,\nnumber = "CS 95-07"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Resource-Bounded Instance Complexity.\n \n \n \n \n\n\n \n Fortnow, L.; and Kummer, M.\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 597-609. Springer, Berlin, 1995.\n \n\n\n\n
\n\n\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{instance-C,\nauthor = "L. Fortnow and M. Kummer",\ntitle = "Resource-Bounded Instance Complexity",\nurl = "https://dx.doi.org/10.1007/3-540-59042-0_108",\ndoi = "10.1007/3-540-59042-0_108",\nbooktitle = stacs12,\nyear = 1995,\naddress = "Berlin",\nseries = lncs,\npublisher = springer,\nvolume = 900,\npages = "597-609"}\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 \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-C,\nauthor = "S. Fenner and L. Fortnow",\ntitle = "Beyond {$P^{NP}=NEXP$}",\nbooktitle = stacs12,\nyear = 1995,\naddress = "Berlin",\nseries = lncs,\nvolume = 900,\nurl = "https://dx.doi.org/10.1007/3-540-59042-0_110",\ndoi = "10.1007/3-540-59042-0_110",\npublisher = springer,\npages = "619-627"}\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 \n \n Measure, Category and Learning Theory.\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 In Proceedings of the 22nd International Colloquium on Automata, Languages and Programming, volume 944, of Lecture Notes in Computer Science, pages 558-569. Springer, 1995.\n \n\n\n\n
\n\n\n\n \n \n $\"Measure,$ 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{measure-C,\nauthor = "L. Fortnow and R. Freivalds and W. Gasarch and M. Kummer\n          and S. Kurtz and C. Smith and F. Stephan",\ntitle = "Measure, Category and Learning Theory",\nbooktitle = icalp22,\nyear = 1995,\npublisher = springer,\nseries = lncs,\nurl = "https://dx.doi.org/10.1007/3-540-60084-1_105",\ndoi = "10.1007/3-540-60084-1_105",\nvolume = 944,\npages = "558-569"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n Using autoreducibility to separate complexity classes.\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 36th IEEE Symposium on Foundations of Computer Science, pages 520-527. IEEE, New York, 1995.\n \n\n\n\n
\n\n\n\n \n \n $\"Using$ Paper\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{auto-C,\ntitle = "Using autoreducibility to separate complexity classes",\nauthor = "H. Buhrman and L. Fortnow and L. Torenvliet",\nurl = "https://dx.doi.org/10.1109/SFCS.1995.492582",\ndoi = "10.1109/SFCS.1995.492582",\nbooktitle = focs36,\npublisher = "IEEE",\naddress = "New York",\nyear = 1995,\npages = "520-527",\n\t\t  url_paper = {https://lance.fortnow.com/papers/files/auto.pdf}}\n\n

\n\n\n\n

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

\n\n

\n \n 1994\n \n \n (12)\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 Technical Report CS 94-21, University of Chicago Department of Computer Science, 1994.\n \n\n\n\n
\n\n\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@techreport{bigmatch-O,\nauthor = "L. Fortnow and P. Kimmel",\ntitle = "Beating a finite automaton in the big match",\ninstitution = chics,\nyear = 1994,\nnumber = "CS 94-21",\n\t\t  url_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 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 1 download\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 8 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 2 downloads\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 8 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 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 In Proceedings of the 5th Annual International Symposium on Algorithms and Computation, volume 834, of Lecture Notes in Computer Science, pages 396-404. Springer, Berlin, 1994.\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{FoRo-C,\nauthor = "L. Fortnow and J. Rogers",\ntitle = "Separability and One-Way Functions",\nbooktitle = isaac5,\nyear = 1994,\naddress = "Berlin",\nseries = lncs,\npublisher = springer,\nurl = "https://dx.doi.org/10.1007/3-540-58325-4_204",\ndoi = "10.1007/3-540-58325-4_204",\nvolume = 834,\npages = "396-404",\n\t\t  url_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 \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 \n \n Generic Separations.\n \n \n \n \n\n\n \n Fortnow, L.; and Yamakami, T.\n\n\n \n\n\n\n In Proceedings of the 9th IEEE Structure in Complexity Theory Conference, pages 139-145. IEEE, New York, 1994.\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{FY-C,\nauthor = "L. Fortnow and T. Yamakami",\ntitle = "Generic Separations",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict9,\nurl = "https://dx.doi.org/10.1109/SCT.1994.315809",\ndoi = "10.1109/SCT.1994.315809",\nYEAR = "1994",\npages = "139-145",\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 1993\n \n \n (5)\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 2 downloads\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 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 In Proceedings of the 8th IEEE Structure in Complexity Theory Conference, pages 120-131. IEEE, New York, 1993.\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{FFKL-C,\nauthor = "Fenner, S. and L. Fortnow and S. Kurtz and L. Li",\ntitle = "An Oracle Builder's Toolkit",\npublisher = "IEEE",\naddress = "New York",\nurl = "https://dx.doi.org/10.1109/SCT.1993.336534",\ndoi = "10.1109/SCT.1993.336534",\nbooktitle = sict8,\nyear = 1993,\npages = "120-131",\n\t\t  url_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 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 \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 In Proceedings of the 10th Symposium on Theoretical Aspects of Computer Science, volume 665, of Lecture Notes in Computer Science, pages 484-493. Springer, Berlin, 1993.\n \n\n\n\n
\n\n\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{FFL-C,\nauthor = "S. Fenner and L. Fortnow and L. Li",\ntitle = "Gap-Definability as a Closure Property",\nbooktitle = stacs10,\nurl = "https://dx.doi.org/10.1007/3-540-56503-5_48",\ndoi = "10.1007/3-540-56503-5_48",\nyear = 1993,\npages = "484-493",\nvolume = 665,\naddress = "Berlin",\nseries = lncs,\npublisher = springer}\n\n

\n\n\n\n

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

\n\n

\n \n 1992\n \n \n (5)\n \n \n

\n \n \n

\n \n\n \n \n \n \n \n \n Degrees of Inferability.\n \n \n \n \n\n\n \n Cholak, P.; Downey, R.; Fortnow, L.; Gasarch, W.; Kinber, E.; Kummer, M.; Kurtz, S.; and Slaman, T.\n\n\n \n\n\n\n In Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, pages 180-192. ACM, New York, 1992.\n \n\n\n\n
\n\n\n\n \n \n $\"Degrees$ 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{infer-C,\nauthor = "P. Cholak and R. Downey and L. Fortnow and W. Gasarch\n          and E. Kinber and M. Kummer and S. Kurtz and T. Slaman",\ntitle = "Degrees of Inferability",\npublisher = "ACM",\nurl = "https://dl.acm.org/authorize?87884",\ndoi = "10.1145/130385.130406",\naddress = "New York",\nbooktitle = colt5,\nyear = 1992,\npages = "180-192"}\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 In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages 30-39. IEEE, New York, 1992.\n \n\n\n\n
\n\n\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

@incollection{FFK2-C,\nauthor = "Fenner, S. and L. Fortnow and S. Kurtz",\ntitle = "The isomorphism conjecture holds relative to an oracle",\npublisher = "IEEE",\naddress = "New York",\nurl = "https://dx.doi.org/10.1109/SFCS.1992.267821",\ndoi = "10.1109/SFCS.1992.267821",\nbooktitle = focs33,\nyear = 1992,\npages = "30-39"}\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 In Proceedings of the 7th IEEE Structure in Complexity Theory Conference, pages 338-346. IEEE, New York, 1992.\n \n\n\n\n
\n\n\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

@INCOLLECTION{FFLS-C,\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",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict7,\nurl = "https://dx.doi.org/10.1109/SCT.1992.215408",\ndoi = "10.1109/SCT.1992.215408",\nyear = 1992,\npages = "338-346"}\n\n

\n\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 4 downloads\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 (10)\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 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 In Proceedings of the 6th IEEE Structure in Complexity Theory Conference, pages 213-219. IEEE, New York, 1991.\n \n\n\n\n
\n\n\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{BFNW-C,\nauthor = "L. Babai and L. Fortnow and N. Nisan and A. Wigderson",\ntitle = "{BPP} has subexponential simulations unless {EXPTIME}\n         has publishable proofs",\npublisher = "IEEE",\naddress = "New York",\nurl = "https://dx.doi.org/10.1109/SCT.1991.160263",\ndoi = "10.1109/SCT.1991.160263",\nbooktitle = sict6,\nyear = 1991,\npages = "213-219"}\n\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 7 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 \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 In Proceedings of the 6th IEEE Structure in Complexity Theory Conference, pages 124-132. IEEE, New York, 1991.\n \n\n\n\n
\n\n\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

@INCOLLECTION{FF-C,\nauthor = "Feigenbaum, J. and L. Fortnow",\ntitle = "On the Random-Self-Reducibility of Complete Sets",\nurl = "https://dx.doi.org/10.1109/SCT.1991.160252",\ndoi = "10.1109/SCT.1991.160252",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict6,\nyear = 1991,\npages = "124-132"\n}\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 In Proceedings of the 6th IEEE Structure in Complexity Theory Conference, pages 30-42. IEEE, New York, 1991.\n \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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@INCOLLECTION{FFK-C,\nauthor = "Fenner, S. and L. Fortnow and S. Kurtz",\ntitle = "Gap-Definable Counting Classes",\nurl = "https://dx.doi.org/10.1109/SCT.1991.160241",\ndoi = "10.1109/SCT.1991.160241",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict6,\nyear = 1991,\npages = "30-42",\n\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 Review of Goldwasser, Micali and Rackoff, ``The Knowledge Complexity of Interactive Proof Systems'', Goldreich, Micali and Wigderson, ``Proofs that Release Minimum Knowledge'' and Goldreich, ``Randomness, Interactive Proofs and Zero-Knowledge''.\n \n \n \n\n\n \n Fortnow, L.\n\n\n \n\n\n\n Journal of Symbolic Logic, 56(3): 1092-1094. 1991.\n \n\n\n\n
\n\n\n\n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@article{ipr-O,\nauthor = "L. Fortnow",\ntitle = {{Review of Goldwasser, Micali and Rackoff, ``The Knowledge\nComplexity of Interactive Proof Systems'', Goldreich, Micali and\nWigderson, ``Proofs that Release Minimum Knowledge'' and Goldreich,\n``Randomness, Interactive Proofs and Zero-Knowledge''}},\njournal = jsl,\nvolume = 56,\nnumber = 3,\nyear = 1991,\npages = "1092-1094"}\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 In Proceedings of the 8th Symposium on Theoretical Aspects of Computer Science, volume 480, of Lecture Notes in Computer Science, pages 263-274. Springer, Berlin, 1991.\n \n\n\n\n
\n\n\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{FL-C,\nAUTHOR = "Fortnow, L. and C. Lund",\nTITLE = "Interactive Proof Systems and Alternating Time-Space Complexity",\nbooktitle = stacs8,\nyear = 1991,\npages = "263-274",\nvolume = 480,\nurl = "https://dx.doi.org/10.1007/BFb0020804",\ndoi = "10.1007/BFb0020804",\naddress = "Berlin",\nseries = lncs,\npublisher = springer}\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 In Proceedings of the 6th IEEE Structure in Complexity Theory Conference, pages 13-15. IEEE, New York, 1991.\n \n\n\n\n
\n\n\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{FR-C,\nauthor = "L. Fortnow and N. Reingold",\ntitle = "{PP} is Closed Under Truth-Table Reductions",\nurl = "https://dx.doi.org/10.1109/SCT.1991.160239",\ndoi = "10.1109/SCT.1991.160239",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = sict6,\nyear = 1991,\npages = "13-15"}\n\n

\n\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 In Proceedings of ASIACRYPT '91: International Conference on the Theory and Application of Cryptology, volume 739, of Lecture Notes in Computer Science, pages 345-351. Springer, 1991.\n \n\n\n\n
\n\n\n\n \n \n $\"On$ Paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{FSz-C,\nauthor = "L. Fortnow and M. Szegedy",\ntitle = "On the power of two-local random reductions",\npublisher = springer,\nseries = lncs,\nbooktitle = "Proceedings of ASIACRYPT '91: International Conference on the Theory and Application of Cryptology",\nyear = 1991,\nvolume = 739,\npages = "345-351",\nurl = "https://dx.doi.org/10.1007/3-540-57332-1_29"}\n

\n\n\n\n

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

\n\n

\n \n 1990\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 In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pages 16-25. IEEE, New York, 1990.\n 2020 FOCS Test of Time Award\n\n\n\n
\n\n\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{BFL-C,\nAUTHOR = "Babai, L. and L. Fortnow and C. Lund",\nTITLE = "Nondeterministic Exponential Time has Two-Prover Interactive\nProtocols",\npublisher = "IEEE",\nurl = "https://dx.doi.org/10.1109/FSCS.1990.89520",\ndoi = "10.1109/FSCS.1990.89520",\naddress = "New York",\nbooktitle = focs31,\nyear = 1990,\nnote = "2020 FOCS Test of Time Award",\npages = "16-25"}\n\n

\n\n\n\n

\n\n\n

\n \n\n \n \n \n \n \n \n A Characterization of $#$P by Arithmetic Straight Line Programs.\n \n \n \n \n\n\n \n Babai, L.; and Fortnow, L.\n\n\n \n\n\n\n In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pages 26-34. IEEE, New York, 1990.\n \n\n\n\n
\n\n\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

@incollection{BaFo-C,\nAUTHOR = "Babai, L. and L. Fortnow",\nTITLE = "A Characterization of {$\\#$P} by Arithmetic Straight Line Programs",\nurl = "https://dx.doi.org/10.1109/FSCS.1990.89521",\ndoi = "10.1109/FSCS.1990.89521",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = focs31,\nyear = 1990,\npages = "26-34"}\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 In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pages 2-9. IEEE, New York, 1990.\n FOCS 2020 Test of Time Award\n\n\n\n
\n\n\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 \n \n \n \n \n \n\n \n \n \n\n\n\n

@incollection{LFKN-C,\nAUTHOR = "Lund, C. and Fortnow, L. and Karloff, H. and Nisan, N.",\nTITLE = "Algebraic Methods for Interactive Proof Systems",\nurl = "https://dx.doi.org/10.1109/FSCS.1990.89518",\ndoi = "10.1109/FSCS.1990.89518",\npublisher = "IEEE",\naddress = "New York",\nbooktitle = focs31,\nyear = 1990,\nnote = "FOCS 2020 Test of Time Award",\npages = "2-9"}\n\n

\n\n\n\n

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

\n\n

\n \n 1989\n \n \n (4)\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 9 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 \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

@incollection{Fo-J,\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}}\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 2 downloads\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 5 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 (2)\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 In Proceedings of the 3rd IEEE Structure in Complexity Theory Conference, pages 156–161. IEEE, New York, 1988.\n \n\n\n\n
\n\n\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

@INCOLLECTION{FRS-C,\nAUTHOR = "Fortnow, L. and J. Rompel and M. Sipser",\nTITLE = "On the Power of Multi-Prover Interactive Protocols",\npublisher = "IEEE",\naddress = "New York",\nurl = "https://dx.doi.org/10.1109/SCT.1988.5275",\ndoi = "10.1109/SCT.1988.5275",\nbooktitle = sict3,\nYEAR = "1988",\nPAGES = "156--161" }\n\n

\n\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 8 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 1987\n \n \n (1)\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 Proceedings of the 19th ACM Symposium on the Theory of Computing, pages 204-209. ACM, New York, 1987.\n \n\n\n\n
\n\n\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

@incollection{Fo-C,\nAUTHOR = "Fortnow, L.",\nTITLE = "The Complexity of Perfect Zero-Knowledge",\nurl = "https://dl.acm.org/authorize?77151",\ndoi = "10.1145/28395.28418",\npublisher = "ACM",\naddress = "New York",\nbooktitle = stoc19,\nYEAR = "1987",\npages = "204-209"}\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\n