REVIEW 6 cited by
Explicit expanders of every degree and size
Not yet reviewed by Pith; the record is open.
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
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.
Forward citations
Cited by 6 Pith papers
-
Macroeconomic Message Passing for Anticipating Foreign Exchange Regime Changes: A Deep Logical Learning Approach using Graph Tsetlin Machines
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...
-
Serving the Long Tail: Training-Free LLM Candidate Generation for Vacation Rental Marketplaces
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%.
-
Refining Text Generation for Realistic Conversational Recommendation via Direct Preference Optimization
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.
-
Optimizing Recall or Relevance? A Multi-Task Multi-Head Approach for Item-to-Item Retrieval in Recommendation
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.
-
Leveraging Recurrent Patterns in Graph Accelerators
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.
-
Content filtering methods for music recommendation: A review
A survey of content-based music recommendation methods, including audio analysis, lyrics analysis, and context awareness, with no new experimental results.
Discussion (0). Continue with ORCID to comment.