Tagged Questions

The tag has no usage guidance.

84 views

Lower bound on the element distinctness problem

The element distinctness problem asks whether any two elements of the input sequence $<x_1,\ldots,x_n>$ are equal? This problem has a lower bound of $\Omega(n \log n)$ in the algebraic decision ...
45 views

Randomized and deterministic query complexity of symmetric functions

The deterministic query complexity $D(f)$ of a symmetric function $f$ is $\Omega(n)$ (except for f = 0 or f = 1). I am wondering if the same result holds for the (bounded-error) randomized query ...
92 views

Minmax vs Maxmin

I'm reading this paper about building a combat simulator for 8 unit vs 8 unit mini combats in StarCraft: Brood War. The basic idea is to build a search tree simulating these small combats in order to ...
102 views

decision tree complexity and query complexity

I want good sources for starting with decision tree complexity and query complexity , what papers to start with ? what book chapters to read ? I already seen arora and barak book and I begin to read ...
156 views

The Complexity of Properly Learning Decision Trees

Where does this paper prove the middle bullet point of its abstract? I have looked through that paper fairly thoroughly. There are three things I want to read how they're getting around. ...
353 views

Canonical representation of Binary Decision Tree in Ptime?

I am wondering whether there may exist a way to give a sort of "normal form" for binary decision trees (BDT) in a tractable way. More precisely: a BDT is a tree with internal nodes labelled by ...
144 views

Lower bound for finding repeated elements in sorted array

This is inspired by [1] (which still needs answers). What is the tight lower bound (or optimal algorithms) for the "finding repeated elements" problem: Given a sorted integer array of size $n$, ...
240 views

What is the complexity of the equivalence problem for read-once decision trees?

A read-once decision tree is defined as follows: $True$ and $False$ are read-once decision trees. If $A$ and $B$ are read-once decision trees and $x$ is a variable not occurring in $A$ and $B$, ...