### Abstract

We propose a new model of compulation for VLSI which is a refinement of previous models and makes the additional assumption that the lime for propagating information is linear in the distance. Our approach is motivated by the failure of previous models to allow for realistic asymptotic analysis. While accommodating for basic laws of physics, this model tries to be most general and technology-independent. Thus, from a complexity viewpoint, it is especially suited for deriving lower bounds and trade-offs. We present new results for a number of problems including fan-in, addition, transitive functions, matrix multiplication, and sorting.

Original language | English (US) |
---|---|

Title of host publication | Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981 |

Publisher | Association for Computing Machinery |

Pages | 318-325 |

Number of pages | 8 |

ISBN (Print) | 0897910419 |

DOIs | |

State | Published - May 11 1981 |

Externally published | Yes |

Event | 13th Annual ACM Symposium on Theory of Computing, STOC 1981 - Milwaukee, United States Duration: Jun 11 1981 → Jun 13 1981 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 13th Annual ACM Symposium on Theory of Computing, STOC 1981 |
---|---|

Country | United States |

City | Milwaukee |

Period | 6/11/81 → 6/13/81 |

### All Science Journal Classification (ASJC) codes

- Software

## Fingerprint Dive into the research topics of 'A model of computation for VLSI with related complexity results'. Together they form a unique fingerprint.

## Cite this

*Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981*(pp. 318-325). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/800076.802485