# Tag Info

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})$ ...
• 236

### 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 ...
• 22.3k

### 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 ...
• 6,898
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 ...
• 342

• 676
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 ...
• 2,470

### 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.
• 1,984
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 ...
• 9,566
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 ...
• 1,996
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$. ...
• 9,378

### 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 ...
• 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$. ...
• 293

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