Bounding Rationality by Discounting Time (2009)
Fortnow, Lance, Santhanam, Rahul
Consider a game where Alice generates an integer and Bob wins if he can factor that integer. Traditional game theory tells us that Bob will always win this game even though in practice Alice will win...
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? (2009)
Harry Buhrman, Lance Fortnow, John D. Rogers, Nikolay Vereshchagin
Abstract. The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such...
Infeasibility of instance compression and succinct PCPs for NP (2009)
Lance Fortnow, Rahul Santhanam
The OR-SAT problem asks, given Boolean formulae φ1,..., φm each of size at most n, whether at least one of the φi’s is satisfiable. We show that there is no reduction from OR-SAT to any set A...
Complexity Classes of Equivalence Problems Revisited (2009)
Fortnow, Lance, Grochow, Joshua A.
To determine if two given lists of numbers are the same set, we would sort both lists and see if we get the same result. The sorted list is a canonical form for the equivalence relation of set...
Lance Fortnow, Eric Allender, Stephen Fenner, Eldar Fischer, William Gasarch, Evan Golub, ...
In the June issue Jacobo Torán will take over as editor of this column and I look forward to many exciting columns under his direction. I would like to thank Grzegorz Rozenberg who served as BEATCS...
Approximating the Weight of the Euclidean Minimum Spanning Treein Sublinear Time (2009)
Funda Erg, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohlerk
Abstract We consider the problem of computing the weight of a Euclidean minimum spanning tree fora set of n points in Rd. We focus on the setting where the input point set is supported by...
Yiling Chen, Lance Fortnow, David M. Pennock
We discuss the design of combinatorial betting mechanisms. We characterize the computational complexity of several variants of the problem and pose some oepn research questions.
Non-Deterministic Exponential Time has Two-Prover Interactive Protocols (2008)
Laszlo Babai, Lance Fortnow, Carsten Lund
We determine the exact power of two-prover inter-active proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful non-communicating provers...
Kolmogorov Complexity with Error (2008)
Lance Fortnow, Troy Lee, Nikolai Vereshchagin
Abstract. We introduce the study of Kolmogorov complexity with error. For a metric d, we define Ca(x) to be the length of a shortest program p which prints a string y such that d(x, y) ≤ a. We also...
Complexity of Combinatorial Market Makers ∗ (2008)
Yiling Chen, David M. Pennock, Lance Fortnow, Jennifer Wortman, Nicolas Lambert
We analyze the computational complexity of market maker pricing algorithms for combinatorial prediction markets. We focus on Hanson’s popular logarithmic market scoring rule market maker (LMSR)....
On the Complexity of Succinct Zero-Sum Games (2008)
Fortnow, Lance, Impagliazzo, Russell, Kabanets, Valentine, Umans, Christopher
We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i,j) = C(i,j). We complement the known...
Abstract: A property tester with high probability accepts inputs satisfying a given prop-erty and rejects inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron...
Complexity of Combinatorial Market Makers ∗ (2008)
Yiling Chen, David M. Pennock, Lance Fortnow, Jennifer Wortman, Nicolas Lambert
We analyze the computational complexity of market maker pricing algorithms for combinatorial prediction markets. We focus on Hanson’s popular logarithmic market scoring rule market maker (LMSR)....
Yiling Chen, Lance Fortnow, David M. Pennock
We discuss the design of combinatorial betting mechanisms. We characterize the computational complexity of several variants of the problem and pose some open research questions.
Lance Fortnow, Joe Kilian, David M. Pennock
We develop a framework for trading in compound securities: financial instruments that pay off contingent on the outcomes of arbitrary statements in propositional logic. Buying or selling...
time has two-prover interactive protocols. Computational Complexity, 1:3–40, 1991. (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron Testing, László Babai, ...
[4] Sanjeev Arora, László Babai, Jacques Stern, and Z Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time (2008)
Artur Czumaj, Ilan Newman, Funda Ergün, Ronitt Rubinfeld, Lance Fortnow, Avner Magen, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a ¦ set of §© ¨ points in. We focus on the setting where the input point set is supported by certain basic...
Inverting Onto Functions and Polynomial Hierarchy (2008)
Harry Buhrman, Lance Fortnow, John D. Rogers, Nikolay Vereshchagin
Abstract. The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such...
Yiling Chen, Lance Fortnow, David M. Pennock
We discuss the design of combinatorial betting mechanisms. We characterize the computational complexity of several variants of the problem and pose some open research questions.
Lance Fortnow, Rahul Santhanam
We explore whether various complexity classes can have linear or more generally n k-sized circuit families for some fixed k. We show • The following are equivalent, – NP is in SIZE(n k) (has O(n...
We show that for any constant a, ZPP/b(n) strictly contains ZPTIME(n a)/b(n) for some b(n) = O(log n log log n). Our techniques are very general and give the same hierarchy for all common semantic...
Complexity of Combinatorial Market Makers (2008)
Chen, Yiling, Fortnow, Lance, Lambert, Nicolas, Pennock, David M., Wortman, Jennifer
We analyze the computational complexity of market maker pricing algorithms for combinatorial prediction markets. We focus on Hanson's popular logarithmic market scoring rule market maker (LMSR). Our...
Enumerations of the Kolmogorov Function (2008)
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, ...
A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x). f is an k(n)-enumerator if for every input x of length n, h(x) is...
ON THE COMPLEXITY OF SUCCINCT (2008)
Zero-sum Games, Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
Abstract. We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i,j) = C(i,j). We complement the...
ON THE COMPLEXITY OF SUCCINCT (2008)
Zero-sum Games, Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
Abstract. We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i, j) = C(i, j). We complement the...
Inverting Onto Functions and Polynomial Hierarchy (2008)
Harry Buhrman, Lance Fortnow, John D. Rogers, Nikolay Vereshchagin
Abstract. The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such...
Kolmogorov Complexity with Error (2008)
Lance Fortnow, Troy Lee, Nikolai Vereshchagin
visiting CWI. Abstract. We introduce the study of Kolmogorov complexity with error. For a metric d, we define Ca(x) to be the length of a shortest program p which prints a string y such that d(x, y)...
Under a standard hardness assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all polynomial-time samplable distributions. More...
Some results on derandomization (2008)
Harry Buhrman, Lance Fortnow, A. Pavan
We show several results about derandomization including
NEC Laboratories America Abstract (2008)
Richard Beigel, Lance Fortnow, William Gasarch
We show that any 1-round 2-server Private Information Retrieval Protocol where the answers are 1-bit long must ask questions that are at least n − 2 bits long, which is nearly equal to the known...
Membership Comparable and p-selective Sets (2008)
Richard Beigel, Lance Fortnow, A. Pavan
We construct a 2-membership comparable set that is not btt-reducible to any p-selective set. This is a rare example of an unconditional separation in computational complexity. More generally, for...
Enumerations of the Kolmogorov Function (2008)
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, ...
A recursive enumerator for a function h is an algorithm f which enumerates
Membership Comparable and p-selective Sets (2008)
Richard Beigel, Lance Fortnow, A. Pavan
We construct a 2-membership comparable set that is not btt-reducible to any p-selective set. This is a rare example of an unconditional separation in computational complexity. More generally, for...
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time ∗ (2008)
Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R d. We focus on the setting where the input point set is supported by certain basic (and...
Enumerations of the Kolmogorov Function (2008)
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, ...
A recursive enumerator for a function h is an algorithm f which enumerates
Inverting Onto Functions and Polynomial Hierarchy (2008)
Harry Buhrman, Lance Fortnow, John D. Rogers, Nikolay Vereshchagin
Abstract. The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such...
Lance Fortnow, Rahul Santhanam
We explore whether various complexity classes can have linear or more generally n k-sized circuit families for some fixed k. We show • The following are equivalent, – NP is in SIZE(n k) (has O(n...
Lance Fortnow, Rahul Santhanam
We explore whether various complexity classes can have linear or more generally n k-sized circuit families for some fixed k. We show • The following are equivalent, – NP is in SIZE(n k) (has O(n...
Recent Developments in Explicit Constructions of Extractors (2008)
An extractor is a device that takes a distribution with low maximum probability and with a small amount of truly random bits creates a nearly uniform distribution. Extractors have surprisingly many...
The complexity of algorithms tax even the resources of sixty billion gigabits—or of a universe full of bits; Meyer and Stockmeyer had proved, long ago, that, regardless of computer power, problems...
Under a standard hardness assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all polynomial-time samplable distributions. More...
Some results on derandomization (2008)
Harry Buhrman, Lance Fortnow, A. Pavan
We show several results about derandomization including
Lance Fortnow, Adam R. Klivans
We describe a new approach for understanding the difficulty of designing efficient learning algorithms. We prove that the existence of an efficient learning algorithm for a circuit class C in...
Yiling Chen, Lance Fortnow, David M. Pennock
We discuss the design of combinatorial betting mechanisms. We characterize the computational complexity of several variants of the problem and pose some open research questions.
We show that for any constant a, ZPP/b(n) strictly contains ZPTIME(n a)/b(n) for some b(n) = O(log n log log n). Our techniques are very general and give the same hierarchy for all common semantic...
• Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena at ITT Kanpur have given (2008)
Lance Fortnow, Kenneth W. Regan
This has been an exciting summer for computational complexity.
The Computational Complexity Column (2008)
Lance Fortnow, Kenneth W. Regan
We explain the essence of K. Mulmuley and M. Sohoni, \Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems" [MS02] for a general complexity-theory audience. We...
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time (2008)
Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R^d. We focus on the setting where the input point set is supported by certain basic (and...
07411 Executive Summary -- Algebraic Methods in Computational Complexity (2008)
Agrawal, Manindra, Buhrman, Harry, Fortnow, Lance, Thierauf, Thomas
The seminar brought together almost 50 researchers covering a wide spectrum of complexity theory. The focus on algebraic methods showed once again the great importance of algebraic techniques for...
07411 Abstracts Collection -- Algebraic Methods in Computational Complexity (2008)
Agrawal, Manindra, Buhrman, Harry, Fortnow, Lance, Thierauf, Thomas
From 07.10. to 12.10., the Dagstuhl Seminar 07411 ``Algebraic Methods in Computational Complexity'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the...
Testing Theories with Learnable and Predictive Representations ∗ (2008)
Alvaro S, Rann Smorodinsky, Jonathan Weinstein, Lance Fortnow, Ehud Kalai, ...
We study the problem of testing an expert whose theory has a learnable and predictive parametric representation, as do all standard processes used in Bayesian statistics. We design a test in which...
On the Weak mod m Representation of Boolean Functions (2007)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
one article at a time in L ATEX source form on the Internet. Pagination
Lance Fortnow, William Gasarch, Sanjay Jain, Efim Kinber, Martin Kummer, ...
IBM Corporation
Circuit Lower Bounds à la Kolmogorov (2007)
Lance Fortnow, Sophie Laplante, Sophie Laplante
In a recent paper, Razborov [Raz93] gave a new combinatorial proof of Hastad's switching lemma [Has89], eliminating the probabilistic argument altogether. In this paper we adapt his proof and...
Uniformly Hard Languages (2007)
Ladner [18] showed that there are no minimal recursive sets under polynomial-time reductions. Given any recursive set A, Ladner constructs a set B such that B strictly reduces to A but B does not lie...
On the Relative Sizes of Learnable Sets (2007)
Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith
Measure and category (or rather, their recursion-theoretical counterparts) have been used in theoretical computer science to make precise the intuitive notion "for most of the recursive...
Lance Fortnow, Stuart Kurtz, Duke Whang
In 1986, Babai, Frankl and Simon [BFS86] defined the polynomial hierarchy in communication complexity and asked whether \Sigma cc 2 = \Pi cc 2 . In order to tackle this problem, researchers have...
Uniformly Hard Languages (2007)
Ladner [14] showed that there are no minimal recursive sets under polynomial-time reductions. Given any recursive set A, Ladner constructs a set B such that B strictly reduces to A but B does not lie...
Two Remarks on Self-Correctability versus Random-Self-Reducibility (2007)
Joan Feigenbaum, Lance Fortnow, Ashish Naik
We examine the relationship between two types of probabilistic self-reductions that play crucial roles in the theory of interactive proof systems, program-checking, and program-testing:...
Aki Kanamori. A Short History of Computational Complexity (2007)
Lance Fortnow, Lance Fortnow, Steve Homer
Every third year the Conference on Computational Complexity is held in Europe and this summer the University of Aarhus (Denmark) will host the meeting July 7-10. More details at the conference web...
Derandomization: A Brief Overview (2007)
Lance Fortnow, Valentine Kabanets
Perhaps no area in computational complexity has seen greater progress over the past several years than derandomization, i.e., the ability to remove randomness from probabilistic computation. The last...
Tugkan Batu, Eldar Fischer, Lance Fortnow, Ronitt Rubinfeld, Patrick White
Given access to independent samples of a distribution A over [n] [m], we show how to test whether the distributions formed by projecting A to each coordinate are independent, i.e., whether A is...
The Computational Complexity Column by (2007)
I have moved back to the University of Chicago and so has the web page for this column. See above for new URL and contact informaion. This issue Scott Aaronson writes quite an interesting (and...
We develop a framework for trading in compound securities: financial instruments that pay off contingent on the outcomes of arbitrary statements in propositional logic. Buying or selling...
NEC Laboratories America (2007)
Richard Beigel, Lance Fortnow, William Gasarch
We show that any 1-round 2-server Private Information Retrieval System where the answers are 1-bit long must ask questions that are at least n 2 bits long, which is nearly equal to the known n 1...
Lance Fortnow, A. Pavan, Samik Sengupta
We show that if SAT does not have small circuits, then there must exist a small number of formulas such that every small circuit fails to compute satisfiability correctly on at least one of these...
Richard Beigel, Harry Buhrman, Lance Fortnow, U. Chicago
We construct an oracle A such that P
Harry Buhrman, Richard Chang, Lance Fortnow
The results in this paper show that coNP is contained in NP with 1 bit of advice (denoted NP=1) if and only if the Polynomial Hierarchy (PH) collapses to D P, the second level of the Boolean...
Letter Computational Identification of Operons in Microbial Genomes (2007)
Yu Zheng, Joseph D. Szustakowski, Lance Fortnow, Richard J. Roberts, Simon Kasif
By applying graph representations to biochemical pathways, a new computational pipeline is proposed to find potential operons in microbial genomes. The algorithm relies on the fact that enzyme genes...
Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of estimating the weight of a Euclidean minimum spanning tree for a set of n points in R
Membership Comparable and p-Selective Sets (2007)
Richard Beigel, Lance Fortnow, A. Pavan
We show that there exists a 2-membership comparable set that is not btt-reducible to any pselective set. This is a rare example of an unconditional separation in computational complexity. More...
Stephen Fenner, Lance Fortnow, Stuart A. Kurtz
We introduce symmetric perfect generic sets. These sets vary from the usual generic sets by allowing limited infinite encoding into the oracle. We then show that the Berman-Hartmanis isomorphism...
Luis Antunes, Lance Fortnow, N. V. Vinodchandran
We show a relation between Computational Depth and Levin's notion of average polynomial time. Computational depth measures the amount of \useful " information in a string. We consider...
Some results on derandomization (2007)
We show several results about derandomization including 1. If NP is easy on average then ecient pseudorandom generators exist and P = BPP. 2. If NP is easy on average then given an NP machine M we...
The Computational Complexity Column (2007)
Lance Fortnow, William Gasarch, Evan Golub, Clyde Kruskal
This has been quite an exciting summer for computational complexity. The 15th Conference on Computational Complexity held July 4-7 in Florence was a great success. We had many interesting talks and a...
Richard Beigel, Harry Buhrman, Lance Fortnow, Leen Torenvliet
We consider the hardness of enumerating k possible values for the Kolmogorov complexity function C(x) so that one of them is correct. We show several results including Any computable enumerator for...
Richard Beigel, Noga Alon, Mehmet Serkan Apaydn, Lance Fortnow, Simon Kasif
Tettelin et. al. proposed a new method for closing the gaps in whole genome shotgun sequencing projects. The method uses a multiplex PCR strategy in order to minimize the time and eort required to...
Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith
Measure and category (or rather, their recursion theoretical counterparts)
Tugkan Batu, Eldar Fischer, Lance Fortnow, Ronitt Rubinfeld, Patrick White
random variables for independence and identity
The Division Breakthroughs (2007)
Sometimes the simplest problems lead to the most interesting theory. Consider the division problem, given a and b in binary, output b a
Tugkan Batu, Eldar Fischer, Lance Fortnow, Ronitt Rubinfeld, Patrick White
Given access to independent samples of a distribution A over [n] [m], we show how to test whether the distributions formed by projecting A to each coordinate are independent, i.e., whether A is...
Stephen Fenner, Lance Fortnow, Lide Li
Gap-definability and the gap-closure operator were defined in [FFK94]. Few complexity classes were known at that time to be gap-definable. In this paper, we give simple characterizations of both...
Membership Comparable and p-selective Sets (2007)
Richard Beigel, Lance Fortnow, A. Pavan
We show that there exists a 2-membership comparable set that is not btt-reducible to any pselective set. This is a rare example of an unconditional separation in computational complexity.
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time (2007)
Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R . We focus on the setting where the input point set is supported by certain basic (and...
A Survey on Private Information Retrieval (2007)
Lance Fortnow, Eric Allender, Stephen Fenner, Eldar Fischer, Evan Golub, Clyde Kruskal, ...
In the June issue Jacobo Torn will take over as editor of this column and I look forward to many exciting columns under his direction. I would like to thank Grzegorz Rozenberg who served as BEATCS...
Recent Developments in Explicit Constructions of Extractors (2007)
An extractor is a device that takes a distribution with low maximum probability and with a small amount of truly random bits creates a nearly uniform distribution. Extractors have surprisingly many...
Enumerations of the Kolmogorov Function (2007)
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpre, ...
Torenvliet i A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x). f is an k(n)-enumerator if for every input x of length n,...
Uniformly Hard Languages (2007)
Ladner [18] showed that there are no minimal recursive sets under polynomial-time reductions. Given any recursive set A, Ladner constructs a set B such that B strictly reduces to A but B does not lie...
Some results on derandomization (2007)
Harry Buhrman, Lance Fortnow, A. Pavan
We show several results about derandomization including 1. If NP is easy on average then e#cient pseudorandom generators exist and P = BPP. 2. If NP is easy on average then given an NP machine M we...
Membership Comparable and p-selective Sets (2007)
Richard Beigel, Lance Fortnow, A. Pavan
We show that there exists a 2-membership comparable set that is not btt-reducible to any pselective set. This is a rare example of an unconditional separation in computational complexity.
The Computational Complexity Column (2007)
Lance Fortnow Nec, Lance Fortnow, Stephen A. Fenner
This article de nes and proves basic properties of the standard quantum circuit model of computation. The model is developed abstractly in close analogy with (classical) deterministic and...
Two Oracles that Force a Big Crunch (2007)
Harry Buhrman, Stephen Fenner, Lance Fortnow, Leen Torenvliet
We construct an oracle A such that NEXP . The construction of this oracle answers a long standing open question rst posed by Heller, and unsuccessfully attacked many times since. For the rst...
Joan Feigenbaum, David M. Pennock, Lance Fortnow, Rahul Sami
According to economic theory, supported by empirical and laboratory evidence, the equilibrium price of a financial security reflects all of the information regarding the security’s value. We...
Bluffing and strategic reticence in prediction markets (2007)
Yiling Chen, Daniel M. Reeves, David M. Pennock, Robin D. Hanson, Lance Fortnow, Rica Gonen
Abstract. We study the equilibrium behavior of informed traders interacting with two types of automated market makers: market scoring rules (MSR) and dynamic parimutuel markets (DPM). Although both...
Lance Fortnow, Rahul Santhanam
The OR-SAT problem asks, given Boolean formulae φ1,..., φm each of size at most n, whether at least one of the φi’s is satisfiable. We show that there is no reduction from OR-SAT to any set A...
Betting on permutations (2007)
Yiling Chen, Evdokia Nikolova, Lance Fortnow
We consider a permutation betting scenario, where people wager on the final ordering of n candidates: for example, the outcome of a horse race. We examine the auctioneer problem of risklessly...
Lance Fortnow, Rahul Santhanam
The OR-SAT problem asks, given Boolean formulae φ1,...,φm each of size at most n, whether at least one of the φi’s is satisfiable. We show that there is no reduction from OR-SAT to any set A...
Lance Fortnow, Rahul Santhanam
We survey time hierarchies, with an emphasis on recent work on hierarchies for semantic classes. 1
Enumerations of the Kolmogorov function (2006)
Beigel, Richard, Buhrman, Harry, Fejer, Peter, Fortnow, Lance, Grabowski, Piotr, Longpré, Luc, ...
A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x). f is a k(n)-enumerator if for every input x of length n, h(x) is among...
Very Sparse Leaf Languages (2006)
Fortnow, Lance, Ogihara, Mitsunori
Unger studied the balanced leaf languages defined via poly-logarithmically sparse leaf pattern sets. Unger shows that $\np$-complete sets are not polynomial-time many-one reducible to such balanced...
Abstract Alexandre Pinto U. (2006)
Lance Fortnow, U. Chicago, André Souto
Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of non-random information by computational depth, the difference between the polynomial-time-bounded Kolmogorov complexity and...
Extracting Kolmogorov complexity with applications to dimension zero-one laws (2006)
Lance Fortnow, John M. Hitchcock, A. Pavan, N. V. Vinodch, Fengming Wang Y
Abstract. We apply recent results on extracting randomness from independent sources to "extract " Kolmogorov complexity. For any ff; ffl? 0, given a string x with K(x) ? ffjxj, we...
Extracting Kolmogorov complexity with applications to dimension zero-one laws (2006)
Lance Fortnow, John M. Hitchcock, A. Pavan, N. V. Vinodch, Fengming Wang
Abstract. We apply recent results on extracting randomness from independent sources to "extract " Kolmogorov complexity. For any ff, ffl> 0, given a string x with K(x)> ff|x|,...
Computational depth: Concept and applications (2006)
Luis Antunes, Lance Fortnow, Dieter Van Melkebeek, N. V. Vinodch
Torturing an uninformed witness cannot give information about the
Extracting Kolmogorov complexity with applications to dimension zero-one laws (2006)
Lance Fortnow, A. Pavan, John M. Hitchcock, N. V. Vinodch, Fengming Wang
We apply results on extracting randomness from independent sources to “extract ” Kolmogorov complexity. For any α, ɛ> 0, given a string x with K(x)> α|x|, we show how to use a constant...
A tight lower bound for restricted PIR protocols (2006)
Richard Beigel, Lance Fortnow, William Gasarch
Abstract. We show that any 1-round 2-server Private Information Retrieval Protocol where the answers are 1-bit long must ask questions that are at least n − 2 bits long, which is nearly equal to...
Computational depth: Concept and applications (2006)
Luis Antunes, Lance Fortnow, Dieter Van Melkebeek, N. V. Vinodch
Torturing an uninformed witness cannot give information about the crime. Leonid Levin [Lev84] Abstract. We introduce Computational Depth, a measure for the amount of “nonrandom ” or “useful”...
Computational depth: Concept and applications (2006)
Luis Antunes, Lance Fortnow, Dieter Van Melkebeek, N. V. Vinodch
Torturing an uninformed witness cannot give information about the crime. Leonid Levin [Lev84] Abstract. We introduce Computational Depth, a measure for the amount of “nonrandom ” or “useful”...
The complexity of forecast testing (2006)
Lance Fortnow, Rakesh V. Vohra
Abstract Consider a weather forecaster predicting a probability of rain for the next day. We consider tests that given a finite sequence of forecast predictions and outcomes will either pass or fail...
Abstract Alexandre Pinto U. (2006)
Lance Fortnow, U. Chicago, André Souto
Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of non-random information by computational depth, the difference between the polynomial-time-bounded Kolmogorov complexity and...
The complexity of forecast testing (2006)
Lance Fortnow, Rakesh V. Vohra
Consider a weather forecaster predicting a probability of rain for the next day. We consider tests that given a finite sequence of forecast predictions and outcomes will either pass or fail the...
Abstract Alexandre Pinto U. (2006)
Lance Fortnow, U. Chicago, André Souto
Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of non-random information by computational depth, the difference between the polynomial-time-bounded Kolmogorov complexity and...
Extracting Kolmogorov complexity with applications to dimension zero-one laws (2006)
Lance Fortnow, A. Pavan, John M. Hitchcock, N. V. Vinodch, Fengming Wang
We apply results on extracting randomness from independent sources to “extract ” Kolmogorov complexity. For any α, ɛ> 0, given a string x with K(x)> α|x|, we show how to use a constant...
The literature of incomplete contracts is actually more about simple contracts than about incomplete contracts: “foundations ” of incomplete contracts are theories of why contracts are optimally...
The complexity of forecast testing (2006)
Lance Fortnow, Rakesh V. Vohra
Consider a weather forecaster predicting a probability of rain for the next day. We consider tests that given a finite sequence of forecast predictions and outcomes will either pass or fail the...
Extracting Kolmogorov complexity with applications to dimension zero-one laws (2006)
Lance Fortnow, John M. Hitchcock, A. Pavan, N. V. Vinodch, Fengming Wang
Abstract We apply recent results on extracting randomness from independent sources to "extract"Kolmogorov complexity. For any ff, ffl> 0, given a string x with K(x)> ff|x|, we show...
Tolerant versus intolerant testing for boolean properties (2005)
Abstract: A property tester with high probability accepts inputs satisfying a given property and rejects inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron...
We show that under a reasonable hardness assumptions, the time-bounded Kolmogorov distribution is a universal samplable distribution. Under the same assumption we exactly characterize the worst-case...
On the complexity of succinct zero-sum games (2005)
Lance Fortnow, Valentine Kabanets, Russell Impagliazzo, Christopher Umans
We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i, j) = C(i, j). We complement the known...
Linear advice for randomized logarithmic space (2005)
Lance Fortnow, Adam R. Klivans
Abstract. We show that RL t, L/O(n), i.e., any language computable in randomized logarithmic space can be computed in deterministic logarithmic space with a linear amount of non-uniform advice. To...
Linear advice for randomized logarithmic space (2005)
Lance Fortnow, Adam R. Klivans
Abstract. We show that RL ⊆ L/O(n), i.e., any language computable in randomized logarithmic space can be computed in deterministic logarithmic space with a linear amount of non-uniform advice. To...
Lance Fortnow, Mitsunori Ogihara
Unger studied the balanced leaf languages defined via poly-logarithmically sparse leaf pattern sets. Unger shows that NP-complete sets are not polynomial-time many-one reducible to such balanced leaf...
Lance Fortnow, Rahul Santhanam, Luca Trevisan
We show that for any constant a, ZPP/b(n) strictly contains ZPTIME(n a)/b(n) for some b(n) = O(log n log log n). Our techniques are very general and give the same hierarchy for
04421 Abstracts Collection -- Algebraic Methods in Computational Complexity (2005)
Buhrman, Harry, Fortnow, Lance, Thierauf, Thomas
From 10.10.04 to 15.10.04, the Dagstuhl Seminar 04421 ``Algebraic Methods in Computational Complexity'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During...
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws (2005)
Lance Fortnow, John M. Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang
We apply recent results on extracting randomness from independent sources to “extract” Kolmogorov complexity. For any α, ɛ> 0, given a string x with K(x)> α|x|, we show how to use a...
Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman
We develop a framework for trading in compound securities: financial instruments that pay o # contingent on the outcomes of arbitrary statements in propositional logic. Buying or selling...
Betting Boolean-Style: A Framework for Trading in Securities Based on Logical Formulas (2004)
Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman
We develop a framework for trading in compound securities: financial instruments that pay o# contingent on the outcomes of arbitrary statements in propositional logic. Buying or selling...
Lance Fortnow, Richard Lipton, Anastasios Viglas, Dieter Van Melkebeek
We establish the first polynomial time-space lower bounds for satisfiability on general models of computation. We show that for any constant c less than the golden ratio there exists a positive...
Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman
We develop a framework for trading in compound securities: financial instruments that pay off contingent on the outcomes of arbitrary statements in propositional logic. Buying or selling...
Kolmogorov complexity and computational complexity (2004)
We describe the properties of various notions of time-bounded Kolmogorov complexity and other connections between Kolmogorov complexity and computational complexity. 1
Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman
We develop a framework for trading in compound securities: financial instruments that pay off contingent on the outcomes of arbitrary statements in propositional logic. Buying or selling...
Kolmogorov complexity and computational complexity (2004)
We describe the properties of various notions of time-bounded Kolmogorov complexity and other connections between Kolmogorov complexity and computational complexity. 1
Kolmogorov Complexity and Computational Complexity (2004)
We describe the properties of various notions of time-bounded Kolmogorov complexity and other connections between Kolmogorov complexity and computational complexity.
Computation in a Distributed Information Market (2004)
Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami
According to economic theory---supported by empirical and laboratory evidence--- the equilibrium price of a financial security reflects all of the information regarding the security's value. We...
Lance Fortnow, Richard Lipton, Anastasios Viglas, Dieter Van Melkebeek
We establish the first polynomial time-space lower bounds for satisfiability on general models of computation. We show that for any constant c less than the golden ratio there exists a positive...
Is P versus NP formally independent (2003)
I have moved back to the University of Chicago and so has the web page for this column. See above for new URL and contact informaion. This issue Scott Aaronson writes quite an interesting (and...
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman
Hein R"ohrig \Lambda \Lambda
Computation in a distributed information market (2003)
Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami
According to economic theory---supported by empirical and laboratory evidence---the equilibrium price of a financial security reflects all of the information regarding the security's value. We...
Sophistication revisited (2003)
Abstract. The Kolmogorov structure function divides the smallest program producing a string in two parts: the useful information present in the string, called sophistication if based on total...
A Short History of Computational Complexity (2003)
It all started with a machine. In 1936, Turing developed his theoretical computational model. He based his model on how he perceived mathematicians think. As digital computers were developed in the...
Computation in a distributed information market (2003)
Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami
According to economic theory---supported by empirical and laboratory evidence---the equilibrium price of a financial security reflects all of the information regarding the security's value. We...
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has...
Are Cook and Karp ever the same (2003)
We consider the question as to whether there exists a set A such that every set polynomialtime Turing equivalent to A is also many-one equivalent to A. We show that if E = NE then no sparse set has...
One complexity theorist’s view of quantum computing (2003)
The complexity of quantum computation remains poorly understood. While physicists attempt to nd ways to create quantum computers, we still do not have much evidence one way or the other as to how...
Are Cook and Karp ever the same (2003)
We consider the question whether there exists a set A such that every set polynomial-time Turing equivalent to A is also many-one equivalent to A. We show that if E = NE then no sparse set has this...
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has...
Infinitely-Often Autoreducible Sets (2003)
Richard Beigel, Lance Fortnow, Frank Stephan, National Ict Australia
A set A is autoreducible if one can compute, for all x, the value A(x) by querying A only at places y x. Furthermore, A is infinitely-often autoreducible if, for infinitely many x, the value A(x) can...
Using Depth to Capture Average-Case Complexity (2003)
Luís Antunes, Lance Fortnow, N. V. Vinodchandran
We give the rst characterization of Turing machines that run in polynomial-time on average. We show that a Turing machine M runs in average polynomial-time if for all inputs x the Turing machine uses...
On the Complexity of Succinct Zero-Sum Games (2003)
Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
We study the complexity of solving succinct zero-sum games, i.e., the games whose payo# matrix M is given implicitly by a Boolean circuit C such that M(i, j) = C(i, j). We complement the known...
Infinitely-Often Autoreducible Sets (2003)
Richard Beigel, Lance Fortnow, Frank Stephan
A set A is autoreducible if one can compute, for all x, the value A(x) by querying A only at places y != x. Furthermore, A is infinitely-often autoreducible if, for infinitely many x, the value A(x)...
Infinitely-often autoreducible sets (2003)
A set A is autoreducible if one can compute, for all x, the value A(x) by querying A only at places y � = x. Furthermore, A is infinitely-often autoreducible if, for infinitely many x, the value...
Harry Buhrman, Richard Chang, Lance Fortnow
Abstract. The results in this paper show that coNP is contained in NP with 1 bit of advice (denoted NP/1) if and only if the Polynomial Hierarchy (PH) collapses to D P, the second level of the...
A Short History of Computational Complexity (2003)
Aki Kanamori, Lance Fortnow, Lance Fortnow, Steve Homer
Every third year the Conference on Computational Complexity is held in Europe and this summer the University of Aarhus (Denmark) will host the meeting July 7-10. More details at the conference web...
Sublinear-Time Approximation of Euclidean Minimum Spanning Tree (2003)
Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R^d. We focus on the situation when the input point set is supported by certain basic...
Is P versus NP formally independent (2003)
I have moved back to the University of Chicago and so has the web page for this column. See above for new URL and contact informaion. This issue Scott Aaronson writes quite an interesting (and...
One complexity theorist’s view of quantum computing (2003)
The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how...
Sophistication revisited (2003)
Kolmogorov complexity measures the ammount of information in a string as the size of the shortest program that computes the string. The Kolmogorov structure function divides the smallest program...
Lance Fortnow, Valentine Kabanets, Russell Impagliazzo, Christopher Umans
We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i, j) = C(i, j). We complement the known...
Sophistication revisited (2003)
Kolmogorov complexity measures the ammount of information in a string as the size of the shortest program that computes the string. The Kolmogorov structure function divides the smallest program...
Quantum property testing (2003)
Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has...
Theory of Quantum Computing and Communication (2002)
A workshop sponsored by NSF C-CR and organized by the Center for Discrete Math and Theoretical Computer Science (DIMACS) was held at Elmsford, New York, January 17-18, 2002 where we had several...
Harry Buhrman, Richard Chang, Lance Fortnow
The results in this paper show that coNP is contained in NP with 1 bit of advice (denoted NP/1) if and only if the Polynomial Hierarchy (PH) collapses to DP,thesecond level of the Boolean Hierarchy...
Prediction and dimension (2002)
Abstract. Given a set X of sequences over a nite alphabet, we investigate the following three quantities. (i) The feasible predictability of X is the highest success ratio that a polynomial-time...
In often autoreducible sets (2002)
Richard Beigel, Lance Fortnow, Frank Stephan
A set A is autoreducible if one can compute, for all x, the value A(x) with querying A only at places y different from x. It is infinitely often autoreducible if, for infinitely many x, the value...
Prediction and dimension (2002)
Given a set X of sequences over a finite alphabet, we investigate the following three quantities. (i) The feasible predictability of X is the highest success ratio that a polynomialtime randomized...
Computational Identification of Operons in Microbial Genomes (2002)
Zheng, Yu, Szustakowski, Joseph D., Fortnow, Lance, Roberts, Richard J., Kasif, Simon
Comparing notions of full derandomization (2001)
Most of the hypotheses of full derandomization fall into two sets of equivalent statements: Those equivalent to the existence of ecient pseudorandom generators and those equivalent to approximating...
Comparing notions of full derandomization (2001)
Most of the hypotheses of full derandomization fall into two sets of equivalent statements: Those equivalent to the existence of ecient pseudorandom generators and those equivalent to approximating...
Melkebeek. Computational depth (2001)
Luis Antunes, Lance Fortnow, Dieter Van Melkebeek
We introduce Computational Depth, a measure for the amount of "nonrandom " or "useful " information in a string by considering the difference of various Kolmogorov...
Melkebeek. Computational depth (2001)
We introduce computational depth, a generalization and extension of the logical depth notion due to Bennet. We consider several variations by considering the dierence of two Kolmogorov complexity...
An optimal procedure for gap closing in whole genome shotgun sequencing (2001)
Richard Beigel, Lance Fortnow, Mehmet Serkan Apaydin, Simon Kasif
Tettelin et. al. proposed a new method for closing the gaps in whole genome shotgun sequencing projects. The method uses a multiplex PCR strategy in order to minimize the time and effort required to...
Ladner [18] showed that there are no minimal recursive sets under polynomial-time reductions. Given any recursive set A, Ladner constructs a set B such that B strictly reduces to A but B does not lie...
Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers
We look at the hypothesis that all honest onto polynomial-time computable functions have a polynomial-time computable inverse. We show this hypothesis equivalent to several other complexity...
Testing random variables for independence and identity (2001)
Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, Patrick White
Given access to independent samples of a ¤ distribution ¥¦ § ¨ ¥© § over, we show how to test whether the distributions formed by projecting ¤ to each coordinate are independent, i.e.,...
One Complexity Theorist's View of Quantum Computing (2000)
The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how...
Testing that distributions are close (2000)
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n
Testing that distributions are close (2000)
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n
Optimal Proof Systems and Sparse Sets (2000)
Harry Buhrman, Steve Fenner, Lance Fortnow, Dieter Van Melkebeek
. We exhibit a relativized world where NP \ SPARSE has no complete sets. This gives the rst relativized world where no optimal proof systems exist. We also examine under what reductions NP \ SPARSE...
Optimal Proof Systems and Sparse Sets (2000)
Harry Buhrman, Steve Fenner, Lance Fortnow, Dieter Van Melkebeek
. We exhibit a relativized world where NP # SPARSE has no complete sets. This gives the first relativized world where no optimal proof systems exist. We also examine under what reductions NP # SPARSE...
We give a modern historical and philosophical discussion of diagonalization as a tool to prove lower bounds in computational complexity. We will give several examples and discuss four possible...
Optimal Proof Systems and Sparse Sets (2000)
By Harry Buhrman, Harry Buhrman, Steve Fenner, Lance Fortnow, Dieter Van Melkebeek
We exhibit a relativized world where NP # SPARSE has no complete sets. This gives the first relativized world where no optimal proof systems exist. We also examine under what reductions NP # SPARSE...
Time-Space Tradeoffs for Nondeterministic Computation (2000)
Lance Fortnow, Dieter Van Melkebeek
We show new tradeoffs for satisfiability and nondeterministic linear time. Satisfiability cannot be solved on general purpose random-access Turing machines in time n 1.618 and space n o(1) . This...
One Complexity Theorist's View of Quantum Computing (2000)
The complexity of quantum computation remains poorly understood. While physicists attempt to nd ways to create quantum computers, we still do not have much evidence one way or the other as to how...
Time-space tradeoffs for satisfiability (2000)
We give the first nontrivial model-independent time-space tradeoffs for satisfiability. Namely, we show that SAT cannot be solved simultaneously in n 1+o(1) time and n 1−ɛ space for any ɛ> 0...
Lance Fortnow, Dieter Van Melkebeek
We show new tradeoffs for satisfiability and nondeterministic linear time. Satisfiability cannot be solved on general purpose random-access Turing machines in time n 1.618 and space n o(1). This...
Testing that distributions are close (2000)
Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n 2/3 ɛ −4 log n)...
Distributionally-Hard Languages (1999)
Lance Fortnow, A. Pavan, Alan L. Selman
Define a set L to be distributionally-hard to recognize if for every polynomial-time computable distribution µ with infinite support, L is not recognizable in polynomial time on the µ-average. Cai...
Optimal Proof Systems and Sparse Sets (1999)
Harry Buhrman, Steve Fenner, Lance Fortnow, Dieter Van Melkebeek
We exhibit a relativized world where NP # SPARSE has no complete sets. This gives the first relativized world where no optimal proof systems exist. We also examine under what reductions NP # SPARSE...
Two Oracles that Force a Big Crunch (1999)
Harry Buhrman, Stephen Fenner, Lance Fortnow, Leen Torenvliet
The central theme of this paper is the construction of an oracle A such that NEXP A = P NP A . The construction of this oracle answers a long standing open question rst posed by Heller, and...
One-sided Versus Two-sided Error in Probabilistic Computation (1999)
We demonstrate how to use Lautemann's proof that BPP is in \Sigma p 2 to exhibit that BPP is in RP PromiseRP . Immediate consequences show that if PromiseRP is easy or if there exist quick...
Lance Fortnow, Judy Goldsmith, Matthew A. Levy, Stephen Mahaney
. A language is L-printable if there is a logspace algorithm which, on input 1 n , prints all members in the language of length n. Following the work of Allender and Rubinstein [AR88] on P -printable...
Complexity Limitations on Quantum Computation (1999)
We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation. We show several results for the probabilistic quantum...
Complexity limitations on quantum computation (1998)
Fortnow, Lance, Rogers, John D.
We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation. We show several results for the probabilistic quantum...
Separating complexity classes using autoreducibility (1998)
Buhrman, Harry, Fortnow, Lance, Torenvliet, Leen, Van Melkebeek, Dieter
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Nearly Optimal Language Compression using Extractors (1998)
Lance Fortnow, Sophie Laplante
. We show two sets of results applying the theory of extractors to resource-bounded Kolmogorov complexity: Most strings in easy sets have nearly optimal polynomial-time CD complexity. This extends...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman Cwi, Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Beating A Finite Automaton in the Big Match (1998)
We look at the Big Match game, a variation of the repeated Matching Pennies game where if the first player plays tails the game ends with the first player receiving the last round's payoff. We...
NP Might Not Be As Easy As Detecting Unique Solutions (1998)
Richard Beigel, Harry Buhrman, Lance Fortnow
We construct an oracle A such that P A = \PhiP A and NP A = EXP A : This relativized world has several amazing properties: ffl The oracle A gives the first relativized world where one can solve...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman Cwi, Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Nonrelativizing Separations (1998)
Harry Buhrman, Lance Fortnow, Thomas Thierauf
We show that MA EXP , the exponential time version of the Merlin-Arthur class, does not have polynomial size circuits. This significantly improves the previous known result due to Kannan since we...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Nearly Optimal Language Compression using Extractors (1998)
Lance Fortnow, Sophie Laplante
. We show two sets of results applying the theory of extractors to resource-bounded Kolmogorov complexity: -- Most strings in easy sets have nearly optimal polynomial-time CD complexity. This extends...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Lance Fortnow, Judy Goldsmith, Matthew A. Levy, Stephen Mahaney
. A language is L-printable if there is a logspace algorithm which, on input 1 n , prints all members in the language of length n. Following the work of Allender and Rubinstein [SIAM J. Comput., 17...
We consider the question whether two queries to SAT are as powerful as one query. We show that if P NP[1] = P NP[2] then ffl Locally either NP = coNP or NP has polynomial-size circuits. ffl P NP = P...
One-sided Versus Two-sided Randomness (1998)
We demonstrate how to use Lautemann's proof that BPP is in \Sigma p 2 to exhibit that BPP is in RP PromiseRP . Immediate consequences show that if PromiseRP is easy or if there exist quick...
Uniformly Hard Languages (1998)
We examine the class of "uniformly hard languages," where a language is just not merely infinitely often not computable in polynomial-time but in fact the languages are hard nearly...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
Separating Complexity Classes using Autoreducibility (1998)
Harry Buhrman, Lance Fortnow, Dieter Van Melkebeek, Leen Torenvliet
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from...
On Coherence, Random-Self-Reducibility, and Self-Correction (1998)
Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish Naik
. We study three types of self-reducibility that are motivated by the theory of program verification. A set A is random-self-reducible if one can determine whether an input x is in A by making random...
On the relative size of learnable sets (1998)
Lance Fortnow, Stuart A. Kurtz, Carl H. Smith, Frank Stephan
Measure and category (or rather, their recursion-theoretical counterparts) have been used in theoretical computer science to make precise the intuitive notion “for most of the recursive sets. ”...
Resource-bounded Kolmogorov complexity revisited (1997)
Harry Buhrman, Lance Fortnow, Sophie Laplante
We take a fresh look at CD complexity, where CD t (x) is the size of the smallest program that distinguishes x from all other strings in time t(jxj). We also look at CND complexity, a new...
Distributionally-hard languages (1997)
Lance Fortnow, A. Pavan, Alan L. Selman
Cai and Selman [CS99] defined a modification of Levin's notion of average polynomial time and proved, for every P-bi-immune language L and every polynomial-time computable distribution with...
Distributionally-hard languages (1997)
Lance Fortnow, A. Pavan, Alan L. Selman
Cai and Selman [CS99] defined a modification of Levin's notion of average polynomial time and proved, for every P-bi-immune language L and every polynomial-time computable distribution with...
Resource-bounded Kolmogorov complexity revisited (1997)
Harry Buhrman, Lance Fortnow, Sophie Laplante
We take a fresh look at CD complexity, where CD t (x) is the size of the smallest program that distinguishes x from all other strings in time t(jxj). We also look at CND complexity, a new...
Resource-Bounded Kolmogorov Complexity Revisited (1997)
We take a fresh look at CD complexity, where CD t (x) is the smallest program that distinguishes x from all other strings in time t(jxj). We also look at a CND complexity, a new nondeterministic...
Probabilistic Computation and Linear Time (1997)
In this paper, we give an oracle under which BPP is equal to probabilistic linear time, an unusual collapse of a complexity time hierarchy. In addition, we also give oracles where \Delta P 2 is...
Traditionally, computational complexity theorists have looked at NP problems like three-coloring to determine whether some solution exists. In counting complexity, we ask how many solutions exist....
Time-Space Tradeoffs for Satisfiability (1997)
We give the first nontrivial model-independent time-space tradeoffs for satisfiability. Namely, we show that SAT cannot be solved simultaneously in n 1+o(1) time and n 1\Gammaffl space for any ffl ?...
Six Hypotheses in Search of a Theorem (1997)
Harry Buhrman, Lance Fortnow, Leen Torenvliet
We consider the following six hypotheses: ffl P = NP. ffl SAT is truth-table reducible to a P-selective set. ffl SAT is truth-table reducible to a k- approximable set for some k. ffl FP NP jj = FP...
Complexity Limitations on Quantum Computation (1997)
We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation. We show several results for the probabilistic quantum...
Results on Resource-Bounded Measure (1997)
Harry Buhrman, Stephen Fenner, Lance Fortnow
. We construct an oracle relative to which NP has p-measure 0 but D p has measure 1 in EXP. This gives a strong relativized negative answer to a question posed by Lutz [Lut96]. Secondly, we give...
On Coherence, Random-Self-Reducibility, and Self-Correction (1997)
Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish Naik
. We study three types of self-reducibility that are motivated by the theory of program verification. A set A is random-self-reducible if one can determine whether an input x is in A by making random...
Complexity Limitations on Quantum Computation (1997)
We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation. We show several results for the probabilistic quantum...
Complexity Limitations on Quantum Computation (1997)
We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation. We show several results for the probabilistic quantum...
Kolmogorov Techniques in Computational Complexity Theory (1997)
Sophie Laplante, Joan Feigenbaum, Lance Fortnow
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii CHAPTER 1. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 iHow Hard is this Problem?j . . . ....
Nonrelativizing Separations (1997)
Harry Buhrman, Lance Fortnow, Thomas Thierauf, Abt Theoretische Informatik
We show that MA EXP , the exponential time version of the Merlin-Arthur class, does not have polynomial size circuits. This significantly improves the previous known result due to Kannan since we...
Consider the three strings shown above. Although all are 24-bit binary strings
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai Vereshchagin
classification: Kolmogorov complexity, computational complexity
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai Vereshchagin
classification: Kolmogorov complexity, computational complexity
Distributionally-hard languages (1997)
Lance Fortnow, A. Pavan, Alan L. Selman
Cai and Selman [CS99] defined a modification of Levin’s notion of average polynomial time and proved, for every P-bi-immune language L and every polynomial-time computable distribution µ with...
We consider the question whether two queries to SAT are as powerful as one query. We show that if P NP[1] = P NP[2] then Locally either NP = coNP or NP has polynomial-size circuits. P NP = P NP[1] ....
Lance Fortnow, Judy Goldsmith, Matthew A. Levy, Stephen Mahaney
A language is L-printable if there is a logspace algorithm which, on input 1 n prints all members in the language of length n. Following the work of Allender and Rubinstein [AR88] for P -printable...
Inverting Onto Functions (1996)
Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers
We look at the hypothesis that all honest onto polynomial-time computable functions have a polynomial-time computable inverse. We show this hypothesis equivalent to several other complexity...
Gap-Definability as a Closure Property (1996)
Stephen Fenner, Lance Fortnow, Lide Li
Gap-definability and the gap-closure operator were defined in [FFK94]. Few complexity classes were known at that time to be gap-definable. In this paper, we give simple characterizations of both...
Structure and Complexity (1996)
Uwe Schöning, Klaus W. Wagner, Farid Ablayev, Eric Allender, ...
S On the Power of Randomized Branching Programs Farid Ablayev Kazan University (joint work with Marek Karpinski, Universitat Bonn) We define a notion of randomized branching programs in a natural way...
Easy Sets Without Easy Small Subsets (1996)
We show the existence of relativized worlds relative to which there exist infinite polynomialtime computable sets without infinite polynomial-time computable sparse subsets or even...
On Inverting Onto Functions (1996)
Stephen Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers
We study the complexity of inverting many-one, honest, polynomial-time computable onto functions. Asserting that every polynomial-time computable, honest, onto function is invertible is equivalent to...
Inverting Onto Functions (1996)
Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D: Rogers, John D. Rogers
this paper we consider inverting the surjective (onto) functions. Grollmann and Selman showed that every one-to-one and onto function is invertible if and only if P = UP \ coUP, and Borodin and...
Lance Fortnow, Tomoyuki Yamakami
this paper fix \Sigma = f0; 1g. For a complexity class C we will often use the notation C(A) to represent the usual relativization of C to the oracle A.
Introduction Hemaspaandra, Hemaspaandra and Hempel [HHH96] showed that for k ? 2, if P \Sigma p k [2] tt = P \Sigma p k [1] then \Sigma p k = \Pi p k . We extend their techniques to show that if P...
Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space (1996)
We discuss the possibility of using the relatively old technique of diagonalization to separate complexity classes, in particular NL from NP. We show several results in this direction. ffl Any...
On Coherence, Random-Self-Reducibility, and Self-Correction (1996)
Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik
We address two questions about self-reducibility -- the power of adaptiveness in examiners that take advice and the relationship between random-self-reducibility and self-correctability. We first...
On Inverting Onto Functions (1996)
Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers
this paper, we study the complexity of inverting many-to-one onto functions. The hypothesis that all polynomial-time computable, honest, onto functions are invertible is equivalent to the following...
Two Results on Resource-Bounded Measure (1996)
Harry Buhrman, Stephen Fenner, Lance Fortnow
We construct an oracle relative to which NP has p-measure 0 but D p has measure 1 in EXP. This gives a strong relativized negative answer to a question posed by Lutz [Lut96]. Secondly, we give strong...
Extractors for Kolmogorov Complexity (1996)
Lance Fortnow, Sophie Laplante
We show two sets of results applying the theory of extractors to resource-bounded Kolmogorov complexity: --- Most strings in easy sets have nearly optimal polynomial-time CD complexity. This extends...
Inverting Onto Functions (1996)
Stephen Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers
We look at the hypothesis that all honest onto polynomial-time computable functions have a polynomial-time computable inverse. We show this hypothesis equivalent to several other complexity...
On Resource-Bounded Instance Complexity (1995)
The instance complexity of a string x with respect to a set A and time bound t, ic t (x : A), is the length of the shortest program for A that runs in time t, decides x correctly, and makes no...
Lance Fortnow, Tomoyuki Yamakami, Tomoyuki Yamakami
In 1987, Blum and Impagliazzo, using techniques of Hartmanis and Hemachandra and Rackoff, show that if P = NP then P(G) = NP(G) " coNP(G) = UP(G), where G is a generic oracle. They leave open...
Using Autoreducibility to Separate Complexity Classes (1995)
Harry Buhrman, Lance Fortnow, Leen Torenvliet
A language is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate exponential space from doubly...
Symmetric Logspace is Closed Under Complement (1995)
Noam Nisan, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 st connectivity problem to its complement. This shows that SL = coSL. 1 Introduction This paper deals with the complexity...
On the Weak mod m Representation of Boolean Functions (1995)
Vince Grolmusz, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
Let P be a polynomial over the ring of mod m integers. P weakly represents Boolean function f : f0; 1g n ! f0; 1g if there is a subset S ` f0; 1; : : : ; m \Gamma 1g such that f(x) = 0 if and only if...
On Coherence, Random-Self-Reducibility, and Self-Correction (1995)
Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik
We address two questions about self-reducibility the power of adaptiveness in examiners that take advice and the relationship between random-self-reducibility and self-correctability. We first show...
Resource-Bounded Instance Complexity (1995)
this paper we consider the resource-bounded version ic
Using Autoreducibility to Separate Complexity Classes (1995)
Harry Buhrman, Lance Fortnow, Leen Torenvliet
A language is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate exponential space from doubly...
Distinguishing Complexity and Symmetry of Information (1995)
We describe how to use polynomial-time Kolmogorov distinguishing complexity to give an approximate measure of the size of sets. For any set S, we show that relative to S the polynomial time...
Symmetric Logspace is Closed under Complement (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
[ii] Chicago Journal of Theoretical Computer Science 1995-3Rabin Measures (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
Published one article at a time in LATEX source form on the Internet. Pagination
The power of adaptiveness and additional queries in random-self-reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
1 We look at relationships between adaptive and nonadaptive random-self-reductions. We also look at what happens to random-self-reductions if we restrict the number of queries they are allowed to...
The Role of Relativization in Complexity Theory (1994)
Several recent nonrelativizing results in the area of interactive proofs have caused many people to review the importance of relativization. In this paper we take a look at how complexity theorists...
Extremes in the Degrees of Inferability (1994)
Lance Fortnow, William Gasarch, Sanjay Jain, Efim Kinber, Stuart Kurtz, ...
this paper we consider the scenario where the learner can ask a fellow student questions. Note that the other student does not know anything more about the function f than the learner; however, she...
Optimality and Domination in Repeated Games with Bounded Players (1994)
We examine questions of optimality and domination in repeated stage games where one or both players may draw their strategies only from (perhaps different) computationally bounded sets. We also...
The Power Of Adaptiveness And Additional Queries In Random-Self-Reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
. We study random-self-reductions from a structural complexity -theoretic point of view. Specifically, we look at relationships between adaptive and nonadaptive random-self-reductions. We also look...
The Isomorphism Conjecture Holds Relative to an Oracle (1994)
Stephen Fenner, Lance Fortnow, Stuart A. Kurtz
We introduce symmetric perfect generic sets. These sets vary from the usual generic sets by allowing limited infinite encoding into the oracle. We then show that the Berman-Hartmanis isomorphism...
Extremes in the Degrees of Inferability (1994)
Lance Fortnow Univ, Lance Fortnow, William Gasarch, Sanjay Jain, Efim Kinber, ...
this paper we consider the scenario where the learner can ask a fellow student questions. Note that the other student does not know anything more about the function f than the learner; however, she...
A Note on Adaptiveness and Advice in Coherence (1994)
Lance Fortnow, Sophie Laplante
Partially supported by NSF grant CCR 92--53582 y Partially supported by an NSERC doctoral fellowship 2 Deterministic examiners suffice First we show that if a function is nonadaptively weakly...
Optimality and Domination in Repeated Games with Bounded Players (1994)
We examine questions of optimality and domination in repeated stage games where one or both players may draw their strategies only from (perhaps different) computationally bounded sets. We also...
The Power Of Adaptiveness And Additional Queries In Random-Self-Reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
. We study random-self-reductions from a structural complexity -theoretic point of view. Specifically, we look at relationships between adaptive and nonadaptive random-self-reductions. We also look...
The Power of Adaptiveness and Additional Queries in Random-Self-Reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
. We study random-self-reductions from a structural complexity -theoretic point of view. Specifically, we look at relationships between adaptive and nonadaptive random-self-reductions. We also look...
Beating A Finite Automaton in the Big Match (1994)
We look at the Big Match game, a variation of the repeated Matching Pennies game where if the first player plays tails the game ends with the first player receiving the last round's payoff. We...
Two Remarks on Self-Correctability versus Random-Self-Reducibility (1994)
Joan Feigenbaum, Lance Fortnow, Ashish V. Naik
We examine the relationship between two types of probabilistic self-reductions that play crucial roles in the theory of interactive proof systems, program-checking, and programtesting:...
Extremes in the degrees of inferability (1994)
Lance Fortnow, Efim Kinber, Mark Pleszkoch, William Gasarch, Martin Kummer, Theodore Slaman, ...
Deutsche Forschungsgemeinschaft (DFG) grant Me 672/4-1 1 1
Extremes in the degrees of inferability (1994)
Lance Fortnow, Efim Kinber, Mark Pleszkoch, William Gasarch, Martin Kummer, Theodore Slaman, ...
Supported by the
An oracle builder's toolkit (1993)
Stephen Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li
We show how to use various notions of genericity as tools in oracle creation. In particular, 1. we give an abstract denition of genericity that encompasses a large collection of dierent generic...
Lance Fortnow, Joan Feigenbaum
. In this paper, we generalize the previous formal definitions of random-self-reducibility. We show that, even under our very general definition, sets that are complete for any level of the...
BPP has Subexponential Time Simulations unless EXPTIME has Publishable Proofs (1993)
László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson, Ma P
. We show that BPP can be simulated in subexponential time for infinitely many input lengths unless exponential time ffi collapses to the second level of the polynomial-time hierarchy, ffi has...
An Oracle Builder's Toolkit (1993)
An Oracle, Stephen Fenner, Stephen Fenner, Lance Fortnow, Lance Fortnow, Stuart A. Kurtz, ...
We show how to use various notions of genericity as a tool in oracle creation. We give an abstract definition of genericity that encompasses a large collection of different generic notions. We then...
Laszlo Babai, Noam Nissan, Lance Fortnow, Avi Wigderson
) L'aszl'o Babai Noam Nisan y Lance Fortnow z Avi Wigderson University of Chicago Hebrew University Abstract We show that BPP can be simulated in subexponential time for infinitely many...
On the Power of Two-Local Random Reductions (1992)
We show that any language that has a two-locally-random reduction in which the target functions are boolean is in NP/poly"co-NP/poly. This extends and simplifies a result by Yao. 1 Introduction...
Algebraic Methods for Interactive Proof Systems (1992)
Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan
We present a new algebraic technique for the construction of interactive proof systems. We use our technique to prove that every language in the polynomial-time hierarchy has an interactive proof...
Gap-Definability as a Closure Property (1992)
Stephen Fenner, Lance Fortnow, Lide Li
. Gap-definability and the gap-closure operator were defined in [FFK91]. Few complexity classes were known at that time to be gapdefinable. In this paper, we give simple characterizations of both...
PP is Closed Under Truth-Table Reductions (1991)
Beigel, Reingold and Spielman [2] showed that PP is closed under intersection and a variety of special cases of polynomial-time truth-table closure. We extend the techniques in [2] to show PP is...
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols (1991)
László Babai, Lance Fortnow, Carsten Lund
. We determine the exact power of two-prover interactive proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers...
Interactive Proof Systems And Alternating Time-Space Complexity (1991)
. We show a rough equivalence between alternating time-space complexity and a public-coin interactive proof system with the verifier having a polynomial related time-space complexity. Special cases...
Arithmetization: A New Method In Structural Complexity Theory (1991)
. We introduce a technique of arithmetization of the process of computation in order to obtain novel characterizations of certain complexity classes via multivariate polynomials. A variety of...
On The Random-Self-Reducibility Of Complete Sets (1991)
Joan Feigenbaum, Lance Fortnow
. In this paper, we generalize the previous formal definitions of random-self-reducibility. We show that, even under our very general definition, sets that are complete for any level of the...
Checking Computations in Polylogarithmic Time (1991)
László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy
. Motivated by Manuel Blum's concept of instance checking, we consider new, very fast and generic mechanisms of checking computations. Our results exploit recent advances in interactive proof...
PP is Closed Under Truth-Table Reductions (1991)
Beigel, Reingold and Spielman [BRS] showed that PP is closed under intersection and a variety of special cases of truth-table closure. We extend the techniques in [BRS] to show PP is closed under...
Algebraic Methods for Interactive Proof Systems (1990)
Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan
We present a new algebraic technique for the construc-tion of interactive proof systems. We use our technique to prove that every language in the polynomial-time hierarchy has an interactive proof...
Are There Interactive Protocols for Co-NP Languages? (1988)
This paper instead exhibits an oracle such that relative to this oracle there exists a language in co-NP that does not have an interactive protocol. From this we get that techniques which relativize...
On the Power of Multi-Prover Interactive Protocols (1988)
Lance Fortnow, John Rompel, Michael Sipser
this paper we consider a further generalization of the proof system model, due to Ben-Or, Goldwasser, Kilian and Wigderson [6], where instead of a single prover there may be many. This apparently...
The Complexity of Perfect Zero-Knowledge (1987)
A Perfect Zero-Knowledge interactive proof system convinces a verifier that a string is in a language without revealing any additional knowledge in an information-theoretic sense. We show that for...
Computational Identification of Operons in Microbial Genomes
Zheng, Yu, Szustakowski, Joseph D., Fortnow, Lance, Roberts, Richard J., Kasif, Simon
By applying graph representations to biochemical pathways, a new computational pipeline is proposed to find potential operons in microbial genomes. The algorithm relies on the fact that enzyme genes...
Computational Identification of Operons in Microbial Genomes
Zheng, Yu, Szustakowski, Joseph D., Fortnow, Lance, Roberts, Richard J., Kasif, Simon
By applying graph representations to biochemical pathways, a new computational pipeline is proposed to find potential operons in microbial genomes. The algorithm relies on the fact that enzyme genes...
The Complexity of Forecast Testing
Lance Fortnow, Rakesh V. Vohra
Consider a weather forecaster predicting a probability of rain for the next day. We consider tests that, given a finite sequence of forecast predictions and outcomes, will either pass or fail the...
My Favorite Ten Complexity Theorems of the Past Decade
We review the past ten years in computational complexity theory by focusing on ten theorems that the author enjoyed the most. We use each of the theorems as a springboard to discuss work done in...
Program Equilibria and Discounted Computation Time
Tennenholtz (GEB 2004) developed Program Equilibrium to model play in a finite two-player game where each player can base their strategy on the other player's strategies. Tennenholtz's model allowed...