We prove an unexpected upper bound on a communication game proposed
by Jeff Edmonds and Russell Impagliazzo as an approach for
proving lower bounds for time-space tradeoffs for branching programs.
Our result is based on a generalization of a construction of Erdos,
Frankl and Rodl of a large 3-hypergraph with ... more >>>

We obtain the first non-trivial time-space tradeoff lower bound for
functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a
Boolean function f that requires exponential size to be computed by any
branching program of length cn, for some constant c>1. We also give the first
separation result between the ... more >>>

We prove the first time-space lower bound tradeoffs for randomized
computation of decision problems. The bounds hold even in the
case that the computation is allowed to have arbitrary probability
of error on a small fraction of inputs. Our techniques are an
extension of those used by Ajtai in his ... more >>>

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.

We extend the lower bound techniques of [Fortnow], to the
unbounded-error probabilistic model. A key step in the argument
is a generalization of Nepomnjascii's theorem from the Boolean
setting to the arithmetic setting. This generalization is made
possible, due to the recent discovery of logspace-uniform TC^0
more >>>

We consider uniform assumptions for derandomization. We provide
intuitive evidence that BPP can be simulated non-trivially in
deterministic time by showing that (1) P \not \subseteq i.o.i.PLOYLOGSPACE
implies BPP \subseteq SUBEXP (2) P \not \subseteq SUBPSPACE implies BPP
= P. These results extend and complement earlier work of ... more >>>

We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for Sat. Let m be a positive integer, and define MODm-Sat to be the problem of determining if a given Boolean formula has ... more >>>

Ever since the fundamental work of Cook from 1971, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time, logarithmic-space algorithm for satisfiability was not ruled out. In 1997 Fortnow, building on earlier work by ... more >>>

A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space.

In this paper we resolve the question by answering ... more >>>

We prove a time-space tradeoff lower bound of $T =
\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ for
randomized oblivious branching programs to compute $1GAP$, also
known as the pointer jumping problem, a problem for which there is a
simple deterministic time $n$ and space $O(\log n)$ RAM (random
access machine) algorithm.

In ... more >>>