Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SEARCH PROBLEMS:
Reports tagged with search problems:
TR10-128 | 15th August 2010
Scott Aaronson

#### The Equivalence of Sampling and Searching

Revisions: 1

In a sampling problem, we are given an input $x\in\left\{0,1\right\} ^{n}$, and asked to sample approximately from a probability
distribution $D_{x}$ over poly(n)-bit strings. In a search problem, we are given an input
$x\in\left\{ 0,1\right\} ^{n}$, and asked to find a member of a nonempty set
$A_{x}$ with high probability. ... more >>>

TR12-100 | 23rd July 2012
Tomas Jirotka

#### NP Search Problems

The thesis summarizes known results in the field of NP search problems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems.

more >>>

TR12-101 | 10th August 2012
Oded Goldreich, Shafi Goldwasser, Dana Ron

#### On the possibilities and limitations of pseudodeterministic algorithms

We study the possibilities and limitations
of pseudodeterministic algorithms,
a notion put forward by Gat and Goldwasser (2011).
These are probabilistic algorithms that solve search problems
such that on each input, with high probability, they output
the same solution, which may be thought of as a canonical solution.
We consider ... more >>>

TR17-015 | 4th February 2017
Ilan Komargodski, Moni Naor, Eylon Yogev

#### White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

Revisions: 1

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so ... more >>>

TR19-012 | 27th January 2019
Oded Goldreich

#### Multi-pseudodeterministic algorithms

In this work, dedicated to Shafi Goldwasser, we consider a relaxation of the notion of pseudodeterministic algorithms, which was put forward by Gat and Goldwasser ({\em ECCC}, TR11--136, 2011).

Pseudodeterministic algorithms are randomized algorithms that solve search problems by almost always providing the same canonical solution (per each input). ... more >>>

ISSN 1433-8092 | Imprint