We examine the power of Boolean functions with low L_1 norms in several
settings. In large part of the recent literature, the degree of a polynomial
which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function.
However, some functions ... more >>>

It has been shown in previous recent work that
multiplicity automata are predictable from multiplicity
and equivalence queries. In this paper we generalize
related notions in a matrix representation
and obtain a basis for the solution
of a number of open problems in learnability theory.
Membership queries are generalized ... more >>>

We propose an information-theoretic approach to proving lower
bounds on the size of branching programs. The argument is based on
Kraft-McMillan type inequalities for the average amount of
uncertainty about (or entropy of) a given input during the various
stages of computation. The uncertainty is measured by the average
more >>>

Let f be a Boolean function. Let N(f)=\dnf(f)+\dnf(\neg f) be the
sum of the minimum number of monomials in a disjunctive normal form
for f and \neg f. Let p(f) be the minimum size of a partition
of the Boolean cube into disjoint subcubes such that f is constant on
more >>>

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate.

First, we show that for any problem that ... more >>>

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is \|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|). Specifically, we prove the following results for functions f:\{0,1\}^n\to \{0,1\} with \|\hat{f}\|_1=A.

1. There is a subspace V of co-dimension at most A^2 such that f|_V is constant.

2. ... more >>>

We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that ... more >>>

For a Boolean function f:\{0,1\}^n \to \{0,1\} computed by a circuit C over a finite basis \cal{B}, the energy complexity of C (denoted by \mathbf{EC}_{{\cal B}}(C)) is the maximum over all inputs \{0,1\}^n the numbers of gates of the circuit C (excluding the inputs) that output a one. Energy Complexity ... more >>>

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

We investigate the number of pairwise comparisons sufficient to sort n elements chosen from a linearly ordered set. This number is shown to be \log_2(n!) + o(n) thus improving over the previously known upper bounds of the form \log_2(n!) + \Theta(n). The new bound is achieved by the proposed group ... more >>>

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let IP denote Inner Product on ... more >>>

Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated `lifted' function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. Several important complexity ... more >>>

In this paper, we initiate study of the computational power of adaptive and non-adaptive monotone decision trees – decision trees where each query is a monotone function on the input bits. In the most general setting, the monotone decision tree height (or size) can be viewed as a measure of ... more >>>

Lifting theorems are used for transferring lower bounds between Boolean function complexity measures. Given a lower bound on a complexity measure A for some function f, we compose f with a carefully chosen gadget function g and get essentially the same lower bound on a complexity measure B for the ... more >>>

For any constant \alpha > 0, we construct an explicit pseudorandom generator (PRG) that fools n-variate decision trees of size m with error \epsilon and seed length (1 + \alpha) \cdot \log_2 m + O(\log(1/\epsilon) + \log \log n). For context, one can achieve seed length $(2 + o(1)) \cdot ... more >>>