Isotropic graphs with applications to parallel computation

This thesis studies the construction of expanding graphs and their applications to parallel computation. In particular, we consider explicit construction techniques, based on finite fields, that provide graphs which exhibit good expansion properties at low densities and can be efficiently implemented. These techniques are related to the one introduced by Morgenstern, based on quotients of the projective linear group over a finite field, which was originally employed for constructing bounded concentrators of density q, for any prime power $q > 2$.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Piertracaprina, Andrea

Contributors dc:contributor

• Liu, C.L.

• Computer Science

Statement dc:rights

• Copyright 1994 Piertracaprina, Andrea

Language dc:language

eng

Identifier

AAI9503296
(UMI)AAI9503296

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/18965