## Algorithms and Complexity: Second Italian Conference, CIAC '94, Rome, Italy, February 23 - 25, 1994. ProceedingsMaurizio Bonuccelli, Pierluigi Crescenzi, Rossella Petreschi The papers in this volume were presented at the Second Italian Conference onAlgorithms and Complexity, held in February 1994 in Rome. This biannual conference series is intended to present research contributions in theory and applications of sequential, parallel, and distributed algorithms, data structures, and computational complexity. The volume contains four invited presentations and 14 regular presentations selected from 32 submissions, each of which was evaluated by at least four program committee members. The invited presentations are by J. Hartmanis and S. Chari, A. Garg and R. Tamassia, S.C. Sahinalp and U. Vishkin, and M. Yannakakis. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Invited Presentations | 1 |

On a ParallelAlgorithms Method for String Matching Problems | 22 |

Yannakakis | 37 |

Copyright | |

10 other sections not shown

### Other editions - View all

### Common terms and phrases

2-sensitivity access cost approximation arbitrary articulation point auxiliary graphs average sensitivity biconnected component binary Blum integer Boolean functions cellular automata chain vertex clauses coin Computer Science consider constant construction CREP data structures defined definition denote deterministic digraph edge electronic cash system elements EREW EREW P-RAM exists fc-core finite Fourier coefficients given graph drawing hamming distance hypercube input insertion interactive iteration labeled Lemma linear lower bound matrix merging node non-interactive NP-complete number of steps O(logn optimal packet pair deletions partition tree planar graph polynomial problem Proc procedure proof system properties prove pruning decomposition PSPACE PSPACE-complete quadratic residue queries random reduce root satisfied self-reducible self-reducible set sequence solution spanning tree sparse sets string substring suffix tree super leaf Tamassia Theorem total number truth assignment unbounded array upward planarity variables verifier vertices zero-knowledge proof