2 papers
math.CO2024
The Rank-Ramsey Problem and the Log-Rank Conjecture
Gal Beniamini, Nati Linial, Adi Shraibman
A graph is called Rank-Ramsey if (i) Its clique number is small, and (ii) The adjacency matrix of its complement has small rank. We initiate a systematic study of such graphs. Our…
cs.IT2023
An Elementary Proof of the First LP Bound on the Rate of Binary Codes
Nati Linial, Elyassaf Loyfer
The asymptotic rate vs. distance problem is a long-standing fundamental problem in coding theory. The best upper bound to date was given in 1977 and has received since then numerou…