Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Lance Fortnow:

TR14-171 | 11th December 2014
Lance Fortnow, Rahul Santhanam

Hierarchies Against Sublinear Advice

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

TR09-064 | 3rd August 2009
Harry Buhrman, Lance Fortnow, Rahul Santhanam

Unconditional Lower Bounds against Advice

We show several unconditional lower bounds for exponential time classes
against polynomial time classes with advice, including:
\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)}$

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

TR08-046 | 14th April 2008
Nikhil R. Devanur, Lance Fortnow

A Computational Theory of Awareness and Decision Making

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

TR07-096 | 8th October 2007
Lance Fortnow, Rahul Santhanam

Infeasibility of Instance Compression and Succinct PCPs for NP

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

TR07-004 | 12th January 2007
Lance Fortnow, Rahul Santhanam

Time Hierarchies: A Survey

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

more >>>

TR06-157 | 14th December 2006
Lance Fortnow, Rahul Santhanam

Fixed-Polynomial Size Circuit Bounds

We explore whether various complexity classes can have linear or
more generally $n^k$-sized circuit families for some fixed $k$. We

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

TR06-149 | 7th December 2006
Lance Fortnow, Rakesh Vohra

The Complexity of Forecast Testing

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

TR06-125 | 20th September 2006
Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto

Low-Depth Witnesses are Easy to Find

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

TR06-024 | 18th February 2006
Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin

Inverting onto functions might not be hard

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

TR05-144 | 5th December 2005
Lance Fortnow, Luis Antunes

Time-Bounded Universal Distributions

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

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

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

TR05-042 | 15th April 2005
Lance Fortnow, Adam Klivans

Linear Advice for Randomized Logarithmic Space

Revisions: 1

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.

more >>>

TR04-105 | 19th November 2004
Eldar Fischer, Lance Fortnow

Tolerant Versus Intolerant Testing for Boolean Properties

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

TR04-103 | 19th November 2004
Lance Fortnow, Adam Klivans

NP with Small Advice

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

TR04-098 | 5th November 2004
Lance Fortnow, Rahul Santhanam, Luca Trevisan

Promise Hierarchies

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,

We show a ... more >>>

TR04-081 | 9th September 2004
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin

Increasing Kolmogorov Complexity

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
Omega(sqrt(n)) bit flips. For a given m, we also give bounds for ... more >>>

TR04-080 | 7th September 2004
Lance Fortnow, Troy Lee, Nikolay Vereshchagin

Kolmogorov Complexity with Error

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

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

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

TR04-001 | 11th December 2003
Lance Fortnow, Russell Impagliazzo, Chris Umans

On the complexity of succinct zero-sum games

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

TR03-087 | 10th December 2003
Richard Beigel, Lance Fortnow, William Gasarch

A Nearly Tight Bound for Private Information Retrieval Protocols

Comments: 1

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

TR00-028 | 17th April 2000
Lance Fortnow, Dieter van Melkebeek

Time-Space Tradeoffs for Nondeterministic Computation

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

more >>>

TR94-021 | 12th December 1994
Lance Fortnow

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
various areas of complexity theory.

more >>>

ISSN 1433-8092 | Imprint