Arrow Research search

Author name cluster

Lance Fortnow

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

31 papers
2 author rows

Possible papers

31

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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. >

Details

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. >

Details

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. >

Details

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. >

Details