Derandomized graph products

Noga Mordechai Alon, Uriel Feige, Avi Wigderson, David Zuckerman

Research output: Contribution to journalArticle

83 Scopus citations

Abstract

Berman and Schnitger gave a randomized reduction from approximating MAX-SNP problems within constant factors arbitrarily close to 1 to approximating clique within a factor of nε (for some ε). This reduction was further studied by Blum, who gave it the name randomized graph products. We show that this reduction can be made deterministic (derandomized), using random walks on expander graphs. The main technical contribution of this paper is in proving a lower bound for the probability that all steps of a random walk stay within a specified set of vertices of a graph. (Previous work was mainly concerned with upper bounds for this probability.) This lower bound extends also to the case where different sets of vertices are specified for different time steps of the walk.

Original languageEnglish (US)
Pages (from-to)60-75
Number of pages16
JournalComputational Complexity
Volume5
Issue number1
DOIs
StatePublished - Mar 1 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Derandomized graph products'. Together they form a unique fingerprint.

  • Cite this

    Alon, N. M., Feige, U., Wigderson, A., & Zuckerman, D. (1995). Derandomized graph products. Computational Complexity, 5(1), 60-75. https://doi.org/10.1007/BF01277956