Pith. sign in

REVIEW 9 cited by

Explicit expanders of every degree and size

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2003.11673 v1 pith:LKWAXJBV submitted 2020-03-25 math.CO cs.DM

Noga Alon This is my paper · ORCID
classification math.COcs.DM
keywords lambdaepsilonsqrtgraphexplicitverticesconstructionevery
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

An $(n,d,\lambda)$-graph is a $d$ regular graph on $n$ vertices in which the absolute value of any nontrivial eigenvalue is at most $\lambda$. For any constant $d \geq 3$, $\epsilon>0$ and all sufficiently large $n$ we show that there is a deterministic poly(n) time algorithm that outputs an $(n,d, \lambda)$-graph (on exactly $n$ vertices) with $\lambda \leq 2 \sqrt{d-1}+\epsilon$. For any $d=p+2$ with $p \equiv 1 \bmod 4$ prime and all sufficiently large $n$, we describe a strongly explicit construction of an $(n,d, \lambda)$-graph (on exactly $n$ vertices) with $\lambda \leq \sqrt {2(d-1)} + \sqrt{d-2} +o(1) (< (1+\sqrt 2) \sqrt {d-1}+o(1))$, with the $o(1)$ term tending to $0$ as $n$ tends to infinity. For every $\epsilon >0$, $d>d_0(\epsilon)$ and $n>n_0(d,\epsilon)$ we present a strongly explicit construction of an $(m,d,\lambda)$-graph with $\lambda < (2+\epsilon) \sqrt d$ and $m=n+o(n)$. All constructions are obtained by starting with known ones of Ramanujan or nearly Ramanujan graphs, modifying or packing them in an appropriate way. The spectral analysis relies on the delocalization of eigenvectors of regular graphs in cycle-free neighborhoods.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 9 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. OpenAlex reports about 5,369 citations worldwide. Full citation record

  1. Optimal $(\alpha,\beta)$-Dense Subgraph Search in Bipartite Graphs

    cs.DB 2025-08 conditional novelty 7.0 of 10

    BD-Index answers (α,β)-dense subgraph queries in a bipartite graph in O(|D|) optimal time using O(|E|) space, with two dynamic maintenance strategies costing O(p·|E|^1.5) and O(p·|E|) per update.

  2. Macroeconomic Message Passing for Anticipating Foreign Exchange Regime Changes: A Deep Logical Learning Approach using Graph Tsetlin Machines

    cs.CE 2026-07 conditional novelty 6.0 of 10

    A Graph Tsetlin Machine with hypervectorized macro multigraphs and message-passing clauses anticipates four USD/JPY regimes, reaching 70.7% overall OOS accuracy and beating reduced-graph and CoTM baselines on stagnant...

  3. Serving the Long Tail: Training-Free LLM Candidate Generation for Vacation Rental Marketplaces

    cs.LG 2026-07 conditional novelty 5.0 of 10

    Union fusion of LLM metadata queries with IBKNN extends candidate coverage to cold-start and long-tail Vrbo listings while matching or beating IBKNN recall at every K and collapsing small-vs-frontier LLM gaps under 1%.

  4. Refining Text Generation for Realistic Conversational Recommendation via Direct Preference Optimization

    cs.IR 2025-08 conditional novelty 5.0 of 10

    DPO fine-tuning of the summary and recommendation writers improves conversational recommendation ranking on two Japanese datasets, but the evaluation shares the scorer that generated the training signal.

  5. Optimizing Recall or Relevance? A Multi-Task Multi-Head Approach for Item-to-Item Retrieval in Recommendation

    cs.IR 2025-06 conditional novelty 5.0 of 10

    A multi-task, multi-head item-to-item retrieval system that merges co-engagement candidates with semantically relevant candidates achieves both higher recall and higher semantic relevance than prior models.

  6. Leveraging Recurrent Patterns in Graph Accelerators

    cs.AR 2025-12 conditional novelty 4.0 of 10

    A ReRAM graph accelerator that pre-configures frequent subgraph patterns into static crossbars reduces memory writes, yielding simulated up-to-2.38x speedup and 7.23x energy savings over a SparseMEM-like baseline.

  7. Progressive Semantic Residual Quantization for Multimodal-Joint Interest Modeling in Music Recommendation

    cs.IR 2025-08 conditional novelty 4.0 of 10

    A progressive residual quantization that feeds the previous nearest centroid back into the codebook input, paired with a multi-codebook cross-attention network, yields small AUC gains in music recommendation.

  8. Collaborative Filtering using Variational Quantum Hopfield Associative Memory

    cs.IR 2025-08 reject novelty 4.0 of 10

    The authors train a variational quantum Hopfield associative memory with an autoencoder and K-Means clustering to classify MovieLens 1M users, reporting ROC 0.9795 in ideal simulation and 0.9177 under noise.

  9. Content filtering methods for music recommendation: A review

    cs.IR 2025-07 conditional

    A survey of content-based music recommendation methods, including audio analysis, lyrics analysis, and context awareness, with no new experimental results.

Pith tools