Journal of the ACM Bibliography

Categories and Subject Descriptors: F.1.3 [Computation by Abstract Devices]: Complexity Classes -- relations among complexity classes; F.2.3 [Analysis of Algorithms and Problem Complexity]: Tradeoffs among Complexity Measures; G.2.2 [Discrete Mathematics]: Graph Theory

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Lower bounds, pebble game, superconcentrators

Selected references

• Ashok K. Chandra. Efficient compilation of linear recursive programs. In 14th Annual Symposium on Switching and Automata Theory, pages 16-25, The University of Iowa, 15-17 October 1973. IEEE.

• Ofer Gabber and Zvi Galil. Explicit constructions of linear size superconcentrators. In 20th Annual Symposium on Foundations of Computer Science, pages 364-370, San Juan, Puerto Rico, 29-31 October 1979. IEEE.

• John Hopcroft, Wolfgang Paul, and Leslie Valiant. On time versus space. Journal of the ACM, 24(2):332-337, April 1977.

• Joseph Ja' Ja'. Time-space tradeoffs for some algebraic problems. In Conference Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pages 339-350, Los Angeles, California, 28-30 April 1980.

• Thomas Lengauer and Robert Endre Tarjan. Upper and lower bounds on time-space tradeoffs. In Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing, pages 262-277, Atlanta, Georgia, 30 April-2 May 1979.

• W. J. Paul. On time hierarchies. In Conference Record of the Ninth Annual ACM Symposium on Theory of Computing, pages 218-222, Boulder, Colorado, 2-4 May 1977.

• Nicholas Pippenger. A time-space trade-off. Journal of the ACM, 25(3):509-515, July 1978.

• Nicholas Pippenger. Comparative schematology and pebbling with auxiliary pushdowns (preliminary version). In Conference Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pages 351-356, Los Angeles, California, 28-30 April 1980.

• Rüdiger Reischuk. Improved bounds on the problem of time-space trade-off in the pebble game. Journal of the ACM, 27(4):839-849, October 1980.

• Martin Tompa. Time-space tradeoffs for computing functions, using connectivity properties of their circuits. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, pages 196-204, San Diego, California, 1-3 May 1978.

• Martin Tompa. Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations. In Conference Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pages 333-338, Los Angeles, California, 28-30 April 1980.

Shortcuts: