Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with search-to-decision reductions:
TR12-002 | 4th January 2012
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe

Query Complexity and Error Tolerance of Witness Finding Algorithms

Revisions: 3

We propose an abstract framework for studying search-to-decision reductions for NP. Specifically, we study the following witness finding problem: for a hidden nonempty set $W\subseteq\{0,1\}^n$, the goal is to output a witness in $W$ with constant probability by making randomized queries of the form ``is $Q\cap W$ nonempty?''\ where $Q\subseteq\{0,1\}^n$. ... more >>>

TR21-041 | 15th March 2021
Zhenjian Lu, Igor Carboni Oliveira

An Efficient Coding Theorem via Probabilistic Representations and its Applications

A probabilistic representation of a string $x \in \{0,1\}^n$ is given by the code of a randomized algorithm that outputs $x$ with high probability [Oliveira, ICALP 2019]. We employ probabilistic representations to establish the first unconditional Coding Theorem in time-bounded Kolmogorov complexity. More precisely, we show that if a distribution ... more >>>

ISSN 1433-8092 | Imprint