All reports by Author Guy Blanc:

__
TR22-027
| 22nd February 2022
__

Guy Blanc, Dean Doron#### New Near-Linear Time Decodable Codes Closer to the GV Bound

Revisions: 1

__
TR19-166
| 20th November 2019
__

Guy Blanc, Jane Lange, Li-Yang Tan#### Top-down induction of decision trees: rigorous guarantees and inherent limitations

Guy Blanc, Dean Doron

We construct a family of binary codes of relative distance $\frac{1}{2}-\varepsilon$ and rate $\varepsilon^{2} \cdot 2^{-\log^{\alpha}(1/\varepsilon)}$ for $\alpha \approx \frac{1}{2}$ that are decodable, probabilistically, in near linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who ... more >>>

Guy Blanc, Jane Lange, Li-Yang Tan

Consider the following heuristic for building a decision tree for a function $f : \{0,1\}^n \to \{\pm 1\}$. Place the most influential variable $x_i$ of $f$ at the root, and recurse on the subfunctions $f_{x_i=0}$ and $f_{x_i=1}$ on the left and right subtrees respectively; terminate once the tree is an ... more >>>