Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR15-117 | 21st July 2015
Boris Bukh, Venkatesan Guruswami

An improved bound on the fraction of correctable deletions

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint