Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
From MaRDI portal
Publication:579273
DOI10.1007/BF02579382zbMath0625.05026WikidataQ56047325 ScholiaQ56047325MaRDI QIDQ579273
Publication date: 1986
Published in: Combinatorica (Search for Journal in Brave)
Searching and sorting (68P10) Extremal problems in graph theory (05C35) Combinatorial aspects of finite geometries (05B25) Generalized Ramsey theory (05C55)
Related Items
Embedding graphs with bounded degree in sparse pseudorandom graphs, Dense expanders and pseudo-random bipartite graphs, Hardness of fully dense problems, Random Cayley graphs and expanders, The number of submatrices of a given type in a Hadamard matrix and related results, Ramanujan graphs, Sorting in rounds, On the number of flats spanned by a set of points in \(PG(d,q)\), Constructive bounds for a Ramsey-type problem, Number of directions determined by a set in \(\mathbb{F}_q^2\) and growth in \(\mathrm{Aff}(\mathbb{F}_q)\), On the growth rate in SL2(Fp)${\rm SL_2}(\mathbb {F}_p)$, the affine group and sum‐product type implications, Domination in transitive colorings of tournaments, Elementary methods for incidence problems in finite fields, On distinct perpendicular bisectors and pinned distances in finite fields, The size Ramsey number of a directed path, Constant time parallel sorting: An empirical view., Extending Erdős-Beck's theorem to higher dimensions, Sign rank versus Vapnik-Chervonenkis dimension, Unnamed Item, The hardest halfspace, More on configurations in Priestley spaces, and some new problems, Pach's selection theorem does not admit a topological extension, Unimodular graphs and Eisenstein sums, Highly symmetric expanders, Non-representability of finite projective planes by convex sets, Unnamed Item, The size-Ramsey number of trees, Universal traversal sequences for expander graphs, On the spectrum of projective norm-graphs, A Ramsey type problem concerning vertex colourings, Candidate One-Way Functions Based on Expander Graphs, A Sample of Samplers: A Computational Perspective on Sampling, Incidence Bounds for Block Designs, ON EMBEDDINGS OF FINITE METRIC SPACES IN, On the second eigenvalue of hypergraphs, Ramanujan edge-indexed graphs, Scalable secure storage when half the system is faulty, \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators, The conjunctive complexity of quadratic Boolean functions, Parallel comparison algorithms for approximation problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Sorting in \(c \log n\) parallel steps
- Eigenvalues and expanders
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- Sorting in one round
- Explicit constructions of linear-sized superconcentrators
- Intersection theorems with geometric consequences
- Graph-theoretic properties in computational complexity
- Asymptotic lower bounds for Ramsey functions
- A note on time-space tradeoffs for computing continuous functions
- Parallel sorting
- On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
- Explicit Concentrators from Generalized N-Gons
- Better expanders and superconcentrators
- Sorting and Selecting in Rounds
- Parallel Sorting with Constant Time for Comparisons
- Sorting and Merging in Rounds
- Asymptotically tight bounds on time-space trade-offs in a pebble game
- Parallelism in Comparison Problems
- Superconcentrators
- Space bounds for a game on graphs
