Next

__
TR19-167
| 21st November 2019
__

Anant Dhayal, Russell Impagliazzo#### UTIME Easy-witness Lemma & Some Consequences

__
TR19-166
| 20th November 2019
__

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

__
TR19-165
| 18th November 2019
__

Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten#### Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

Next

Anant Dhayal, Russell Impagliazzo

We prove an easy-witness lemma ($\ewl$) for unambiguous non-deterministic verfiers. We show that if $\utime(t)\subset\mathcal{C}$, then for every $L\in\utime(t)$, for every $\utime(t)$ verifier $V$ for $L$, and for every $x\in L$, there is a certificate $y$ satisfing $V(x,y)=1$, that can be encoded as a truth-table of a $\mathcal{C}$ circuit. Our ... 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 >>>

Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten

We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$, and a quantitative analysis of how ... more >>>

Next