Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Randomized reductions:
TR95-021 | 20th April 1995
Marek Karpinski, Rutger Verbeek

On Randomized Versus Deterministic Computation

In contrast to deterministic or nondeterministic computation, it is
a fundamental open problem in randomized computation how to separate
different randomized time classes (at this point we do not even know
how to separate linear randomized time from ${\mathcal O}(n^{\log n})$
randomized time) or how to ... more >>>

TR95-049 | 19th October 1995
Anna Gal, Avi Wigderson

Boolean complexity classes vs. their arithmetic analogs

This paper provides logspace and small circuit depth analogs
of the result of Valiant-Vazirani, which is a randomized (or
nonuniform) reduction from NP to its arithmetic analog ParityP.
We show a similar randomized reduction between the
Boolean classes NL and semi-unbounded fan-in Boolean circuits and
their arithmetic counterparts. These ... more >>>

TR02-050 | 5th August 2002
Oded Goldreich, Madhu Sudan

Locally Testable Codes and PCPs of Almost-Linear Length

Locally testable codes are error-correcting codes that admit
very efficient codeword tests. Specifically, using a constant
number of (random) queries, non-codewords are rejected with
probability proportional to their distance from the code.

Locally testable codes are believed to be the combinatorial
core of PCPs. However, the relation is ... more >>>

TR09-139 | 17th December 2009
Mohammad Mahmoody, David Xiao

On the Power of Randomized Reductions and the Checkability of SAT

Revisions: 3

The closure of complexity classes is a elicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions ... more >>>

TR12-020 | 3rd March 2012
Daniele Micciancio

Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

Revisions: 1

We prove that the Shortest Vector Problem (SVP) on point lattices is NP-hard to approximate for any constant factor under polynomial time reverse unfaithful random reductions. These are probabilistic reductions with one-sided error that produce false negatives with small probability, but are guaranteed not to produce false positives regardless of ... more >>>

TR15-198 | 30th November 2015
Shuichi Hirahara, Osamu Watanabe

Limits of Minimum Circuit Size Problem as Oracle

Revisions: 1

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP $\neq$ EXP, which is a ... more >>>

TR22-074 | 20th May 2022
Michael Saks, Rahul Santhanam

On Randomized Reductions to the Random Strings

We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants.

As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language $L$ that has a randomized ... more >>>

ISSN 1433-8092 | Imprint