Explicit constructions of linear-sized superconcentrators
From MaRDI portal
Publication:1165257
DOI10.1016/0022-0000(81)90040-4zbMath0487.05045OpenAlexW2048958388WikidataQ29036351 ScholiaQ29036351MaRDI QIDQ1165257
Publication date: 1981
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(81)90040-4
Related Items (81)
On the relationship between the diameter and the size of a boundary of a directed graph ⋮ The hardness of approximation: Gap location ⋮ On the diameter and bisector size of Cayley graphs ⋮ Recursive construction for 3-regular expanders ⋮ Probabilistically checkable proofs and their consequences for approximation algorithms ⋮ Expander Construction in VNC1 ⋮ Efficient parallel computing with memory faults ⋮ Uniformly Exhaustive Submeasures and Nearly Additive Set Functions ⋮ Expanders obtained from affine transformations ⋮ Dense expanders and pseudo-random bipartite graphs ⋮ Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes ⋮ RECYCLING RANDOM BITS IN PARALLEL ⋮ Local expanders ⋮ Eigenvalues and expanders ⋮ Expansion in SL\(_2(\mathbb R)\) and monotone expanders ⋮ Lower bounds for synchronous circuits and planar circuits ⋮ Optimal parallel selection has complexity O(log log N) ⋮ Explicit expanding expanders ⋮ Expanders and Diffusers ⋮ Efficient construction of a small hitting set for combinatorial rectangles in high dimension ⋮ Simulating BPP using a general weak random source ⋮ Dual VP classes ⋮ Explicit Concentrators from Generalized N-Gons ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ Asymptotic expansion in measure and strong ergodicity ⋮ Generating Extended Resolution Proofs with a BDD-Based SAT Solver ⋮ Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\) ⋮ On the approximability of the Steiner tree problem. ⋮ Unnamed Item ⋮ Expander graphs and their applications ⋮ Equivalent literal propagation in the DLL procedure ⋮ Geometric structures in group theory. Abstracts from the workshop held February 27 -- March 5, 2022 ⋮ Note on the girth of Ramanujan graphs ⋮ Improved non-approximability results for minimum vertex cover with density constraints ⋮ The symmetry rule in propositional logic ⋮ A spanner for the day after ⋮ An Elementary Construction of Constant-Degree Expanders ⋮ Formal Zeta function expansions and the frequency of Ramanujan graphs ⋮ Rigidity of warped cones and coarse geometry of expanders ⋮ Computation of best possible low degree expanders ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ Discrete fundamental groups of warped cones and expanders ⋮ On eigenvalues of random complexes ⋮ Measure expanding actions, expanders and warped cones ⋮ The Steiner tree problem on graphs: inapproximability results ⋮ Construction of expanders and superconcentrators using Kolmogorov complexity ⋮ Comparing first-fit and next-fit for online edge coloring ⋮ Highly symmetric expanders ⋮ Existence of the anchored isoperimetric profile in supercritical bond percolation in dimension two and higher ⋮ Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory ⋮ Improved sorting networks with O(log N) depth ⋮ Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines ⋮ Super-expanders and warped cones ⋮ SIMULATING AN R-MESH ON AN LR-MESH IN CONSTANT TIME ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Universal traversal sequences for expander graphs ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ Candidate One-Way Functions Based on Expander Graphs ⋮ A Sample of Samplers: A Computational Perspective on Sampling ⋮ Bravely, Moderately: A Common Theme in Four Recent Works ⋮ Basic Facts about Expander Graphs ⋮ A fast new algorithm for weak graph regularity ⋮ Sorting in linear time? ⋮ The exact convergence rate in the ergodic theorem of Lubotzky-Phillips-Sarnak and a universal lower bound on discrepancies ⋮ Certifiably Pseudorandom Financial Derivatives ⋮ Natural bounded concentrators ⋮ On the complexity of planar Boolean circuits ⋮ Derandomized graph products ⋮ Explicit Near-Ramanujan Graphs of Every Degree ⋮ Unnamed Item ⋮ Sorting in \(c \log n\) parallel steps ⋮ Extracting randomness: A survey and new constructions ⋮ On subexponential and FPT-time inapproximability ⋮ \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators ⋮ Shallow grates ⋮ Some Graph-Colouring Theorems with Applications to Generalized Connection Networks ⋮ Construction of halvers ⋮ Randomness in interactive proofs ⋮ Reflections on Proof Complexity and Counting Principles ⋮ Diameters and Eigenvalues
Cites Work
This page was built for publication: Explicit constructions of linear-sized superconcentrators
