Local expanders
From MaRDI portal
Publication:1653336
DOI10.1007/s00037-017-0155-1zbMath1398.68164MaRDI QIDQ1653336
Publication date: 3 August 2018
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-017-0155-1
68Q25: Analysis of algorithms and problem complexity
68R05: Combinatorics in computer science
68R10: Graph theory (including graph drawing) in computer science
68W20: Randomized algorithms
Related Items
Deconstructing 1-Local Expanders, Expander-Based Cryptography Meets Natural Proofs, Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Expanders obtained from affine transformations
- Ramanujan graphs
- Explicit constructions of linear-sized superconcentrators
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Symmetric groups and expander graphs.
- The Complexity of Distributions
- Candidate One-Way Functions Based on Expander Graphs
- Nonuniform ACC Circuit Lower Bounds
- Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
- Local Reductions
- Expander graphs and their applications
- Randomness conductors and constant-degree lossless expanders
- Towards a Study of Low-Complexity Graphs
- Foundations of Cryptography
- Short PCPs with Projection Queries
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
- On ε‐biased generators in NC0
- Cryptography in $NC^0$
