文章基本信息

标题：Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs
本地全文：下载
作者：Vikraman Arvind ; Partha Mukhopadhyay ; Prajakta Nimbhorkar 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Given a finite group G by its multiplication table as input, we give a deterministic polynomial-time construction of a directed Cayley graph on G with O(logG) generators, which has a rapid mixing property and a constant spectral expansion.We prove a similar result in the undirected case, and give a new deterministic polynomial-time construction of an expanding Cayley graph with O(logG) generators, for any group G given by its multiplication table. This gives a completely different and elementary proof of a result of Wigderson and Xiao.For any finite group G given by a multiplication table, we give a deterministic polynomial-time construction of a cube generating sequence that gives a distribution on G which is arbitrarily close to the uniform distribution. This derandomizes the construction of Erdos-Renyi sequences
关键词：Deterministic Construction, Expanding Cayley Graphs