Lance Fortnow

I&C Journal 2017 Journal Article

Robust simulations and significant separations

• Lance Fortnow
• Rahul Santhanam

We define a new notion of “robust simulations” between complexity classes which is intermediate between the traditional notions of infinitely-often and almost-everywhere, as well as a corresponding notion of “significant separations”. A language L has a robust simulation in a complexity class C if there is a language in C which agrees with L on arbitrarily large polynomial stretches of input lengths. We show that various implications in complexity theory such as the collapse of PH if NP = P and the Karp–Lipton theorem have analogues for robust simulations. We then use these results to prove that most known separations in complexity theory can be strengthened to significant separations, though in each case, an almost everywhere separation is unknown. Proving our results requires several new ideas, including a completely different proof of the hierarchy theorem for non-deterministic polynomial time than the ones previously known.

MFCS Conference 2013 Conference Paper

Learning Reductions to Sparse Sets

• Harry Buhrman
• Lance Fortnow
• John M. Hitchcock
• Bruno Loff

Abstract We study the consequences of NP having non-uniform polynomial size circuits of various types. We continue the work of Agrawal and Arvind [1] who study the consequences of Sat being many-one reducible to functions computable by non-uniform circuits consisting of a single weighted threshold gate. ( Sat \(\leq_m^p \mathrm{LT}_1\) ). They claim that P= NP follows as a consequence, but unfortunately their proof was incorrect. We take up this question and use results from computational learning theory to show that if Sat \(\leq_m^p \mathrm{LT}_1\) then PH = P NP. We furthermore show that if Sat disjunctive truth-table (or majority truth-table) reduces to a sparse set then Sat \(\leq_m^p\) LT 1 and hence a collapse of PH to P NP also follows. Lastly we show several interesting consequences of Sat \(\leq_{dtt}^p\) SPARSE.

I&C Journal 2011 Journal Article

Complexity classes of equivalence problems revisited

• Lance Fortnow
• Joshua A. Grochow

To determine if two lists of numbers are the same set, we sort both lists and see if we get the same result. The sorted list is a canonical form for the equivalence relation of set equality. Other canonical forms arise in graph isomorphism algorithms. To determine if two graphs are cospectral (have the same eigenvalues), we compute their characteristic polynomials and see if they are equal; the characteristic polynomial is a complete invariant for cospectrality. Finally, an equivalence relation may be decidable in P without either a complete invariant or canonical form. Blass and Gurevich (1984) asked whether these conditions on equivalence relations—having an FP canonical form, having an FP complete invariant, and being in P—are distinct. They showed that this question requires non-relativizing techniques to resolve. We extend their results, and give new connections to probabilistic and quantum computation.

I&C Journal 2011 Journal Article

Extracting Kolmogorov complexity with applications to dimension zero-one laws

• Lance Fortnow
• John M. Hitchcock
• A. Pavan
• N.V. Vinodchandran
• 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 number of advice bits to efficiently compute another string y, | y | = Ω ( | x | ), with K ( y ) > ( 1 - ϵ ) | y |. This result holds for both unbounded and space-bounded Kolmogorov complexity. We use the extraction procedure for space-bounded complexity to establish zero-one laws for the strong dimensions of complexity classes within ESPACE. The unbounded extraction procedure yields a zero-one law for the constructive strong dimensions of Turing degrees.

TARK Conference 2009 Conference Paper

A computational theory of awareness and decision making

• Nikhil R. Devanur
• Lance Fortnow

We exhibit a new computational-based definition of awareness, informally that our level of unawareness of an object is the amount of time needed to generate that object within a certain environment. We give several examples to show this notion matches our intuition in scenarios where one organizes, accesses and transfers information. We also give a formal process-independent definition of awareness based on Levin’s universal enumeration. We show the usefulness of computational awareness by showing how it relates to decision making, and how others can manipulate our decision making with appropriate advertising, in particular, we show connections to sponsored search and brand awareness. Understanding awareness can also help rate the effectiveness of various user interfaces designed to access information.

TARK Conference 2009 Conference Paper

Program equilibria and discounted computation time

• Lance Fortnow

Tennenholtz (GEB 2004) developed Program Equilibrium to model play in a finite twoplayer game where each player can base their strategy on the other player’s strategies. Tennenholtz’s model allowed each player to produce a “loop-free” computer program that had access to the code for both players. He showed a folk theorem where the result of any mixed-strategy individually rational play could be an equilibrium payoff in this model even in a one-shot game. Kalai et al. gave a general folk theorem for correlated play in a more generic commitment model. We develop a new model of program equilibrium using general computational models and discounting the payoffs based on the computation time used. We give an even more general folk theorem giving correlatedstrategy payoffs down to the pure minimax of each player. We also show the existence of equilibrium in other games not covered by the earlier work.

STOC Conference 2008 Conference Paper

Infeasibility of instance compression and succinct PCPs for NP

• 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 where the length of the output is bounded by a polynomial in n, unless NP ⊆ coNP/poly, and the Polynomial-Time Hierarchy collapses. This result settles an open problem proposed by Bodlaender et. al. [4] and Harnik and Naor [15] and has a number of implications. A number of parametric $\NP$ problems, including Satisfiability, Clique, Dominating Set and Integer Programming, are not instance compressible or polynomially kernelizable unless NP ⊆ coNP/poly. Satisfiability does not have PCPs of size polynomial in the number of variables unless NP ⊆ coNP/poly. An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is unlikely to be viable in its present form. (Buhrman-Hitchcock) There are no subexponential-size hard sets for NP unless NP is in co-NP/poly. We also study probabilistic variants of compression, and show various results about and connections between these variants. To this end, we introduce a new strong derandomization hypothesis, the Oracle Derandomization Hypothesis, and discuss how it relates to traditional derandomization assumptions.

TCS Journal 2006 Journal Article

Computational depth: Concept and applications

• Luis Antunes
• Lance Fortnow
• Dieter van Melkebeek
• N.V. Vinodchandran

We introduce Computational Depth, a measure for the amount of “nonrandom” or “useful” information in a string by considering the difference of various Kolmogorov complexity measures. We investigate three instantiations of Computational Depth: • Basic Computational Depth, a clean notion capturing the spirit of Bennett's Logical Depth. We show that a Turing machine M runs in time polynomial on average over the time-bounded universal distribution if and only if for all inputs x, M uses time exponential in the basic computational depth of x. • Sublinear-time Computational Depth and the resulting concept of Shallow Sets, a generalization of sparse and random sets based on low depth properties of their characteristic sequences. We show that every computable set that is reducible to a shallow set has polynomial-size circuits. • Distinguishing Computational Depth, measuring when strings are easier to recognize than to produce. We show that if a Boolean formula has a nonnegligible fraction of its satisfying assignments with low depth, then we can find a satisfying assignment efficiently.

MFCS Conference 2006 Conference Paper

Very Sparse Leaf Languages

• Lance Fortnow
• Mitsunori Ogihara

Abstract 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 language unless the polynomial hierarchy collapses to Θ \(^{p}_{\rm 2}\) and that Σ \(^{p}_{\rm 2}\) -complete sets are not polynomial-time bounded-truth-table reducible (respectively), polynomial-time Turing reducible) to any such balanced leaf language unless the polynomial hierarchy collapses to Δ \(^{p}_{\rm 2}\) (respectively, Σ \(^{p}_{\rm 4}\) ). This paper studies the complexity of the class of such balanced leaf languages, which will be denoted by VSLL. In particular, the following tight upper and lower bounds of VSLL are shown: 1. coNP ⊆ VSLL ⊆ coNP/poly (the former inclusion is already shown by Unger). 2. coNP/1 \(\not\subseteq\) VSLL unless PH = Θ \(^{p}_{\rm 2}\). 3. For all constant c >0, VSLL \(\not\subseteq\) coNP/ n c. 4. P/(loglog( n ) + O (1)) ⊆ VSLL. 5. For all h ( n ) = loglog( n ) + ω (1), P \(/h \not\subseteq\) VSLL.

STOC Conference 2005 Invited Paper

Beyond NP: the work and legacy of Larry Stockmeyer

• Lance Fortnow

TCS Journal 2005 Journal Article

Computation in a distributed information market

• 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 investigate the computational process on the path toward equilibrium, where information distributed among traders is revealed step-by-step over time and incorporated into the market price. We develop a simplified model of an information market, along with trading strategies, in order to formalize the computational properties of the process. We show that securities whose payoffs cannot be expressed as weighted threshold functions of distributed input bits are not guaranteed to converge to the proper equilibrium predicted by economic theory. On the other hand, securities whose payoffs are threshold functions are guaranteed to converge, for all prior probability distributions. Moreover, these threshold securities converge in at most n rounds, where n is the number of bits of distributed information. We also prove a lower bound, showing a type of threshold security that requires at least n / 2 rounds to converge in the worst case.

STOC Conference 2005 Conference Paper

Hierarchies for semantic classes

• Lance Fortnow
• Rahul Santhanam
• Luca Trevisan 0001

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 time classes including RTIME, NTIME ∩ coNTIME, UTIME, MATIME, AMTIME and BQTIME.We show a stronger hierarchy for RTIME: For every constant c, RP/1 is not contained in RTIME(n c )/(log n) 1/2c . To prove this result we first prove a similar statement for NP by building on Zák's proof of the nondeterministic time hierarchy.

FOCS Conference 2004 Conference Paper

Hierarchy Theorems for Probabilistic Polynomial Time

• Lance Fortnow
• Rahul Santhanam

We show a hierarchy for probabilistic time with one bit of advice, specifically we show that for all real numbers 1 /spl les/ /spl alpha/ /spl les/ /spl beta/, BPTIME(n/sup /spl alpha//)/l /spl sube/ BPTIME(n/sup /spl beta//)/l. This result builds on and improves an earlier hierarchy of Barak using O(log log n) bits of advice. We also show that for any constant d > 0, there is a language L computable on average in BPP but not on average in BPTIME (n/sup d/). We build on Barak's techniques by using a different translation argument and by a careful application of the fact that there is a PSPACE-complete problem L such that worst-case probabilistic algorithms for L take only slightly more time than average-case algorithms.

I&C Journal 2003 Journal Article

An oracle builder’s toolkit

• 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 definition of genericity that encompasses a large collection of different generic notions; 2. we consider a new complexity class AWPP, which contains BQP (quantum polynomial time), and infer several strong collapses relative to SP -generics; 3. we show that under additional assumptions these collapses also occur relative to Cohen generics; 4. we show that relative to SP -generics, ULIN∩co-ULIN⊈DTIME(n k ) for any k, where ULIN is unambiguous linear time, despite the fact that UP∪(NP∩co-NP)⊆P relative to these generics; 5. we show that there is an oracle relative to which NP/1∩co-NP/1⊈(NP∩co-NP)/poly; and 6. we use a specialized notion of genericity to create an oracle relative to which NP BPP ⊉ MA.

I&C Journal 2003 Journal Article

Inverting onto functions

• 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 conjectures including: • In polynomial time, one can find accepting paths of nondeterministic polynomial-time Turing machines that accept Σ*. • Every total multivalued nondeterministic function has a polynomial-time computable refinement. • In polynomial time, one can compute satisfying assignments for any polynomial-time computable set of satisfiable formulae. • In polynomial time, one can convert the accepting computations of any nondeterministic Turing machine that accepts SAT to satisfying assignments. We compare these hypotheses with several other important complexity statements. We also examine the complexity of these statements where we only require a single bit instead of the entire inverse.

TCS Journal 2003 Journal Article

One complexity theorist's view of quantum computing

• Lance Fortnow

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 useful these machines will be. The tools of computational complexity theory should come to bear on these important questions. Quantum computing often scares away many potential researchers in computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic. This paper will give an overview of quantum computation from the point of view of a complexity theorist. We will see that one can think of BQP as yet another complexity class and study its power without focusing on the physical aspects behind it.

SODA Conference 2003 Conference Paper

Quantum property testing

• Harry Buhrman
• Lance Fortnow
• Ilan Newman
• Hein Röhrig

SODA Conference 2003 Conference Paper

Sublinear-time approximation of Euclidean minimum spanning tree

• Artur Czumaj
• Funda Ergün
• Lance Fortnow
• Avner Magen
• Ilan Newman
• Ronitt Rubinfeld
• Christian Sohler

TCS Journal 2003 Journal Article

Uniformly hard languages

• Rod Downey
• Lance Fortnow

Ladner (J. Assoc. Comput. Mach. 22 (1975) 155) 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 in P. The set B does have very long sequences of input lengths of easily computable instances. We examine whether Ladner's results hold if we restrict ourselves to “uniformly hard languages” which have no long sequences of easily computable instances. Under a hard to disprove assumption, we show that there exists a minimal recursive uniformly hard set under honest many-one polynomial-time reductions.

FOCS Conference 2001 Conference Paper

Testing Random Variables for Independence and Identity

• Tugkan Batu
• Lance Fortnow
• Eldar Fischer
• Ravi Kumar 0001
• Ronitt Rubinfeld
• Patrick White

Given access to independent samples of a distribution A over [n] /spl times/ [m], we show how to test whether the distributions formed by projecting A to each coordinate are independent, i. e. , whether A is /spl epsi/-close in the L/sub 1/ norm to the product distribution A/sub 1//spl times/A/sub 2/ for some distributions A/sub 1/ over [n] and A/sub 2/ over [m]. The sample complexity of our test is O/spl tilde/(n/sup 2/3/m/sup 1/3/poly(/spl epsi//sup -1/)), assuming without loss of generality that m/spl les/n. We also give a matching lower bound, up to poly (log n, /spl epsi//sup -1/) factors. Furthermore, given access to samples of a distribution X over [n], we show how to test if X is /spl epsi/-close in L/sub 1/ norm to an explicitly specified distribution Y. Our test uses O/spl tilde/(n/sup 1/2/poly(/spl epsi//sup -1/)) samples, which nearly matches the known tight bounds for the case when Y is uniform.

FOCS Conference 2000 Conference Paper

Testing that distributions are close

• 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/sup 2/3//spl epsiv//sup -4/ log n) independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the cases when the distance between the distributions is small (less than max(/spl epsiv//sup 2//32/sup 3//spl radic/n, /spl epsiv//4/spl radic/n=)) or large (more than /spl epsiv/) in L/sub 1/-distance. We also give an /spl Omega/(n/sup 2/3//spl epsiv//sup -2/3/) lower bound. Our algorithm has applications to the problem of checking whether a given Markov process is rapidly mixing. We develop sublinear algorithms for this problem as well.

TARK Conference 1998 Conference Paper

Beating a Finite Automaton in the Big Match

• Lance Fortnow
• Peter G. Kimmel

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 study this game when the second player js implemented as a finite automaton. We show several results including: • If the first player knows the number of states of the second player's automaton then he can achieve the maximum score with a deterministic polynomial-time algorithm. • If a deterministic first player does not know the number of states of the second player then he can not guarantee himself more than the minimum score. • If we allow player one to run in probabilistic polynomial-time then he still cannot achieve the maximum score but he can get arbitrarily close. • In a slight variation of the Big Match, the first player cannot have an even close to dominant strategy.

STOC Conference 1998 Conference Paper

NP Might Not Be As Easy As Detecting Unique Solutions

• Richard Beigel
• Harry Buhrman
• Lance Fortnow

TCS Journal 1998 Journal Article

On the relative sizes of learnable sets

• Lance Fortnow
• Rūsiņs̆ Freivalds
• William I. Gasarch
• Martin Kummer
• 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”. We use the notions of effective measure and category to discuss the relative sizes of inferrible sets, and their complements. We find that inferable sets become large rather quickly in the standard hierarchies of learnability. On the other hand, the complements of the learnable sets are all large.

STOC Conference 1997 Conference Paper

Retraction of Probabilistic Computation and Linear Time

• Lance Fortnow
• Michael Sipser

I&C Journal 1996 Journal Article

Gap-Definability as a Closure Property

• Stephen Fenner
• Lance Fortnow
• Lide Li

Gap-definability and the gap closure operator were defined by S. Fenner, L. Fortnow and S. Kurth (J. Comput. System Sci. 48, 116–148 (1994)). Few complexity classes were known at that time to be gap-definable. In this paper, we give simple characterizations of both gap-definability and the gap-closure operator, and we show that many complexity classes are gap-definable, includingP #P, P #P[1], PSPACE, EXP, NEXP, MP(Middle-bitP), andBP·⊕P. If a class is closed under union and intersection and contains ∅ andΣ*, then it is gap-definable if and only if it containsSPP; its gap-closure is the closure of this class together withSPPunder union and intersection. On the other hand, we give some examples of classes which are reasonable and gap-definable but not closed under union (resp. intersection, complement). Finally, we show that a complexity class such asPSPACEorPP, if it is not equal toSPP, contains a maximal gap-definable many–one reduction-closed subclass, which is properly betweenSPPand the class of allPSPACE-incomplete (PP-incomplete) sets with respect to containment. The gap-closure of the class of all incomplete sets inPSPACE(resp. PP) isPSPACE(resp. PP).

TCS Journal 1996 Journal Article

On resource-bounded instance complexity

• Lance Fortnow
• Martin Kummer

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 mistakes on other strings (where “do not know” answers are permitted). The instance complexity conjecture of Ko, Orponen, Schöning, and Watanabe (1986) states that for every recursive set A not in P and every polynomial t there is a polynomial t′ and a constant c such that for infinitely many x, ic t (x: A) ⩾ C t′ (x) − c, where C t′ (x) is the t′-time bounded Kolmogorov complexity of x. In this paper the conjecture is proved for all recursive tally sets and for all recursive sets which are NP-hard under honest reductions, in particular it holds for all natural NP-hard problems. The method of proof also yields the polynomialspace bounded and the exponential-time bounded versions of the conjecture in full generality. On the other hand, the conjecture itself turns out to be oracle dependent: In any relativized world where P = NP the conjecture holds, but there are also relativized worlds where it fails, even if C-complexity is replaced by Sipser's CD-complexity. Additionally it is proved that the instance complexity measure is noncomputable and it is investigated whether for every polynomial t there is a polynomial t′ such that C t′-complexity is bounded above by CDt -complexity.

I&C Journal 1996 Journal Article

PP Is Closed under Truth-Table Reductions

• Lance Fortnow
• Nick Reingold

Beigel, Reingold, and Spielman (J. Comput. System Sci. 50, 191–202 (1995)) showed that PP is closed under intersection and a variety of special cases of polynomial-time truth-table closure. We extend their techniques to show that PP is closed under general polynomial-time truth-table reductions. We also show that PP is closed under constant-round truth-table reductions.

FOCS Conference 1995 Conference Paper

Using Autoreducibility to Separate Complexity Classes

• 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 exponential space by showing that all Turing complete sets for exponential space are autoreducible but there exists some Turing complete set for doubly exponential space that is not. We immediately also get a separation of logarithmic space from polynomial space. Although we already know how to separate these classes using diagonalization, our proofs separate classes solely by showing they have different structural properties, thus applying Post's Program (E. Pos, 1944) to complexity theory. We feel such techniques may prove unknown separations in the future. In particular if we could settle the question as to whether all complete sets for doubly exponential time were autoreducible we would separate polynomial time from either logarithmic space or polynomial space. We also show several other theorems about autoreducibility.

TCS Journal 1994 Journal Article

On the power of multi-prover interactive protocols

• Lance Fortnow
• John Rompel
• Michael Sipser

We look at complexity issues of interactive proof systems with multiple provers separated from each other. This model, developed by Ben-Or et al. (1988) allows the verifier to play the provers off each other. We show this model equivalent to an alternative interactive proof system model using oracles as provers. We also show that every language accepted by these models lies in nondeterministic exponential time. We exhibit a relativized world where a co-NP language does not have multiple prover interactive proofs. Finally, we show a simple example that one cannot parallelize multiple prover protocols as easily as the single prover model.

STOC Conference 1994 Conference Paper

Optimality and domination in repeated games with bounded players

• Lance Fortnow
• Duke Whang

TCS Journal 1993 Journal Article

Interactive proof systems and alternating time—space complexity

• Lance Fortnow
• Carsten Lund

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 include the following: • All of NC has interactive proofs, with a log-space polynomial-time public-coin verifier vastly improving the best previous lower bound of LOGCFL for this model (Fortnow and Sipser, 1988). • All languages in P have interactive proofs with a polynomial-time public-coin verifier using o(log2 n) space. • All exponential-time languages have interactive proof systems with public-coin polynomial-space exponential-time verifiers. To achieve better bounds, we show how to reduce a k-tape alternating Turing machine to a 1-tape alternating Turing machine with only a constant factor increase in time and space.

FOCS Conference 1992 Conference Paper

The Isomorphism Conjecture Holds Relative to an Oracle

• Stephen A. Fenner
• Lance Fortnow
• Stuart A. Kurtz

The authors introduce symmetric perfect generic sets. these sets vary from the usual generic sets by allowing limited infinite encoding into the oracle. They then show that the Berman-Hartmanis (1977) isomorphism conjecture holds relative to any sp-generic oracle, i. e. , for any symmetric perfect generic set A, all NP/sup A/-complete sets are polynomial-time isomorphic relative to A. As part of the proof that the isomorphism conjecture holds relative to symmetric perfect generic sets they also show that P/sup A/=FewP/sup A/ for any symmetric perfect generic/sup /A. >

STOC Conference 1991 Conference Paper

Checking Computations in Polylogarithmic Time

• László Babai
• Lance Fortnow
• Leonid A. Levin
• Mario Szegedy

FOCS Conference 1990 Conference Paper

A Characterization of \sharp P Arithmetic Straight Line Programs

• László Babai
• Lance Fortnow

Hash P functions are characterized by certain straight-line programs of multivariate polynomials. The power of this characterization is illustrated by a number of consequences. These include a somewhat simplified proof of S. Toda's (1989) theorem that PH contained in P/sup Hash P/, as well as an infinite class of potentially inequivalent checkable functions. >

FOCS Conference 1990 Conference Paper

Algebraic Methods for Interactive Proof Systems

• Carsten Lund
• Lance Fortnow
• Howard J. Karloff
• Noam Nisan

An algebraic technique for the construction of interactive proof systems is proposed. The technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. For the proof, a method is developed for reducing the problem of verifying the value of a low-degree polynomial at two points to verifying the value at one new point. The results have implications for program checking, verification, and self-correction. >

FOCS Conference 1990 Conference Paper

Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols

• László Babai
• Lance Fortnow
• Carsten Lund

The exact power of two-prover interactive proof systems (MIP) introduced by M. Ben-Or et al. (Proc. 20th Symp. on Theory of Computing, 1988, p. 113-31) is determined. In this system, two all-powerful noncommunicating provers convince a randomizing polynomial-time verifier in polynomial time that the input x belongs to the language L. It was previously suspected (and proved in a relativized sense) that coNP-complete languages do not admit such proof systems. In sharp contrast, it is shown that the class of languages having two-prover interactive proof systems is computable in nondeterministic exponential time (NEXP). This represents a further step demonstrating the unexpectedly immense power for randomization and interaction in efficient provability. >

STOC Conference 1987 Conference Paper

The Complexity of Perfect Zero-Knowledge (Extended Abstract)

• Lance Fortnow