Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with decision trees:
TR95-046 | 4th August 1995
Vince Grolmusz

On the Power of Circuits with Gates of Low L_1 Norms

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

TR96-008 | 22nd January 1996
F. Bergadano, N.H. Bshouty, Stefano Varricchio

Learning Multivariate Polynomials from Substitution and Equivalence Queries

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

TR01-039 | 18th May 2001
Stasys Jukna, Stanislav Zak

On Uncertainty versus Size in Branching Programs

Revisions: 1

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

TR02-009 | 17th January 2002
Petr Savicky

On determinism versus unambiquous nondeterminism for decision trees

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

TR09-110 | 5th November 2009
Scott Aaronson, Andris Ambainis

The Need for Structure in Quantum Speedups

Revisions: 1

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

TR13-049 | 1st April 2013
Amir Shpilka, Ben Lee Volk, Avishay Tal

On the Structure of Boolean Functions with Small Spectral Norm

Revisions: 1

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

TR13-164 | 28th November 2013
Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

Weak Parity

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

TR18-153 | 22nd August 2018
Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma

New Bounds for Energy Complexity of Boolean Functions

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

ISSN 1433-8092 | Imprint