Derandomized graph products

Noga Alon; Uriel Feige; Avi Wigderson; David Zuckerman

doi:10.1007/BF01277956

Derandomized graph products

Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman

Research output: Contribution to journal › Article › peer-review

98 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 language	English (US)
Pages (from-to)	60-75
Number of pages	16
Journal	Computational Complexity
Volume	5
Issue number	1
DOIs	https://doi.org/10.1007/BF01277956
State	Published - Mar 1995
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Mathematics
Computational Theory and Mathematics
Computational Mathematics

Keywords

Approximation
Subject classifications: 60J15, 68R10
derandomization
random walks

Access to Document

10.1007/BF01277956

Cite this

@article{d25499d569c14fa097b5eaaee05c90e0,

title = "Derandomized graph products",

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.",

keywords = "Approximation, Subject classifications: 60J15, 68R10, derandomization, random walks",

author = "Noga Alon and Uriel Feige and Avi Wigderson and David Zuckerman",

year = "1995",

month = mar,

doi = "10.1007/BF01277956",

language = "English (US)",

volume = "5",

pages = "60--75",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Birkhauser Verlag Basel",

number = "1",

}

TY - JOUR

T1 - Derandomized graph products

AU - Alon, Noga

AU - Feige, Uriel

AU - Wigderson, Avi

AU - Zuckerman, David

PY - 1995/3

Y1 - 1995/3

N2 - 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.

AB - 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.

KW - Approximation

KW - Subject classifications: 60J15, 68R10

KW - derandomization

KW - random walks

UR - http://www.scopus.com/inward/record.url?scp=0002566799&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0002566799&partnerID=8YFLogxK

U2 - 10.1007/BF01277956

DO - 10.1007/BF01277956

M3 - Article

AN - SCOPUS:0002566799

SN - 1016-3328

VL - 5

SP - 60

EP - 75

JO - Computational Complexity

JF - Computational Complexity

IS - 1

ER -

Derandomized graph products

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this