|
 ABSTRACT
The main concrete result of this paper is the first explicit construction of constant degree lossless expanders. In these graphs, the expansion factor is almost as large as possible: (1—&egr;)D, where D is the degree and &egr; is an arbitrarily small constant. The best previous explicit constructions gave expansion factor D/2, which is too weak for many applications. The D/2 bound was obtained via the eigenvalue method, and is known that that method cannot give better bounds.The main abstract contribution of this paper is the introduction and initial study of randomness conductors, a notion which generalizes extractors, expanders, condensers and other similar objects. In all these functions, certain guarantee on the input "entropy" is converted to a guarantee on the output "entropy". For historical reasons, specific objects used specific guarantees of different flavors. We show that the flexibility afforded by the conductor definition leads to interesting combinations of these objects, and to better constructions such as those above.The main technical tool in these constructions is a natural generalization to conductors of the zig-zag graph product, previously defined for expanders and extractors.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
|
| |
3
|
|
| |
4
|
N. Alon. Private communication. 1995.
|
| |
5
|
N. Alon and V. D. Milman. Eigenvalues, expanders and superconcentrators (extended abstract). In 25th Annual Symposium on Foundations of Computer Science, pages 320--322, Singer Island, Florida, 24--26 Oct. 1984. IEEE.
|
| |
6
|
|
| |
7
|
P. Beame and T. Pitassi. Propositional proof complexity: Past, present and future. Technical Report TR98-067, Electronic Colloquium on Computational Complexity, 1998.
|
 |
8
|
|
| |
9
|
|
| |
10
|
H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are bitvectors optimal?, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.449-458, May 21-23, 2000, Portland, Oregon, United States
[doi> 10.1145/335305.335357]
|
| |
11
|
M. Capalbo. Explicit constant-degree unique-neighbor expanders. Submitted, 2001.
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261--277, 1988.
|
| |
17
|
M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman. Improved low-density parity-check codes using irregular graphs. IEEE Trans. Inform. Theory, 47(2):585--598, 2001.
|
| |
18
|
G. A. Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51--60, 1988.
|
| |
19
|
|
| |
20
|
D. Peleg and E. Upfal. Constructing disjoint paths on expander graphs. Combinatorica, 9(3):289--313, 1989.
|
| |
21
|
|
| |
22
|
|
| |
23
|
|
| |
24
|
Ran Raz , Omer Reingold , Salil Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.149-158, May 01-04, 1999, Atlanta, Georgia, United States
[doi> 10.1145/301250.301292]
|
| |
25
|
|
| |
26
|
|
| |
27
|
|
| |
28
|
M. Sipser and D. A. Spielman. Expander codes. IEEE Trans. Inform. Theory, 42(6, part 1):1710--1722, 1996.
|
| |
29
|
D. A. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inform. Theory, 42(6, part 1):1723--1731, 1996.
|
| |
30
|
|
| |
31
|
Amnon Ta-Shma , Christopher Umans , David Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.143-152, July 2001, Hersonissos, Greece
[doi> 10.1145/380752.380790]
|
| |
32
|
M. R. Tanner. Explicit concentrators from generalized n-gons. SIAM Journal on Algebraic Discrete Methods, 5(3):287--293, 1984.
|
| |
33
|
|
| |
34
|
G. C. Tseitin. On the complexity of derivations in propositional calculus. In Studies in constructive (MATH)ematics and (MATH)ematical logic, Part II. Consultants Bureau, New-York-London, 1968.
|
| |
35
|
|
| |
36
|
|
CITED BY 17
|
|
Chi-Jen Lu , Omer Reingold , Salil Vadhan , Avi Wigderson, Extractors: optimal up to constant factors, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Boaz Barak , Guy Kindler , Ronen Shaltiel , Benny Sudakov , Avi Wigderson, Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
|
|
|
|
|
|
|
|
|
|
|
|
Mette Berger , Esben Rune Hansen , Rasmus Pagh , Mihai Pǎtraşcu , Milan Ružić , Peter Tiedemann, Deterministic load balancing and dictionaries in the parallel disk model, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
|
|
|
|
|
|
Boaz Barak , Anup Rao , Ronen Shaltiel , Avi Wigderson, 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
|
|
|
|
|
|
|
|
|
Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Cryptography with constant computational overhead, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
G.2