30 votes
Accepted

Oracle Construction for Grover's Algorithm

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to. For example, suppose you have a 3-sat problem: ...
Craig Gidney's user avatar
  • 1,518
28 votes
Accepted

Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

These problems are polynomially equivalent. Indeed, suppose that you have an algorithm that can decide whether two graphs are isomorphic or not, and it claims that they are. Attach a clique of size $n+...
domotorp's user avatar
  • 13.8k
17 votes

Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

More specific to Babai's algorithm: yes, the algorithm not only finds an isomorphism, it finds generators of the automorphism group (and therefore effectively finds all isomorphisms) as part of the ...
Joshua Grochow's user avatar
9 votes

How to efficiently find a loop between two nodes in a directed graph?

This problem has been shown to be NP-complete in the following paper: S. Fortune, J. Hopcroft, J. Wyllie: "The directed subgraph homeomorphism problem" Theoretical Computer Science 10 (1980), ...
Gamow's user avatar
  • 5,772
8 votes
Accepted

Find a string with minimal edit distance from a set of given strings

Your problem is called the Median string problem. Nicolas and Rivals proved that the Median String problem (under the Levenshtein distance) is NP-complete even for binary strings.
Mohammad Al-Turkistany's user avatar
7 votes
Accepted

Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?

I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (...
Sasho Nikolov's user avatar
4 votes
Accepted

Does PPAD really capture the notion of finding another unbalanced vertex?

The problems have been proved to be equivalent (and thus PPAD-complete), see Section 8 in The Hairy Ball Problem is PPAD-Complete by Paul W. Goldberg and Alexandros Hollender.
domotorp's user avatar
  • 13.8k
4 votes

Does PPAD really capture the notion of finding another unbalanced vertex?

This is an interesting question, and I can only give a partial answer. It is easy to see that the construction on p. 505 of Papadimitriou’s paper shows the equivalence of AUV with its special case ...
Emil Jeřábek's user avatar
4 votes
Accepted

Approximation Ratio of Local search for $k-$center problem

Local search (with a single swap) doesn't give you a good approximation factor in the worst case for $k$-center, as illustrated by the following example. Take a simplex in $\mathbb{R}^{k-1}$, and put ...
Neal Young's user avatar
3 votes
Accepted

Is Levin's Universal Search valid for the integer factorization problem while using the AKS test?

In a practical sense, Levin search is not useful. It has an enormous constant factor (exponential in the length/size of the optimal factoring algorithm). This makes it of little use in practice. In ...
D.W.'s user avatar
  • 12k
3 votes
Accepted

Literature reference for search-BPP

I’m not sure about the exact definition as given. However, the kind of search problems that has been studied the most in the literature are NP-search problems. In this context, there is no meaningful ...
Emil Jeřábek's user avatar
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 ...
Klaus Draeger's user avatar
2 votes

Is any computational problem a search problem?

The linked PDF, "Handout 2 for Stanford University — CS254: Computational Complexity", defines four types of "computational problems": Decision problems Search problems Optimization problems ...
Nat's user avatar
  • 123
2 votes

How to find a non-zero point of a non-zero polynomial of low degree?

This does not directly answer your question, but if $f$ is $n$-variate, and is known to have partial degrees at most $D$ and at most $T$ terms, and $\mathbb{F}$ is known to contain an element $\omega$ ...
user41530's user avatar
2 votes
Accepted

Biased binary search?

Change the binary search procedure to pick a weighted midpoint at each time step: 1. Input: Search key K, sorted array A, probability distribution P. ...
Thomas's user avatar
  • 2,803
1 vote

Find an approximate argmax using only approximate max queries

Extended comment of an idea or two toward a lower bound. Let $B = \Theta(\log n)$, say (though the best choice may be different), and let $\{v_1,\dots,v_n\} = \{\frac{1}{n}B, \dots, \frac{n-1}{n}B, B\}...
usul's user avatar
  • 7,615
1 vote

What is the largest distance that still guarantees a linear time distance search?

There's a straightforward algorithm for your original problem, based on a linear scan through the array with two pointers, one to $a$ and the other to the largest $b$ such that $|a-b|<c$. The ...
D.W.'s user avatar
  • 12k
1 vote

Oracle Construction for Grover's Algorithm

You can also get a solution which uses only one ancillary qubit (but relies on NOT gates with multiple controls), by getting your input to algebraic normal form (e.g. with Mathematicas ...
Daniel Hauck's user avatar
1 vote

Binary Search with Errors

A good old trick is that it's sufficient to give an algorithm that achieves this with $O(\log n)$ expected number of coin flips and $99\%$ probability, as if we are exceeding the expected running time ...
domotorp's user avatar
  • 13.8k

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