Superconcentrators
From MaRDI portal
Publication:4134003
DOI10.1137/0206022zbMath0361.05035OpenAlexW4235082445MaRDI QIDQ4134003
Publication date: 1977
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0206022
Related Items
Multi-processor scheduling and expanders, Complexity of linear circuits and geometry, Recursive construction for 3-regular expanders, On using deterministic functions to reduce randomness in probabilistic algorithms, Smaller superconcentrators of density 28, Uniformly Exhaustive Submeasures and Nearly Additive Set Functions, Expanders obtained from affine transformations, Rounds versus time for the two person pebble game, Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, Finite fields and Ramanujan graphs, Eigenvalues and expanders, On the spectral distribution of large weighted random regular graphs, Expanders and Diffusers, Explicit Concentrators from Generalized N-Gons, Pebbling with an auxiliary pushdown, The complexity of testing whether a graph is a superconcentrator, Superconcentrators of depth 2, Explicit constructions of linear-sized superconcentrators, Size bounds for superconcentrators, Min-rank conjecture for log-depth circuits, Invariant and geometric aspects of algebraic complexity theory. I, Three-regular path pairable graphs, Construction of expanders and superconcentrators using Kolmogorov complexity, Highly symmetric expanders, Entropy of operators or why matrix multiplication is hard for depth-two circuits, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Nullstellensatz size-degree trade-offs from reversible pebbling, Lower bounds for matrix factorization, A note on a construction of Margulis, Time-space trade-offs in a pebble game, Approximate Modularity Revisited, Lower bounds for matrix factorization, Size-space tradeoffs for oblivious computations, Extracting randomness: A survey and new constructions, Lower bounds in algebraic computational complexity, Rounds versus time for the two person pebble game, Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization, Diameters and Eigenvalues, OptORAMa: optimal oblivious RAM
