Article

Free access

On notions of information transfer in VLSI circuits

Authors:

Alfred V. Aho,

Jeffrey D. Ullman,

Mihalis YannakakisAuthors Info & Claims

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

Pages 133 - 139

https://doi.org/10.1145/800061.808742

Published: 01 December 1983 Publication History

PDF eReader

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.

Google Scholar

[2]

Lipton, R. J. and R. Sedgewick, "Lower bounds for VLSI," Proc. Thirteenth Annual ACM Symposium on the Theory of Computing, pp. 300-307, 1981.

Digital Library

Google Scholar

[3]

Melhorn, K. and E. M. Schmidt, "Las Vegas is better than determinism in VLSI and distributed computing," Proc. Fourteenth Annual ACM Symposium on Theory of Computing, pp. 330-337, 1982.

Digital Library

Google Scholar

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

Google Scholar

[5]

Papadimitriou, C. H. and M. Sipser, "Communication complexity," Proc. Fourteenth Annual ACM Symposium on the Theory of Computing, pp. 196-200, 1982.

Digital Library

Google Scholar

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

Google Scholar

[7]

Thompson, C. D., "Area-time complexity for VLSI," Proc. Eleventh Annual ACM Symposium on Theory of Computing, pp.81-88, 1979.

Digital Library

Google Scholar

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

Google Scholar

[9]

Yao, A. C., "The entropic limitations of VLSI computations," Proc. Thirteen Annual ACM Symposium on the Theory of Computing, pp. 308-311, 1981.

Digital Library

Google Scholar

[10]

Yao, A. C., "Some complexity questions related to distributive computing," Proc. Eleventh Annual ACM Symposium on the Theory of Computing, pp. 209-213, 1979.

Digital Library

Google Scholar

Cited By

View all

Barokah UUnsunnidhal LKristianingrum YKusumawati A(2023)Transformation of HBcAg gene of hepatitis B virus using pEGFP-C1 vectorTHE 5TH INTERNATIONAL CONFERENCE ON BIOSCIENCE AND BIOTECHNOLOGY10.1063/5.0175741(020006)Online publication date: 2023
https://doi.org/10.1063/5.0175741
Mirajkar KDeshpande ABudihal H(2022)QSPR analysis of KCD coindices for some Chemical compoundsINTERNATIONAL CONFERENCE ON ADVANCES IN MATERIALS, COMPUTING AND COMMUNICATION TECHNOLOGIES: (ICAMCCT 2021)10.1063/5.0070749(130037)Online publication date: 2022
https://doi.org/10.1063/5.0070749
Babichenko YRubinstein A(2022)Communication complexity of approximate Nash equilibriaGames and Economic Behavior10.1016/j.geb.2020.07.005134(376-398)Online publication date: Jul-2022
https://doi.org/10.1016/j.geb.2020.07.005
Show More Cited By

Index Terms

On notions of information transfer in VLSI circuits
1. Hardware
  1. Very large scale integration design
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

December 1983

487 pages

ISBN:0897910990

DOI:10.1145/800061

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1983

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

117
Total Citations
View Citations
296
Total Downloads

Downloads (Last 12 months)84
Downloads (Last 6 weeks)14

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Barokah UUnsunnidhal LKristianingrum YKusumawati A(2023)Transformation of HBcAg gene of hepatitis B virus using pEGFP-C1 vectorTHE 5TH INTERNATIONAL CONFERENCE ON BIOSCIENCE AND BIOTECHNOLOGY10.1063/5.0175741(020006)Online publication date: 2023
https://doi.org/10.1063/5.0175741
Mirajkar KDeshpande ABudihal H(2022)QSPR analysis of KCD coindices for some Chemical compoundsINTERNATIONAL CONFERENCE ON ADVANCES IN MATERIALS, COMPUTING AND COMMUNICATION TECHNOLOGIES: (ICAMCCT 2021)10.1063/5.0070749(130037)Online publication date: 2022
https://doi.org/10.1063/5.0070749
Babichenko YRubinstein A(2022)Communication complexity of approximate Nash equilibriaGames and Economic Behavior10.1016/j.geb.2020.07.005134(376-398)Online publication date: Jul-2022
https://doi.org/10.1016/j.geb.2020.07.005
Martynenko A(2021)Hierarchy of intercity transport network elements and the gravity model for the origin-destination matrixTHERMOPHYSICAL BASIS OF ENERGY TECHNOLOGIES (TBET 2020)10.1063/5.0041823(090017)Online publication date: 2021
https://doi.org/10.1063/5.0041823
Rao AYehudayoff A(2020)Communication Complexity10.1017/9781108671644Online publication date: 30-Jan-2020
https://doi.org/10.1017/9781108671644
Fomin FGolovach PPanolan F(2020)Parameterized low-rank binary matrix approximationData Mining and Knowledge Discovery10.1007/s10618-019-00669-5Online publication date: 2-Jan-2020
https://doi.org/10.1007/s10618-019-00669-5
Göös MJayram TPitassi TWatson T(2018)Randomized Communication versus Partition NumberACM Transactions on Computation Theory10.1145/317071110:1(1-20)Online publication date: 24-Jan-2018
https://dl.acm.org/doi/10.1145/3170711
Hospodár MJirásková GMlynárčik P(2018)A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic ComplexityAdventures Between Lower Bounds and Higher Altitudes10.1007/978-3-319-98355-4_2(17-32)Online publication date: 9-Aug-2018
https://doi.org/10.1007/978-3-319-98355-4_2
Babichenko YRubinstein AHatami HMcKenzie PKing V(2017)Communication complexity of approximate Nash equilibriaProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055407(878-889)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055407
Ambainis AKokainis MKothari R(2016)Nearly optimal separations between communication (or query) complexity and partitionsProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982449(1-14)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.5555/2982445.2982449
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Testable designs for CMOS VLSI circuits

Modeling energy consumption in vlsi circuits

Synthesis of sequential circuits for VLSI design