Expanders with respect to Hadamard spaces and random graphs

DOI10.1145/2554797.2554829zbMath1365.05262OpenAlexW2004534915MaRDI QIDQ5892453

Assaf Naor, Manor Mendel

Publication date: 19 May 2017

Published in: Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2554797.2554829

zbMATH Keywords

random regular graphsexpandersmetric embeddingsHadamard spaces\(\mathrm{CAT}(0)\)Euclidean cone

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Complete metric spaces (54E50) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

On the Structure of Isometrically Embeddable Metric Spaces

Cites Work

• Unnamed Item
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• (Leveled) fully homomorphic encryption without bootstrapping
• Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
• Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Trapdoors for hard lattices and new cryptographic constructions
• Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness
• Evaluating Branching Programs on Encrypted Data
• Bounds for Width Two Branching Programs
• Fully homomorphic encryption using ideal lattices
• Public-key cryptosystems from the worst-case shortest vector problem
• Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
• New lattice-based cryptographic constructions
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography