Lance Fortnow - RankMe

237 papers A* 34A 39B 10C 2Misc 3Journal 119Unranked 24

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Accelerating Scientific Research with Gemini: Case Studies and Common Techniques. CoRR David P. Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, MohammadHossein Bateni, Simina Brânzei, Michael P. Brenner, Lin Chen, Ying Feng, Lance Fortnow, Gang Fu, Ziyi Guan, Zahra Hadizadeh, Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Adel Javanmard, Karthik C. S., Ken-ichi Kawarabayashi, Ravi Kumar, Silvio Lattanzi, Euiwoong Lee, Yi Li, Ioannis Panageas, Dimitris Paparas, Benjamin Przybocki, Bernardo Subercaseaux, Ola Svensson, Shayan Taherijam, Xuan Wu, Eylon Yogev, Morteza Zadimoghaddam, Samson Zhou, Yossi Matias, James Manyika, Vahab Mirrokni
2025	J	`jnl`	Search versus Decision for S CoRR Lance Fortnow
2022	J	`jnl`	Computational Complexity. Bull. EATCS Lance Fortnow
2022	J	`jnl`	Fifty years of P vs. NP and the possibility of the impossible. Commun. ACM Lance Fortnow
2021	J	`jnl`	Worlds to Die Harder For Open Oracle Questions for the 21st Century. SIGACT News Lance Fortnow
2020	J	`jnl`	Matrix Multiplication and Binary Space Partitioning Trees : An Exploration. CoRR C. N. P. Slagle, Lance Fortnow
2018	B	`conf`	2-Hop Eclipse: A Fast Algorithm for Bandwidth-Efficient Data Center Switching. CLOUD Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow
2018	—	`conf`	Best First Fit (BFF): An Approach to Partially Reconfigurable Hybrid Circuit and Packet Switching. IEEE CLOUD Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow
2018	Misc	`conf`	Quantized BvND: A Better Solution for Optical and Hybrid Switching in Data Center Networks. UCC Liang Liu, Jun (Jim) Xu, Lance Fortnow
2017	J	`jnl`	Better Algorithms for Hybrid Circuit and Packet Switching in Data Centers. CoRR Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow
2017	—	`conf`	Complexity with Rod. Computability and Complexity Lance Fortnow
2017	J	`jnl`	Compression Complexity. CoRR Stephen A. Fenner, Lance Fortnow
2017	J	`jnl`	Robust simulations and significant separations. Inf. Comput. Lance Fortnow, Rahul Santhanam
2016	J	`jnl`	David Stifler Johnson: A Tribute by Lance Fortnow. Bull. EATCS Lance Fortnow
2016	A*	`conf`	Freestyle Dancing: Randomized Algorithms for Dynamic Storage Load-Balancing. SIGMETRICS Liang Liu, Yating Wang, Lance Fortnow, Jin Li, Jun (Jim) Xu
2016	A	`conf`	New Non-Uniform Lower Bounds for Uniform Classes. CCC Lance Fortnow, Rahul Santhanam
2016	—	`conf`	Randomized Algorithms for Dynamic Storage Load-Balancing. SoCC Liang Liu, Lance Fortnow, Jin Li, Yating Wang, Jun (Jim) Xu
2016	J	`jnl`	The Golden Ticket P, NP, and the Search for the Impossible. Bull. EATCS Lance Fortnow
2015	C	`conf`	Nondeterministic Separations. TAMC Lance Fortnow
2014	—	`ch.`	Computational Complexity. Computational Logic Lance Fortnow, Steven Homer
2014	J	`jnl`	Hierarchies Against Sublinear Advice. Electron. Colloquium Comput. Complex. Lance Fortnow, Rahul Santhanam
2013	C	`conf`	A Personal View of the P versus NP Problem. CiE Lance Fortnow
2013	B	`conf`	Learning Reductions to Sparse Sets. MFCS Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff
2013	J	`jnl`	Testing Closeness of Discrete Distributions. J. ACM Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
2013	—	`book`	The Golden Ticket - P, NP, and the Search for the Impossible. Lance Fortnow
2012	J	`jnl`	Inseparability and Strong Hypotheses for Disjoint NP Pairs. Theory Comput. Syst. Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
2012	J	`jnl`	Low-Depth Witnesses are Easy to Find. Comput. Complex. Luis Filipe Coelho Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
2012	J	`jnl`	Multi-outcome and Multidimensional Market Scoring Rules CoRR Lance Fortnow, Rahul Sami
2012	J	`jnl`	The Enduring Legacy of the Turing Machine. Comput. J. Lance Fortnow
2011	J	`jnl`	Complexity classes of equivalence problems revisited. Inf. Comput. Lance Fortnow, Joshua A. Grochow
2011	J	`jnl`	Extracting Kolmogorov complexity with applications to dimension zero-one laws. Inf. Comput. Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang
2011	J	`jnl`	Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. Lance Fortnow, Rahul Santhanam
2011	A*	`ed.`	Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011 STOC Lance Fortnow, Salil P. Vadhan
2011	J	`jnl`	Repeated Matching Pennies with Limited Randomness CoRR Michele Budinich, Lance Fortnow
2011	A*	`conf`	Repeated matching pennies with limited randomness. EC Michele Budinich, Lance Fortnow
2011	—	`conf`	Robust Simulations and Significant Separations. ICALP (1) Lance Fortnow, Rahul Santhanam
2010	A	`conf`	Bounding Rationality by Discounting Time. ICS Lance Fortnow, Rahul Santhanam
2010	A	`conf`	Derandomizing from Random Strings. CCC Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
2010	J	`jnl`	Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
2010	J	`jnl`	Gaming Prediction Markets: Equilibrium Strategies with a Market Maker. Algorithmica Yiling Chen, Stanko Dimitrov, Rahul Sami, Daniel M. Reeves, David M. Pennock, Robin D. Hanson, Lance Fortnow, Rica Gonen
2010	A	`conf`	Inseparability and Strong Hypotheses for Disjoint NP Pairs. STACS Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
2010	J	`jnl`	Robust Simulations and Significant Separations CoRR Lance Fortnow, Rahul Santhanam
2010	J	`jnl`	Testing Closeness of Discrete Distributions CoRR Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
2010	J	`jnl`	Ubiquity symposium 'What is computation?': The enduring legacy of the Turing machine. Ubiquity Lance Fortnow
2009	—	`conf`	09421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans
2009	—	`conf`	09421 Executive Summary - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans
2009	J	`jnl`	A Simple Proof of Toda's Theorem. Theory Comput. Lance Fortnow
2009	B	`conf`	A computational theory of awareness and decision making. TARK Nikhil R. Devanur, Lance Fortnow
2009	—	`ed.`	Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009 Algebraic Methods in Computational Complexity Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans
2009	J	`jnl`	Bounding Rationality by Discounting Time CoRR Lance Fortnow, Rahul Santhanam
2009	J	`jnl`	Complexity Classes of Equivalence Problems Revisited CoRR Lance Fortnow, Joshua A. Grochow
2009	J	`jnl`	Derandomizing from Random Strings CoRR Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
2009	J	`jnl`	Editor's Foreword. ACM Trans. Comput. Theory Lance Fortnow
2009	J	`jnl`	Efficient learning algorithms yield circuit lower bounds. J. Comput. Syst. Sci. Lance Fortnow, Adam R. Klivans
2009	A	`conf`	Fixed-Polynomial Size Circuit Bounds. CCC Lance Fortnow, Rahul Santhanam, Ryan Williams
2009	A*	`ed.`	Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6--10, 2009 EC John Chuang, Lance Fortnow, Pearl Pu
2009	B	`conf`	Program equilibria and discounted computation time. TARK Lance Fortnow
2009	J	`jnl`	Sophistication Revisited. Theory Comput. Syst. Luis Filipe Coelho Antunes, Lance Fortnow
2009	J	`jnl`	The status of the P versus NP problem. Commun. ACM Lance Fortnow
2009	—	`conf`	Unconditional Lower Bounds against Advice. Algebraic Methods in Computational Complexity Harry Buhrman, Lance Fortnow, Rahul Santhanam
2009	—	`conf`	Unconditional Lower Bounds against Advice. ICALP (1) Harry Buhrman, Lance Fortnow, Rahul Santhanam
2009	J	`jnl`	Unconditional Lower Bounds against Advice. Electron. Colloquium Comput. Complex. Harry Buhrman, Lance Fortnow, Rahul Santhanam
2009	J	`jnl`	Viewpoint - Time for computer science to grow up. Commun. ACM Lance Fortnow
2009	A	`conf`	Worst-Case Running Times for Average-Case Algorithms. CCC Luis Filipe Coelho Antunes, Lance Fortnow
2008	J	`jnl`	A Computational Theory of Awareness and Decision Making. Electron. Colloquium Comput. Complex. Nikhil R. Devanur, Lance Fortnow
2008	—	`ed.`	Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007 Algebraic Methods in Computational Complexity Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
2008	J	`jnl`	Complexity of Combinatorial Market Makers CoRR Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman
2008	A*	`conf`	Complexity of combinatorial market makers. EC Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman
2008	A*	`conf`	Infeasibility of instance compression and succinct PCPs for NP. STOC Lance Fortnow, Rahul Santhanam
2008	J	`jnl`	On the Complexity of Succinct Zero-Sum Games. Comput. Complex. Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
2008	A*	`ed.`	Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008 EC Lance Fortnow, John Riedl, Tuomas Sandholm
2008	J	`jnl`	Proving SAT does not have small circuits with an application to the two queries problem. J. Comput. Syst. Sci. Lance Fortnow, Aduri Pavan, Samik Sengupta
2008	J	`jnl`	Quantum Property Testing. SIAM J. Comput. Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
2008	J	`jnl`	The complexity of forecast testing. SIGecom Exch. Lance Fortnow, Rakesh V. Vohra
2008	A*	`conf`	The complexity of forecast testing: abstract. EC Lance Fortnow, Rakesh Vohra
2007	—	`conf`	07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
2007	—	`conf`	07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
2007	A*	`conf`	Betting on permutations. EC Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock
2007	—	`conf`	Bluffing and Strategic Reticence in Prediction Markets. WINE Yiling Chen, Daniel M. Reeves, David M. Pennock, Robin D. Hanson, Lance Fortnow, Rica Gonen
2007	J	`jnl`	Combinatorial betting. SIGecom Exch. Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock
2007	J	`jnl`	Infeasibility of Instance Compression and Succinct PCPs for NP. Electron. Colloquium Comput. Complex. Lance Fortnow, Rahul Santhanam
2007	Misc	`conf`	Inverting Onto Functions and Polynomial Hierarchy. CSR Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
2007	A	`conf`	Low-Depth Witnesses are Easy to Find. CCC Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
2007	J	`jnl`	Time Hierarchies: A Survey. Electron. Colloquium Comput. Complex. Lance Fortnow, Rahul Santhanam
2006	J	`jnl`	A tight lower bound for restricted pir protocols. Comput. Complex. Richard Beigel, Lance Fortnow, William I. Gasarch
2006	J	`jnl`	Computational depth: Concept and applications. Theor. Comput. Sci. Luis Antunes, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran
2006	A*	`conf`	Efficient Learning Algorithms Yield Circuit Lower Bounds. COLT Lance Fortnow, Adam R. Klivans
2006	J	`jnl`	Enumerations of the Kolmogorov function. J. Symb. Log. Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet
2006	—	`conf`	Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. ICALP (1) Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang
2006	J	`jnl`	Fixed-Polynomial Size Circuit Bounds. Electron. Colloquium Comput. Complex. Lance Fortnow, Rahul Santhanam
2006	J	`jnl`	Infinitely-Often Autoreducible Sets. SIAM J. Comput. Richard Beigel, Lance Fortnow, Frank Stephan
2006	J	`jnl`	Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
2006	A	`conf`	Kolmogorov Complexity with Error. STACS Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
2006	A	`conf`	Linear Advice for Randomized Logarithmic Space. STACS Lance Fortnow, Adam R. Klivans
2006	J	`jnl`	Low-Depth Witnesses are Easy to Find. Electron. Colloquium Comput. Complex. Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
2006	J	`jnl`	The Complexity of Forecast Testing. Electron. Colloquium Comput. Complex. Lance Fortnow, Rakesh Vohra
2006	J	`jnl`	Tolerant Versus Intolerant Testing for Boolean Properties. Theory Comput. Eldar Fischer, Lance Fortnow
2006	B	`conf`	Very Sparse Leaf Languages. MFCS Lance Fortnow, Mitsunori Ogihara
2005	—	`ed.`	Algebraic Methods in Computational Complexity, 10.-15. October 2004 Algebraic Methods in Computational Complexity Harry Buhrman, Lance Fortnow, Thomas Thierauf
2005	J	`jnl`	Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. SIAM J. Comput. Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler
2005	J	`jnl`	Betting Boolean-style: a framework for trading in securities based on logical formulas. Decis. Support Syst. Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman
2005	A*	`conf`	Beyond NP: the work and legacy of Larry Stockmeyer. STOC Lance Fortnow
2005	J	`jnl`	Computation in a distributed information market. Theor. Comput. Sci. Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami
2005	J	`jnl`	Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws Electron. Colloquium Comput. Complex. Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang
2005	A*	`conf`	Hierarchies for semantic classes. STOC Lance Fortnow, Rahul Santhanam, Luca Trevisan
2005	A	`conf`	Increasing Kolmogorov Complexity. STACS Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
2005	J	`jnl`	Linear Advice for Randomized Logarithmic Space Electron. Colloquium Comput. Complex. Lance Fortnow, Adam R. Klivans
2005	A	`conf`	NP with Small Advice. CCC Lance Fortnow, Adam R. Klivans
2005	A	`conf`	On the Complexity of Succinct Zero-Sum Games. CCC Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
2005	J	`jnl`	Prediction and dimension. J. Comput. Syst. Sci. Lance Fortnow, Jack H. Lutz
2005	J	`jnl`	Some Results on Derandomization. Theory Comput. Syst. Harry Buhrman, Lance Fortnow, Aduri Pavan
2005	J	`jnl`	Time-Bounded Universal Distributions Electron. Colloquium Comput. Complex. Lance Fortnow, Luis Antunes
2005	J	`jnl`	Time-space lower bounds for satisfiability. J. ACM Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas
2005	A	`conf`	Tolerant Versus Intolerant Testing for Boolean Properties. CCC Eldar Fischer, Lance Fortnow
2004	—	`conf`	04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Harry Buhrman, Lance Fortnow, Thomas Thierauf
2004	J	`jnl`	Enumerations of the Kolmogorov Function Electron. Colloquium Comput. Complex. Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrei A. Muchnik, Frank Stephan, Leen Torenvliet
2004	A*	`conf`	Hierarchy Theorems for Probabilistic Polynomial Time. FOCS Lance Fortnow, Rahul Santhanam
2004	J	`jnl`	Increasing Kolmogorov Complexity Electron. Colloquium Comput. Complex. Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
2004	J	`jnl`	Kolmogorov Complexity with Error Electron. Colloquium Comput. Complex. Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
2004	J	`jnl`	NP with Small Advice Electron. Colloquium Comput. Complex. Lance Fortnow, Adam R. Klivans
2004	J	`jnl`	On the complexity of succinct zero-sum games Electron. Colloquium Comput. Complex. Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
2004	J	`jnl`	Promise Hierarchies Electron. Colloquium Comput. Complex. Lance Fortnow, Rahul Santhanam, Luca Trevisan
2004	J	`jnl`	Review of "Theory of semi-feasible algorithms" by Lane Hemaspaandra and Leen Torenvliet. Springer. SIGACT News Lance Fortnow
2004	J	`jnl`	Tolerant Versus Intolerant Testing for Boolean Properties Electron. Colloquium Comput. Complex. Eldar Fischer, Lance Fortnow
2003	J	`jnl`	A Nearly Tight Bound for Private Information Retrieval Protocols Electron. Colloquium Comput. Complex. Richard Beigel, Lance Fortnow, William I. Gasarch
2003	J	`jnl`	A Short History of Computational Complexity. Bull. EATCS Lance Fortnow, Steven Homer
2003	J	`jnl`	An oracle builder's toolkit. Inf. Comput. Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li
2003	A	`conf`	Are Cook and Karp Ever the Same? CCC Richard Beigel, Lance Fortnow
2003	A*	`conf`	Betting boolean-style: a framework for trading in securities based on logical formulas. EC Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman
2003	A*	`conf`	Computation in a distributed information market. EC Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami
2003	B	`conf`	Infinitely-Often Autoreducible Sets. ISAAC Richard Beigel, Lance Fortnow, Frank Stephan
2003	J	`jnl`	Inverting onto functions. Inf. Comput. Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers
2003	A	`conf`	One Bit of Advice. STACS Harry Buhrman, Richard Chang, Lance Fortnow
2003	J	`jnl`	One complexity theorist's view of quantum computing. Theor. Comput. Sci. Lance Fortnow
2003	A	`conf`	Proving SAT does not have Small Circuits with an Application to the Two. CCC Lance Fortnow, Aduri Pavan, Samik Sengupta
2003	A*	`conf`	Quantum property testing. SODA Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
2003	A	`conf`	Some Results on Derandomization. STACS Harry Buhrman, Lance Fortnow, Aduri Pavan
2003	A*	`conf`	Sophistication Revisited. ICALP Luis Antunes, Lance Fortnow
2003	A*	`conf`	Sublinear-time approximation of Euclidean minimum spanning tree. SODA Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler
2003	J	`jnl`	Uniformly hard languages. Theor. Comput. Sci. Rodney G. Downey, Lance Fortnow
2003	B	`conf`	Using Depth to Capture Average-Case Complexity. FCT Luis Antunes, Lance Fortnow, N. V. Vinodchandran
2002	A*	`conf`	Prediction and Dimension. COLT Lance Fortnow, Jack H. Lutz
2002	J	`jnl`	Separability and one-way functions. Comput. Complex. Lance Fortnow, John D. Rogers
2002	A	`conf`	The History of Complexity. CCC Lance Fortnow
2001	B	`conf`	An optimal procedure for gap closing in whole genome shotgun sequencing. RECOMB Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, Lance Fortnow
2001	A	`conf`	Comparing Notions of Full Derandomization. CCC Lance Fortnow
2001	A	`conf`	Computational Depth. CCC Luis Antunes, Lance Fortnow, Dieter van Melkebeek
2001	—	`ch.`	Diagonalization. Current Trends in Theoretical Computer Science Lance Fortnow
2001	J	`jnl`	Distributionally Hard Languages. Theory Comput. Syst. Lance Fortnow, Aduri Pavan, Alan L. Selman
2001	J	`jnl`	Guest Editor's Foreword. J. Comput. Syst. Sci. Lance Fortnow
2001	J	`jnl`	Resource-Bounded Kolmogorov Complexity Revisited. SIAM J. Comput. Harry Buhrman, Lance Fortnow, Sophie Laplante
2001	A*	`conf`	Testing Random Variables for Independence and Identity. FOCS Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White
2001	J	`jnl`	Two oracles that force a big crunch. Comput. Complex. Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Leen Torenvliet
2000	J	`jnl`	Diagonalization. Bull. EATCS Lance Fortnow
2000	J	`jnl`	One Complexity Theorist's View of Quantum Computing CoRR Lance Fortnow
2000	—	`conf`	One complexity theorist's view of quantum computing. CATS Lance Fortnow
2000	A	`conf`	Optimal Proof Systems and Sparse Sets. STACS Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek
2000	J	`jnl`	Separating Complexity Classes Using Autoreducibility. SIAM J. Comput. Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet
2000	A*	`conf`	Testing that distributions are close. FOCS Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
2000	J	`jnl`	Time-Space Tradeoffs for Nondeterministic Computation Electron. Colloquium Comput. Complex. Lance Fortnow, Dieter van Melkebeek
2000	A	`conf`	Time-Space Tradeoffs for Nondeterministic Computation. CCC Lance Fortnow, Dieter van Melkebeek
2000	J	`jnl`	Time-Space Tradeoffs for Satisfiability. J. Comput. Syst. Sci. Lance Fortnow
1999	J	`jnl`	Book review: of Bounded Queries in Recursion Theory by William A. Gasarch and Georgia A. Martin (Birkhauser. Boston, Basel, Berlin, 1999). SIGACT News Lance Fortnow
1999	J	`jnl`	Complexity Limitations on Quantum Computation. J. Comput. Syst. Sci. Lance Fortnow, John D. Rogers
1999	Misc	`conf`	Distributionally-Hard Languages. COCOON Lance Fortnow, Aduri Pavan, Alan L. Selman
1999	A	`conf`	One-sided Versus Two-sided Error in Probabilistic Computation. STACS Harry Buhrman, Lance Fortnow
1999	J	`jnl`	Relativized Worlds with an Infinite Hierarchy. Inf. Process. Lett. Lance Fortnow
1999	J	`jnl`	Two Queries. J. Comput. Syst. Sci. Harry Buhrman, Lance Fortnow
1998	B	`conf`	Beating a Finite Automaton in the Big Match. TARK Lance Fortnow, Peter G. Kimmel
1998	A	`conf`	Complexity Limitations on Quantum Computation. CCC Lance Fortnow, John D. Rogers
1998	J	`jnl`	Complexity limitations on quantum computation CoRR Lance Fortnow, John D. Rogers
1998	J	`jnl`	L-Printable Sets. SIAM J. Comput. Lance Fortnow, Judy Goldsmith, Matthew A. Levy, Stephen R. Mahaney
1998	A*	`conf`	NP Might Not Be As Easy As Detecting Unique Solutions. STOC Richard Beigel, Harry Buhrman, Lance Fortnow
1998	A	`conf`	Nearly Optimal Language Compression Using Extractors. STACS Lance Fortnow, Sophie Laplante
1998	A	`conf`	Nonrelativizing Separations. CCC Harry Buhrman, Lance Fortnow, Thomas Thierauf
1998	J	`jnl`	On Coherence, Random-Self-Reducibility, and Self-Correction. Comput. Complex. Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik
1998	J	`jnl`	On the Relative Sizes of Learnable Sets. Theor. Comput. Sci. Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan
1998	A	`conf`	Two Queries. CCC Harry Buhrman, Lance Fortnow
1998	A	`conf`	Uniformly Hard Languages. CCC Rodney G. Downey, Lance Fortnow
1997	A	`conf`	Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability. CCC Lance Fortnow
1997	A	`conf`	Resource-Bounded Kolmogorov Complexity Revisited. STACS Harry Buhrman, Lance Fortnow
1997	A*	`conf`	Results on Resource-Bounded Measure. ICALP Harry Buhrman, Stephen A. Fenner, Lance Fortnow
1997	A*	`conf`	Retraction of Probabilistic Computation and Linear Time. STOC Lance Fortnow, Michael Sipser
1997	A	`conf`	Six Hypotheses in Search of a Theorem. CCC Harry Buhrman, Lance Fortnow, Leen Torenvliet
1996	J	`jnl`	Complexity Theory Newsflash. SIGACT News Stephen A. Fenner, Lance Fortnow, William I. Gasarch
1996	J	`jnl`	Gap-Definability as a Closure Property. Inf. Comput. Stephen A. Fenner, Lance Fortnow, Lide Li
1996	J	`jnl`	Generic Separations. J. Comput. Syst. Sci. Lance Fortnow, Tomoyuki Yamakami
1996	A	`conf`	Inverting Onto Functions. CCC Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers
1996	A	`conf`	L-Printable Sets. CCC Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney
1996	A	`conf`	On Coherence, Random-self-reducibility, and Self-correction. CCC Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik
1996	J	`jnl`	On Resource-Bounded Instance Complexity. Theor. Comput. Sci. Lance Fortnow, Martin Kummer
1996	J	`jnl`	PP is Closed Under Truth-Table Reductions. Inf. Comput. Lance Fortnow, Nick Reingold
1996	J	`jnl`	The Isomorphism Conjecture Holds Relative to an Oracle. SIAM J. Comput. Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz
1995	A	`conf`	Beyond P^(NP) - NEXP. STACS Stephen A. Fenner, Lance Fortnow
1995	J	`jnl`	Circuit Lower Bounds à la Kolmogorov. Inf. Comput. Lance Fortnow, Sophie Laplante
1995	A*	`conf`	Measure, Category and Learning Theory. ICALP Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan
1995	A	`conf`	Resource-Bounded Instance Complexity (Extended Abstract). STACS Lance Fortnow, Martin Kummer
1995	A*	`conf`	Using Autoreducibility to Separate Complexity Classes. FOCS Harry Buhrman, Lance Fortnow, Leen Torenvliet
1994	J	`jnl`	Extremes in the Degrees of Inferability. Ann. Pure Appl. Log. Lance Fortnow, William I. Gasarch, Sanjay Jain, Efim B. Kinber, Martin Kummer, Stuart A. Kurtz, Mark Pleszkovich, Theodore A. Slaman, Robert Solovay, Frank Stephan
1994	J	`jnl`	Gap-Definable Counting Classes. J. Comput. Syst. Sci. Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz
1994	—	`conf`	Generic Separations. SCT Lance Fortnow, Tomoyuki Yamakami
1994	J	`jnl`	My Favorite Ten Complexity Theorems of the Past Decade Electron. Colloquium Comput. Complex. Lance Fortnow
1994	—	`conf`	My Favorite Ten Complexity Theorems of the Past Decade. FSTTCS Lance Fortnow
1994	J	`jnl`	On the Power of Multi-Prover Interactive Protocols. Theor. Comput. Sci. Lance Fortnow, John Rompel, Michael Sipser
1994	A*	`conf`	Optimality and domination in repeated games with bounded players. STOC Lance Fortnow, Duke Whang
1994	B	`conf`	Separability and One-Way Functions. ISAAC Lance Fortnow, John D. Rogers
1994	J	`jnl`	The Power of Adaptiveness and Additional Queries in Random-Self-Reductions. Comput. Complex. Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel A. Spielman
1994	J	`jnl`	The Role of Relativization in Complexity Theory. Bull. EATCS Lance Fortnow
1994	J	`jnl`	The infinite version of an open communication complexity problem is independent of the axioms of set theory. SIGACT News Lance Fortnow, Stuart A. Kurtz, Duke Whang
1993	—	`conf`	An Oarcle Builder's Toolkit. SCT Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li
1993	J	`jnl`	BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Comput. Complex. László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson
1993	A	`conf`	Gap-Definability as a Closure Property. STACS Stephen A. Fenner, Lance Fortnow, Lide Li
1993	J	`jnl`	Interactive Proof Systems and Alternating Time-Space Complexity. Theor. Comput. Sci. Lance Fortnow, Carsten Lund
1993	J	`jnl`	Random-Self-Reducibility of Complete Sets. SIAM J. Comput. Joan Feigenbaum, Lance Fortnow
1992	J	`jnl`	Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complex. László Babai, Lance Fortnow, Carsten Lund
1992	J	`jnl`	Algebraic Methods for Interactive Proof Systems. J. ACM Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan
1992	A*	`conf`	Degrees of Inferability. COLT Peter Cholak, Efim B. Kinber, Rodney G. Downey, Martin Kummer, Lance Fortnow, Stuart A. Kurtz, William I. Gasarch, Theodore A. Slaman
1992	J	`jnl`	On the Power of Two-Local Random Reductions. Inf. Process. Lett. Lance Fortnow, Mario Szegedy
1992	A*	`conf`	The Isomorphism Conjecture Holds Relative to an Oracle FOCS Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz
1992	—	`conf`	The Power of Adaptiveness and Additional Queries in Random-Self-Reductions. SCT Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel A. Spielman
1991	J	`jnl`	Arithmetization: A New Method in Structural Complexity Theory. Comput. Complex. László Babai, Lance Fortnow
1991	A*	`conf`	Checking Computations in Polylogarithmic Time STOC László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy
1991	—	`conf`	Gap-Definable Counting Classes. SCT Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz
1991	A	`conf`	Interactive Proof Systems and Alternating Time-Space Complexity. STACS Lance Fortnow, Carsten Lund
1991	J	`jnl`	Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complex. László Babai, Lance Fortnow, Carsten Lund
1991	A	`conf`	On the Power of Two-Local Random Reductions. ASIACRYPT Lance Fortnow, Mario Szegedy
1991	—	`conf`	On the Random-Self-Reducibility of Complete Sets. SCT Joan Feigenbaum, Lance Fortnow
1991	—	`conf`	PP is Closed Under Truth-Table Reductions. SCT Lance Fortnow, Nick Reingold
1990	A*	`conf`	A Characterization of \sharp P Arithmetic Straight Line Programs FOCS László Babai, Lance Fortnow
1990	A*	`conf`	Algebraic Methods for Interactive Proof Systems FOCS Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan
1990	—	`conf`	Errata for On the Power of Multi-Prover Interactive Protocols. SCT Lance Fortnow, John Rompel, Michael Sipser
1990	A*	`conf`	Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols FOCS László Babai, Lance Fortnow, Carsten Lund
1989	J	`jnl`	The Complexity of Perfect Zero-Knowledge. Adv. Comput. Res. Lance Fortnow
1988	J	`jnl`	Are There Interactive Protocols for CO-NP Languages? Inf. Process. Lett. Lance Fortnow, Michael Sipser
1988	—	`conf`	On the power of multi-power interactive protocols. SCT Lance Fortnow, John Rompel, Michael Sipser
1987	A*	`conf`	The Complexity of Perfect Zero-Knowledge (Extended Abstract) STOC Lance Fortnow
1987	—	`conf`	The complexity of perfect zero-knowledge. SCT Lance Fortnow