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
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
