On notions of information transfer in VLSI circuits

ABSTRACT

Several papers have recently dealt with techniques for proving area-time lower bounds for VLSI computation by “crossing sequence” methods. A number of natural questions are raised by these definitions. 1.Is the fooling set approach the most powerful way to get information-transfer-based lower bounds? We shall show it is not, and offer a candidate for the title “most powerful.” Of course, without a precise definition of “information transfer argument,” there could be other contenders. 2.Are the notions of the three papers cited equivalent? We shall exhibit certain inequivalences among the three notions, although open questions remain. However, we can resolve an open question of Papadimitriou and Sipser [PS] concerning the relationship between nondeterministic and deterministic communication complexity.

REFERENCES

• 1: Kedem, Z. M., "Optimal allocation of computational resources in VLSI," Proc. Twenty-Third Annual IEEE Symposium on Foundations of Computer Science, pp. 379-386, 1982.
• 2: Richard J. Lipton , Robert Sedgewick, Lower bounds for VLSI, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.300-307, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802482]
• 3: Kurt Mehlhorn , Erik M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.330-337, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802208]
• 4: Orlin, J., "Contentment in graph theory: covering graphs with cliques," Proc. Koninklijke Nederlandse Akademie van Wetenschappen, Amsterdam series A 80:5, pp. 406-424, 1977.
• 5: Christos H. Papadimitriou , Michael Sipser, Communication complexity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.196-200, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802192]
• 6: Savage, J. E., "Planar circuit complexity and the performance of VLSI algorithms," in Kung, Sproull, and Steele (eds.), VLSI Systems and Computations, Computer Science Press, Rockville, Md., 1981.
• 7: C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
• 8: Vuillemin, J. E., "A combinatorial limit to the computing power of VLSI circuits," Proc. Twenty-First Annual IEEE Symposium on Foundations of Computer Science, pp. 294-300, 1980.
• 9: Andrew C. Yao, The entropic limitations on VLSI computations(Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.308-311, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802483]
• 10: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

General Terms:
Theory