High dimensional expanders and property testing

DOI10.1145/2554797.2554842MaRDI QIDQ2988903zbMATH OpenOpenAlexFDO

Authors Tali Kaufman, Alexander Lubotzky

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://arxiv.org/abs/1312.2367

zbMATH Keywords

high-dimensional expandersproperty testing

Mathematics Subject Classification ID

Combinatorial aspects of simplicial complexes (05E45) Randomized algorithms (68W20)

Abstract: We show that the high dimensional expansion property as defined by Gromov, Linial and Meshulam, for simplicial complexes is a form of testability. Namely, a simplicial complex is a high dimensional expander iff a suitable property is testable. Using this connection, we derive several testability results.

Recommendations

• Property testing and expansion in cubical complexes
• Testing Odd Direct Sums Using High Dimensional Expanders
• HIGH DIMENSIONAL EXPANDERS
• Simplicial complexes: spectrum, homology and random walks

Cites work

• (Leveled) fully homomorphic encryption without bootstrapping
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Evaluating Branching Programs on Encrypted Data
• Fully homomorphic encryption using ideal lattices
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• New lattice-based cryptographic constructions
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
• Public-key cryptosystems from the worst-case shortest vector problem
• Toward basing fully homomorphic encryption on worst-case hardness
• Trapdoors for hard lattices and new cryptographic constructions
• Trapdoors for lattices: simpler, tighter, faster, smaller

Cited in

(22)

• A test for expandability
• Spectrum of signless 1-Laplacian on simplicial complexes
• Expansion of building-like complexes
• Property testing and expansion in cubical complexes
• High dimensional random walks and colorful expansion
• Ramanujan complexes and high dimensional expanders
• HIGH DIMENSIONAL EXPANDERS
• scientific article; zbMATH DE number 7650107 (Why is no real title available?)
• Testing Odd Direct Sums Using High Dimensional Expanders
• Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes
• Single-shot decoding of good quantum LDPC codes
• Nowhere to go but high: a perspective on high-dimensional expanders
• Boolean function analysis on high-dimensional expanders
• Coboundary expansion for the union of determinantal hypertrees
• Sparse high dimensional expanders via local lifts
• Coboundary and cosystolic expansion without dependence on dimension or degree
• The largest Laplacian eigenvalue and the balancedness of simplicial complexes
• Bounds on the mod 2 homology of random 2-dimensional determinantal hypertrees
• Stability of homomorphisms, coverings and cocycles. I: Equivalence
• Stability of homomorphisms, coverings and cocycles. II: Examples, applications and open problems
• Explicit SoS lower bounds from high-dimensional expanders
• Coboundary and cosystolic expansion from strong symmetry

This page was built for publication: High dimensional expanders and property testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988903)