|
|
|
|
|
Time-Space Tradeoffs
For many natural problems, such as sorting or matrix-multiplication, there are
many choices of algorithms
to use, some of which are extremely space-efficient and others of which are
extremely time-efficient. This is an instance of a general phenomenon where one
can often save space by recomputing intermediate results.
Research in time-space tradeoff lower bounds seeks to prove that, for certain
problems, no algorithms exist that achieve small space and small time
simultaneously.
Another key motivation for studying time-space tradeoffs is as a step towards
showing that there are problems in P (or even NP) that do not have small
space algorithms (algorithms in L).
Our results include optimal time-space tradeoffs for sorting, the
first-ever time-space tradeoff lower bounds for randomized computation
of decision problems in NP, and the currently best tradeoff lower bounds
know for any problem.
Publications
- Paul Beame and Erik Vee.
Time-space
tradeoffs, multiparty communication complexity, and nearest-neighbor
problems.
In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of
Computing, pages 688-697, Montreal, Quebec, Canada, May 2002.
- Paul Beame,
Michael Saks, Xiaodong Sun, and Erik Vee.
Time-space tradeoff lower bounds for randomized computation of decision problems.
Journal of the ACM, 2002.
To appear.
- Paul Beame,
T. S. Jayram, and Michael Saks.
Time-space
tradeoffs for branching programs.
Journal of Computer and System Sciences, 63(4):542-572, December
2001.
Special issue of selected papers from 1998 FOCS Conference.
- Paul Beame,
Michael Saks, Xiaodong Sun, and Erik Vee.
Super-linear time-space tradeoff lower bounds for randomized computation.
In Proceedings 41st Annual Symposium on Foundations of Computer
Science, pages 169-179, Redondo Beach, CA, November 2000. IEEE.
- Paul Beame,
Michael Saks, Xiaodong Sun, and Erik Vee.
Super-linear time-space tradeoff lower bounds for randomized computation.
Technical Report TR00-025, Electronic Colloquium in Computation Complexity,
2000.
- Paul Beame, Allan Borodin,
Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
A time-space tradeoff
for undirected graph traversal by walking automata.
SIAM Journal on Computing, 28(3):1051-1072, 1999.
- Paul Beame, Michael
Saks, and Jayram S. Thathachar.
Time-space tradeoffs for branching programs.
In Proceedings 39th Annual Symposium on Foundations of Computer
Science, pages 254-263, Palo Alto, CA, November 1998. IEEE.
- Paul Beame,
Michael Saks, and Jayram S. Thathachar.
Time-space tradeoffs for branching programs.
Technical Report TR98-053, Electronic Colloquium in Computation Complexity,
1998.
- Paul Beame, Allan Borodin,
Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
Time-space tradeoffs for undirected graph traversal by graph automata.
Information and Computation, 130(2):101-129, November 1996.
- Paul Beame, Martin
Tompa, and Peiyuan Yan.
Communication-space
tradeoffs for unrestricted protocols.
SIAM Journal on Computing, 23(3):652-661, 1994.
- Paul Beame, Allan
Borodin, Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
Time-space
tradeoffs for undirected graph traversal.
Technical Report UW-CSE-93-02-01, Department of Computer Science and
Engineering, University of Washington, February 1993.
- Paul Beame.
A general sequential time-space tradeoff for finding unique elements.
SIAM Journal on Computing, 20(2):270-277, 1991.
- Paul Beame, Allan
Borodin, Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
Time-space tradeoffs for undirected graph traversal.
In Proceedings 31st Annual Symposium on Foundations of Computer
Science, pages 429-438, St. Louis, MO, October 1990. IEEE.
- Paul Beame,
Martin Tompa, and Peiyuan Yan.
Communication-space tradeoffs for unrestricted protocols.
In Proceedings 31st Annual Symposium on Foundations of Computer
Science, pages 420-428, St. Louis, MO, October 1990. IEEE.
- Paul Beame,
Martin Tompa, and Peiyuan Yan.
Communication-space tradeoffs for unrestricted protocols.
Technical Report UW-CSE-90-01-12, Department of Computer Science and
Engineering, University of Washington, January 1990.
- Paul Beame.
A general sequential time-space tradeoff for finding unique elements.
In Proceedings of the Twenty-First Annual ACM Symposium on Theory of
Computing, pages 197-203, Seattle, WA, May 1989.
- Paul Beame.
A general sequential time-space tradeoff for finding unique elements.
Technical Report UW-CSE-88-10-04, Department of Computer Science and
Engineering, University of Washington, October 1988.
|
CSE Home
