We give an algorithm for finding an \epsilon-fixed point of a contraction map f:[0,1]^k\rightarrow [0,1]^k under the \ell_\infty-norm with query complexity O (k^2\log (1/\epsilon ) ).

more >>>

We study the problem of finding a Tarski fixed point over the k-dimensional grid [n]^k. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique ... more >>>

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

We prove that any non-adaptive algorithm that tests whether an unknown
Boolean function f\colon \{0, 1\}^n\to\{0, 1\} is a k-junta or \epsilon-far from every k-junta must make \widetilde{\Omega}(k^{3/2} / \epsilon) many queries for a wide range of parameters k and \epsilon. Our result dramatically improves previous lower ... more >>>

In this note, we study the recursive teaching dimension(RTD) of concept classes of low VC-dimension. Recall that the VC-dimension of C \subseteq \{0,1\}^n, denoted by VCD(C), is the maximum size of a shattered subset of [n], where Y\subseteq [n] is shattered if for every binary string \vec{b} of length |Y|, ... more >>>

Let U_{k,N} denote the Boolean function which takes as input k strings of N bits each, representing k numbers a^{(1)},\dots,a^{(k)} in \{0,1,\dots,2^{N}-1\}, and outputs 1 if and only if a^{(1)} + \cdots + a^{(k)} \geq 2^N. Let THR_{t,n} denote a monotone unweighted threshold gate, i.e., the Boolean function which takes ... more >>>