Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DECISION TREE:
Reports tagged with Decision Tree:
TR02-019 | 20th March 2002
Nader Bshouty, Lynn Burroughs

On the proper learning of axis parallel concepts

We study the proper learnability of axis parallel concept classes
in the PAC learning model and in the exact learning model with
membership and equivalence queries. These classes include union of boxes,
DNF, decision trees and multivariate polynomials.

For the {\it constant} dimensional axis parallel concepts $C$
we ... more >>>


TR02-054 | 5th September 2002
Detlef Sieling

Minimization of Decision Trees is Hard to Approximate

Decision trees are representations of discrete functions with widespread applications in, e.g., complexity theory and data mining and exploration. In these areas it is important to obtain decision trees of small size. The minimization problem for decision trees is known to be NP-hard. In this paper the problem is shown ... more >>>


TR12-163 | 24th November 2012
Avishay Tal

Properties and Applications of Boolean Function Composition

For Boolean functions $f:\{0,1\}^n \to \{0,1\}$ and $g:\{0,1\}^m \to \{0,1\}$, the function composition of $f$ and $g$ denoted by $f\circ g : \{0,1\}^{nm} \to \{0,1\}$ is the value of $f$ on $n$ inputs, each of them is the calculation of $g$ on a distinct set of $m$ Boolean variables. Motivated ... more >>>


TR13-149 | 28th October 2013
Albert Atserias, Neil Thapen

The Ordering Principle in a Fragment of Approximate Counting

The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over $\mathrm{T}^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk ... more >>>


TR16-062 | 18th April 2016
Avishay Tal

On The Sensitivity Conjecture

The sensitivity of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ is the maximal number of neighbors a point in the Boolean hypercube has with different $f$-value. Roughly speaking, the block sensitivity allows to flip a set of bits (called a block) rather than just one bit, in order to change the ... more >>>


TR17-107 | 1st June 2017
Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

A Composition Theorem for Randomized Query complexity

Revisions: 1

Let the randomized query complexity of a relation for error probability $\epsilon$ be denoted by $\R_\epsilon(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $\R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. ... more >>>


TR22-001 | 28th December 2021
Yogesh Dahiya, Meena Mahajan

On (Simple) Decision Tree Rank

Revisions: 1

In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-studied one, and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure ... more >>>


TR22-135 | 18th September 2022
Rahul Chugh, Supartha Poddar, Swagato Sanyal

Decision Tree Complexity versus Block Sensitivity and Degree

Comments: 1

Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It ... more >>>


TR23-008 | 2nd February 2023
Ond?ej Ježil

Limits of structures and Total NP Search Problems

For a class of finite graphs, we define a limit object relative to some computationally restricted class of functions. The properties of the limit object then reflect how a computationally restricted viewer "sees" a generic instance from the class. The construction uses Krají?ek's forcing with random variables [7]. We prove ... more >>>


TR23-012 | 16th February 2023
Yogesh Dahiya, Vignesh K, Meena Mahajan, Karteek Sreenivasaiah

Linear threshold functions in decision lists, decision trees, and depth-2 circuits

We show that polynomial-size constant-rank linear decision trees (LDTs) can be converted to polynomial-size depth-2 threshold circuits LTF$\circ$LTF. An intermediate construct is polynomial-size decision lists that query a conjunction of a constant number of linear threshold functions (LTFs); we show that these are equivalent to polynomial-size exact linear decision lists ... more >>>


TR23-157 | 31st October 2023
Vladimir Podolskii, Dmitrii Sluch

One-Way Communication Complexity of Partial XOR Functions

Boolean function $F(x,y)$ for $x,y \in \{0,1\}^n$ is an XOR function if $F(x,y) = f(x\oplus y)$ for some function $f$ on $n$ input bits, where $\oplus$ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing Fourier analytic technique. For total XOR functions it is known ... more >>>


TR24-034 | 19th February 2024
Bruno Loff, Alexey Milovanov

The hardness of decision tree complexity

Let $f$ be a Boolean function given as either a truth table or a circuit. How difficult is it to find the decision tree complexity, also known as deterministic query complexity, of $f$ in both cases? We prove that this problem is $NC$-hard and PSPACE-hard, respectively. The second bound is ... more >>>




ISSN 1433-8092 | Imprint