Avi Wigderson, David Zuckerman  @ NUS Home/Search
Context Related
| utexas.edu/pub/techrepor...tr9521.ps.Z utexas.edu/ftp/pub/techr...tr9521.ps.Z Cached: PS.gz PS PDF Image Update Help From: utexas.edu (more) (Enter author homepages) |
Rate this article:      (best)Comment on this article |
Abstract: For every n and 0 ! ffi ! 1, we construct graphs on n nodes such that every two sets of size n ffi share an edge, having essentially optimal maximum degree n 1\Gammaffi+o(1) . We use them to explicitly construct: 1. A k round sorting algorithm using n 1+1=k+o(1) comparisons. 2. A k round selection algorithm using n 1+1=(2 k \Gamma1)+o(1) comparisons. 3. A depth 2 superconcentrator of size n 1+o(1) . 4. A depth k wide-sense nonblocking generalized connector of size n 1+1=k+o(1) .... (Update)
Cited by: More
A Project Report - Submitted In Partial (Correct)
Collective Asynchronous Reading with Polylogarithmic.. - Chlebus, Kowalski.. (Correct)
Loss-less Condensers, Unbalanced Expanders, and Extractors - Ta-Shma, Umans, Zuckerman (Correct)
Active bibliography (related documents): More All
3.4: Expanders that Beat the Eigenvalue Bound: Explicit.. - Wigderson, Zuckerman (1993) (Correct)
0.9: On the Complexity of Bilinear Forms (Extended Abstract) - Nisan, Wigderson (1994) (Correct)
0.3: Most Regular Graphs are Quickly r-Transitive - Friedman, Joux, Roichman.. (1994) (Correct)
Similar documents based on text: More All
0.3: A Complete Bibliography of Publications in the ACM Symposia on.. - Beebe (2001) (Correct)
0.3: Expander Graphs for Digital Stream Authentication and.. - Song, Zuckerman, Tygar (2002) (Correct)
0.3: Construction of Extractors Using Pseudo-Random Generators.. - Trevisan (1999) (Correct)
Related documents from co-citation: More All
36: Simulating BPP Using a General Weak Random Source - Zuckerman - 1991
34: Computing with Very Weak Random Sources - Srinivasan, Zuckerman
33: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Co.. - Chor, Goldreich - 1988
BibTeX entry: (Update)
A. Wigderson, D. Zuckerman, " Expanders that Beat the Eigenvalue Bound, Explicit Construction and Applications", Proc. of the 25th STOC, pp. 245--251, 1993. To appear in Combinatorica. http://citeseer.comp.nus.edu.sg/10577.html More
@misc{ wigderson93expanders,
author = "A. Wigderson and D. Zuckerman",
title = "Expanders that Beat the Eigenvalue Bound, Explicit Construction and Applications",
text = "A. Wigderson, D. Zuckerman, Expanders that Beat the Eigenvalue Bound,
Explicit Construction and Applications, Proc. of the 25th STOC, pp. 245--251,
1993. To appear in Combinatorica.",
year = "1993",
url = "citeseer.comp.nus.edu.sg/10577.html" }
Citations (may not include all citations):148 Ramanujan Graphs (context) - Lubotzky, Philips et al. - 1988
126 Eigenvalues and Expanders (context) - Alon - 1986
88 Deterministic Simulation of Logspace (context) - Ajtai, Komlos et al. - 1987
84 Simulating BPP Using a General Weak Random Source - Zuckerman - 1991
79 Parallelism in Comparison Problems (context) - Valiant - 1975
75 Randomness is Linear in Space - Nisan, Zuckerman - 1993
71 Explicit Construction of Linear Sized Superconcentrators (context) - Gabber, Galil - 1981
60 Computing with Very Weak Random Sources - Srinivasan, Zuckerman
54 Explicit Construction of Concentrators (context) - Margulis
36 Security Preserving Amplification of Hardness - Goldreich, Impagliazzo et al. - 1990
35 General Weak Random Sources (context) - Zuckerman - 1990
29 Sorting and Selecting in Rounds (context) - Pippenger - 1987
21 Explicit Construction of Concentrators from Generalized N -g.. (context) - Tanner - 1984
20 Graph Theoretic Properties in Computational Complexity (context) - Valiant - 1976
17 Sorting in c log n Parallel Steps (context) - Ajtai, Komlos et al. - 1983
17 Wide-Sense Nonblocking Networks (context) - Feldman, Friedman et al. - 1988
16 the Second Eigenvalue and Linear Expansion of Regular Graphs (context) - Kahale - 1992
13 1 , Isoperimetric Inequalities for Graphs and Superconcentra.. (context) - Alon, Milman - 1985
11 A Geometric Construction of a Superconcentrator of Depth 2 (context) - Meshulam - 1984
9 Almost Sorting in One Round (context) - Ajtai, Komlos et al. - 1989
9 Rearrangeable Networks with Limited Depth (context) - Pippenger, Yao - 1982
7 Superconcentrators (context) - Pippenger - 1977
5 Superconcentrators, Generalizers, and Generalized Connectors.. (context) - Dolev, Dwork et al. - 1983
4 Time Space Tradeoffs for Computing Functions, Using Connecti.. (context) - Tompa - 1980
3 Explicit Construction of Natural Bounded Concentrators (context) - Morgenstern - 1991
3 Superconcentrators of Depth 2 (context) - Pippenger - 1982
3 Parallel Selection (context) - Azar, Pippenger - 1990
2 Parallel Sorting (context) - Bollobas, Thomason - 1983
2 Sorting, Approximate Sorting, and Searching in Rounds (context) - Alon, Azar - 1988
1 Expanders, Sorting in Rounds, and Superconcentrators of Limi.. (context) - Alon - 1985
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://fermivista.math.jussieu.fr/ftp/ftp.cs.utexas.edu.html): More
Stack Tracing In A Statically Typed Language - Diwan (1991) (Correct)
Combining Top-down and Bottom-up Techniques in Inductive .. - Zelle, Mooney, Konvisser (1994) (Correct)
Expert Systems for Monitoring and Control - Dvorak (1987) (Correct)
Online articles have much greater impact More about CiteSeer.IST at NUS Add search form to your site Submit documents Feedback
CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.