Expander Graphs for Pseudorandom-number Generation

A guided research project in Algorithms & Discrete Mathematics.

← Algorithms & Discrete Mathematics projects

Experience Research Algorithms & Discrete Mathematics

Question

How can a sparse graph produce a sequence that behaves almost randomly?

Strong expansion spreads a local random choice quickly across the whole graph.
Strong expansion spreads a local random choice quickly across the whole graph.

Goals

  • Build or study an expander graph and its random walks.
  • Measure mixing and use the walk as a pseudorandom generator.

Method

Move through a highly connected sparse graph using a small random choice at each step.

  • Construct a regular graph and examine its expansion or spectral gap.
  • Generate sequences from random walks on the graph.
  • Compare their distribution and correlations with truly random and ordinary graph walks.