2 citations · 2 across the 4 of their papers we have counts for
7 papers
Linear Programming Bounds for Almost-Balanced Binary Codes
Venkatesan Guruswami, Andrii Riazanov
We revisit the linear programming bounds for the size vs. distance trade-off for binary codes, focusing on the bounds for the almost-balanced case, when all pairwise distances are…
Linear Shannon Capacity of Cayley Graphs
Venkatesan Guruswami, Andrii Riazanov
The Shannon capacity of a graph is a fundamental quantity in zero-error information theory measuring the rate of growth of independent sets in graph powers. Despite being well-stud…
Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity
Venkatesan Guruswami, Andrii Riazanov, Min Ye
Let be a binary-input memoryless symmetric (BMS) channel with Shannon capacity and fix any . We construct, for any sufficiently small , binary linear codes o…
Beating Fredman-Komlós for perfect -hashing
Venkatesan Guruswami, Andrii Riazanov
We say a subset is a -hash code (also called -separated) if for every subset of codewords from , there exists a coordinate where all th…
Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network Flow
Andrii Riazanov, Yury Maximov, Michael Chertkov
Belief Propagation algorithms are instruments used broadly to solve graphical model optimization and statistical inference problems. In the general case of a loopy Graphical Model,…
Exploring the bounds on the positive semidefinite rank
Andrii Riazanov, Mikhail Vyalyiy
The nonnegative and positive semidefinite (PSD-) ranks are closely connected to the nonnegative and positive semidefinite extension complexities of a polytope, which are the minima…