Treffer: The computational complexity of universal hashing
Title:
The computational complexity of universal hashing
Authors:
Source:
Structure in complexity theoryTheoretical computer science. 107(1):121-133
Publisher Information:
Amsterdam: Elsevier, 1993.
Publication Year:
1993
Physical Description:
print, 25 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Automates. Machines abstraites. Machines de turing, Automata. Abstract machines. Turing machines, Circuit VLSI, VLSI circuit, Circuito VLSI, Complexité calcul, Computing complexity, Complejidad cálculo, Hachage, Hashing, Implémentation, Implementation, Ejecución, Informatique théorique, Computer theory, Informática teórica, Limite inférieure, Lower bound, Límite inferior, Machine Turing, Turing machine, Máquina Turing, Multiprocesseur, Multiprocessor, Multiprocesador, Mémoire accès direct, Random access memory(RAM), Memoria acceso directo, Programmation booléenne, Boolean programming, Programación booleana, Ramification, Branching, Ramificación, Système informatique, Computer system, Sistema informático, Système parallèle, Parallel system, Sistema paralelo
Document Type:
Fachzeitschrift
Article
File Description:
text
Language:
English
Author Affiliations:
MIT, lab. computer sci., Cambridge MA 02139, United States
ISSN:
0304-3975
Rights:
Copyright 1993 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.4518484
Database:
PASCAL Archive
Weitere Informationen
Any implementation of Carter-Wegman universal hashing from n-bit strings to m-bit strings requires a time-space tradeoff of TS=Ω(nm). The bound holds in tale general boolean branching program model and, talus, in essentially any model of computation. As a corollary, computing a+b*c in any field F requires a quadratic time-space tradeoff, and tale bound holds for any representation of tale elements of tale field. Other lower bounds on tale complexity of any implementation of universal hashing are given as well: quadratic AT2 bound for VLSI implementation; Ω(log n) parallel time bound on a CREW PRAM; and exponential size for constant-depth circuits.