All reports by Author Boris Bukh:

__
TR21-156
| 10th November 2021
__

Boris Bukh, Karthik C. S., Bhargav Narayanan#### Applications of Random Algebraic Constructions to Hardness of Approximation

__
TR15-117
| 21st July 2015
__

Boris Bukh, Venkatesan Guruswami#### An improved bound on the fraction of correctable deletions

Revisions: 1

Boris Bukh, Karthik C. S., Bhargav Narayanan

In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural.

(*) Panchromatic Graphs: For fixed integer k, a k-panchromatic graph is, roughly speaking, a balanced bipartite graph with one partition class equipartitioned into k colour classes in ...
more >>>

Boris Bukh, Venkatesan Guruswami

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed $k \ge 2$, we construct a family of codes over alphabet of size $k$ with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching $1-\frac{2}{k+1}$. In particular, for binary codes, we are able to ... more >>>