Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR19-166 | 20th November 2019
Guy Blanc, Jane Lange, Li-Yang Tan

Top-down induction of decision trees: rigorous guarantees and inherent limitations

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

ISSN 1433-8092 | Imprint