More than 30 years ago, Karp conjectured that all nontrivial monotone graph properties are
evasive, ie, have decision tree complexity n2, where n is the number of vertices. It was …

Many graph properties (eg, connectedness, containing a complete subgraph) are known to
be difficult to check. In a decision-tree model, the cost of an algorithm is measured by the …

A function f:{0, 1} n->{0, 1} is called evasive if its decision tree complexity is maximal, ie, D
(f)= n. The long-standing Anderaa-Rosenberg-Karp (ARK) Conjecture asserts that every non …

In this article, we investigate the sensitivity complexity of hypergraph properties. We present
ak-uniform hypergraph property with sensitivity complexity O (n (⌈ k/3⌉) for any k≥ 3, where …

The query complexity of graph properties is well-studied when queries are on edges. We
investigate the same when queries are on nodes. In this setting a graph $ G=(V, E) $ on $ n …

For a Boolean function f, let D (f) denote its deterministic decision tree complexity, ie,
minimum number of (adaptive) queries required in worst case in order to determine f. In a …

A boolean function in n variables is weakly evasive if its decision-tree complexity is Ω (n). By
k-graphs we mean k-uniform hypergraphs. A k-graph property} on v vertices is a boolean …

A graph property is said to be elusive (or evasive) if every algorithm testing this property by
asking questions of the form “is there an edge between vertices xx and yy?” requires, in the …

A Boolean function in n variables is weakly evasive if its decision-tree complexity is Ω (n). By
k-graphs, we mean k-uniform hypergraphs. A k-graph property on v vertices is a Boolean …

The decision tree model, aka the query model, perhaps due to its simplicity and fundamental
nature has been extensively studied over decades. Yet there remain some fascinating open …