16 citations · 17 across the 11 of their papers we have counts for
14 papers
Tournament Robustness via Redundancy
Klim Efremenko, Hendrik Molter, Meirav Zehavi
A knockout tournament is one of the most simple and popular forms of competition. Here, we are given a binary tournament tree where all leaves are labeled with seed position names.…
Unbounded Error Correcting Codes
Klim Efremenko, Or Zamir
Traditional error-correcting codes (ECCs) assume a fixed message length, but many scenarios involve ongoing or indefinite transmissions where the message length is not known in adv…
Statistically Near-Optimal Hypothesis Selection
Olivier Bousquet, Mark Braverman, Klim Efremenko +2
Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class of distributions, and a sampling access to an unknown tar…
Non-parametric Binary regression in metric spaces with KL loss
Ariel Avital, Klim Efremenko, Aryeh Kontorovich +2
We propose a non-parametric variant of binary regression, where the hypothesis is regularized to be a Lipschitz function taking a metric space to [0,1] and the loss is logarithmic.…
Fast and Bayes-consistent nearest neighbors
Klim Efremenko, Aryeh Kontorovich, Moshe Noivirt
Research on nearest-neighbor methods tends to focus somewhat dichotomously either on the statistical or the computational aspects -- either on, say, Bayes consistency and rates of…
Optimal Short-Circuit Resilient Formulas
Mark Braverman, Klim Efremenko, Ran Gelles +1
We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate's inputs. A recent result by Kalai et al. (FOCS 2012) convert…