22 votes
Accepted

The randomized query complexity of the conjoined trees problem

I think I have a deterministic algorithm that finds the exit in $O(n2^{n/2})$ oracle calls. First, find the labels for all the vertices of distance $n/2$ from the entrance. This takes $O(2^{n/2})$ ...
user avatar
  • 236
17 votes

Easy problems with hard counting versions

A very nice and simple example from Graph Theory is counting the number of Eularian circuits in an undirected graph. The decision version is easy (... and the Seven Bridges of Königsberg problem has ...
user avatar
17 votes

Easy problems with hard counting versions

One interesting example from number theory is expressing a positive integer as a sum of four squares. This can be done relatively easily in random polynomial time (see my 1986 article with Rabin at ...
user avatar
9 votes
Accepted

Easy problems with hard counting versions

Here's a truly excellent example (I may be biased). Given a partially ordered set: a) does it have a linear extension (i.e., a total order compatible with the partial order)? Trivial: All posets ...
user avatar
9 votes

Canonical representation of Binary Decision Tree in Ptime?

I think that assuming that $\mathsf{NP} \not \subseteq \mathsf{SUBEXP}$, such a canonical representation does not exist. Proof: Suppose such a canonical representation does exist. Then the function $A ...
user avatar
  • 1,733
7 votes
Accepted

Las Vegas vs Monte Carlo randomized decision tree complexity

This question has been resolved! A few days ago Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs uploaded a preprint showing the existence of a total ...
user avatar
6 votes

Lower bound on the element distinctness problem

This was also done, independently, by Lubiw and Racz in 1991. See http://www.sciencedirect.com/science/article/pii/089054019190034Y .
user avatar
6 votes
Accepted

Lower bound on the element distinctness problem

Such a lower bound for integer inputs is indeed known, and is not just a trivial consequence of the result for the reals: A. C.-C. Yao, Lower Bounds for Algebraic Computation Trees of Functions ...
user avatar
6 votes

Easy problems with hard counting versions

Concerning your second question, problems such as Monotone-2-SAT (deciding of the satisfiability of a CNF-formula having at most 2 positive literals by clause) is completely trivial (you just have to ...
user avatar
  • 1,855
5 votes
Accepted

Complexity of constructing minimum depth decision trees

I think I can see a fairly easy reduction from 3DM. Let $B=\{0^J\}$, i.e., it is a singleton set with the only zero element. The points of $A$ correspond to the points of the 3DM that are to be ...
user avatar
  • 13.5k
5 votes

Easy problems with hard counting versions

From [Kayal, CCC 2009]: Explicitly evaluating annihilating polynomials at some point From the abstract: ``This is the only natural computational problem where determining the existence of an object (...
user avatar
  • 5,973
5 votes
Accepted

What is the complexity of decision tree complexity?

If you have an oracle for $f$, you can compute the optimal decision tree for $f$ in $O(3^nn)$ time and $O(3^n)$ space. Consider a function $g$ that takes as input a partition of the variables into ...
user avatar
  • 3,236
5 votes
Accepted

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

I found a partial solution. The problem is in L. The negation of $A \leftrightarrow B$ is equivalent to $(\bar A \land B) \lor (A \land \bar{B})$ which is equivalent to $False$ iff both $(\bar A \...
user avatar
  • 676
3 votes
Accepted

Minmax vs Maxmin

First of all, there is a lot of information in this related question: Max Min of function less than Min max of function. That said, the source of your problem is a confusion about which choices are ...
user avatar
3 votes

decision tree complexity and query complexity

Chapters-3,4 in book Analysis of Boolean Functions by Ryan O'Donnell might be a good starting point.
user avatar
  • 1,984
2 votes
Accepted

Binary Trees for Nearest Neighbor Search

This essentially can be derived from a compressed quadtree representing approximate Voronoi diagrams. If you want the decision tree to be balanced you have to use a finger tree on the compressed ...
user avatar
2 votes
Accepted

Finding the maximum no. of people who get along in a group

Convert your array to a zero-one array where $a_{ij}=1$ if persons $i,j$ get along, else it is zero. Let this be the adjacency matrix of an undirected graph $G$ where the vertices are the persons in ...
user avatar
  • 1,996
2 votes
Accepted

Lower bound for finding repeated elements in sorted array

Any algorithm would need $\Omega(\log n)$ queries. To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. ...
user avatar
  • 9,378
2 votes

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

From a ITE formula $\phi$, you can compute polynomially a reduced assignment list to describe all valuations which makes it true. To do that, just look at your formula as a tree with nodes labeled by ...
user avatar
  • 7,672
1 vote
Accepted

Randomized and deterministic query complexity of symmetric functions

Ok, I found the answer in this survey: http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf The sensitivity $s(f)$ of a (nonconstant) symmetric function $f$ is $s(f) \geq \lceil\frac{n+1}{2}\rceil$. ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible