All reports by Author Lance Fortnow:

__
TR14-171
| 11th December 2014
__

Lance Fortnow, Rahul Santhanam#### Hierarchies Against Sublinear Advice

__
TR09-064
| 3rd August 2009
__

Harry Buhrman, Lance Fortnow, Rahul Santhanam#### Unconditional Lower Bounds against Advice

__
TR08-046
| 14th April 2008
__

Nikhil R. Devanur, Lance Fortnow#### A Computational Theory of Awareness and Decision Making

__
TR07-096
| 8th October 2007
__

Lance Fortnow, Rahul Santhanam#### Infeasibility of Instance Compression and Succinct PCPs for NP

__
TR07-004
| 12th January 2007
__

Lance Fortnow, Rahul Santhanam#### Time Hierarchies: A Survey

__
TR06-157
| 14th December 2006
__

Lance Fortnow, Rahul Santhanam#### Fixed-Polynomial Size Circuit Bounds

__
TR06-149
| 7th December 2006
__

Lance Fortnow, Rakesh Vohra#### The Complexity of Forecast Testing

__
TR06-125
| 20th September 2006
__

Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto#### Low-Depth Witnesses are Easy to Find

__
TR06-024
| 18th February 2006
__

Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin#### Inverting onto functions might not be hard

__
TR05-144
| 5th December 2005
__

Lance Fortnow, Luis Antunes#### Time-Bounded Universal Distributions

__
TR05-105
| 24th September 2005
__

Lance Fortnow, John Hitchcock, A. Pavan, Vinodchandran Variyam, Fengming Wang#### Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

__
TR05-042
| 15th April 2005
__

Lance Fortnow, Adam Klivans#### Linear Advice for Randomized Logarithmic Space

Revisions: 1

__
TR04-105
| 19th November 2004
__

Eldar Fischer, Lance Fortnow#### Tolerant Versus Intolerant Testing for Boolean Properties

__
TR04-103
| 19th November 2004
__

Lance Fortnow, Adam Klivans#### NP with Small Advice

__
TR04-098
| 5th November 2004
__

Lance Fortnow, Rahul Santhanam, Luca Trevisan#### Promise Hierarchies

__
TR04-081
| 9th September 2004
__

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin#### Increasing Kolmogorov Complexity

__
TR04-080
| 7th September 2004
__

Lance Fortnow, Troy Lee, Nikolay Vereshchagin#### Kolmogorov Complexity with Error

__
TR04-015
| 24th February 2004
__

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet#### Enumerations of the Kolmogorov Function

__
TR04-001
| 11th December 2003
__

Lance Fortnow, Russell Impagliazzo, Chris Umans#### On the complexity of succinct zero-sum games

__
TR03-087
| 10th December 2003
__

Richard Beigel, Lance Fortnow, William Gasarch#### A Nearly Tight Bound for Private Information Retrieval Protocols

Comments: 1

__
TR00-028
| 17th April 2000
__

Lance Fortnow, Dieter van Melkebeek#### Time-Space Tradeoffs for Nondeterministic Computation

__
TR94-021
| 12th December 1994
__

Lance Fortnow#### My Favorite Ten Complexity Theorems of the Past Decade

Lance Fortnow, Rahul Santhanam

We strengthen the non-deterministic time hierarchy theorem of

\cite{Cook72, Seiferas-Fischer-Meyer78, Zak83} to show that the lower bound

holds against sublinear advice. More formally, we show that for any constants

$c$ and $d$ such that $1 \leq c < d$, there is a language in $\NTIME(n^d)$

which is not in $\NTIME(n^c)/n^{1/d}$. ...
more >>>

Harry Buhrman, Lance Fortnow, Rahul Santhanam

We show several unconditional lower bounds for exponential time classes

against polynomial time classes with advice, including:

\begin{enumerate}

\item For any constant $c$, $\NEXP \not \subseteq \P^{\NP[n^c]}/n^c$

\item For any constant $c$, $\MAEXP \not \subseteq \MA/n^c$

\item $\BPEXP \not \subseteq \BPP/n^{o(1)}$

\end{enumerate}

It was previously unknown even whether $\NEXP \subseteq ... more >>>

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

more >>>

Lance Fortnow, Rahul Santhanam

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there

is a polynomial-time computable function $f$ and a set $A$ such that

for each instance ...
more >>>

Lance Fortnow, Rahul Santhanam

We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes.

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

1) The following are equivalent,

- NP is in SIZE(n^k) (has O(n^k)-size circuit families) for some k

- P^NP|| is in SIZE(n^k) for some k

- ONP/1 is in ...
more >>>

Lance Fortnow, Rakesh 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

forecaster. Sandroni (2003) shows that any test which passes a

forecaster who knows the distribution of nature, can ...
more >>>

Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre 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 traditional Kolmogorov complexity We show how to

find satisfying assignments for formulas that have at least one

assignment of logarithmic depth. The converse holds under a

standard ...
more >>>

Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin

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 functions are

hard, for example, if TFNP is computable in polynomial-time does

this imply the polynomial-time hierarchy collapses?

We give a relativized ... more >>>

Lance Fortnow, Luis Antunes

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 running time of languages that are in average polynomial-time over all P-samplable distributions.

more >>>Lance Fortnow, John Hitchcock, A. Pavan, Vinodchandran Variyam, Fengming Wang

We apply recent results on extracting randomness from independent

sources to ``extract'' Kolmogorov complexity. For any $\alpha,

\epsilon > 0$, given a string $x$ with $K(x) > \alpha|x|$, we show

how to use a constant number of advice bits to efficiently

compute another string $y$, $|y|=\Omega(|x|)$, with $K(y) >

(1-\epsilon)|y|$. ...
more >>>

Lance Fortnow, Adam Klivans

We show that RL is contained in 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

prove our result we show how to take an ultra-low space walk on

the Gabber-Galil expander graph.

Eldar Fischer, Lance Fortnow

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

and Rubinfeld, must also accept inputs that are close enough to satisfying the property. We

construct properties of binary functions ...
more >>>

Lance Fortnow, Adam Klivans

We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP in NP/log if and only if EXP = P^NP|| (polynomial time with non-adaptive queries to SAT). Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in ... more >>>

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 all the common

promise time classes including RTIME, NTIME \cap coNTIME, UTIME,

MATIME, AMTIME and BQTIME.

We show a ... more >>>

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin

How much do we have to change a string to increase its Kolmogorov complexity. We show that we can

increase the complexity of any non-random string of length n by flipping O(sqrt(n)) bits and some strings

require

Omega(sqrt(n)) bit flips. For a given m, we also give bounds for ...
more >>>

Lance Fortnow, Troy Lee, Nikolay Vereshchagin

We introduce the study of Kolmogorov complexity with error. For a

metric d, we define C_a(x) to be the length of a shortest

program p which prints a string y such that d(x,y) \le a. We

also study a conditional version of this measure C_{a,b}(x|y)

where the task is, given ...
more >>>

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

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 among the first $k(n)$ elements enumerated by $f$.

If there is a $k(n)$-enumerator for ...
more >>>

Lance Fortnow, Russell Impagliazzo, Chris 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 $\EXP$-hardness

of computing the \emph{exact} value of a succinct zero-sum game by

several results on \emph{approximating} the value. (1) ...
more >>>

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

$n-1$ upper bound. This improves upon the approximately $0.25n$ lower

bound of Kerenidis and de Wolf while ...
more >>>

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 improves recent results of Lipton and Viglas and

Fortnow.

Lance Fortnow

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

various areas of complexity theory.