Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with self-reducibility:
TR08-038 | 4th April 2008
Eric Allender, Michal Koucky

Amplifying Lower Bounds by Means of Self-Reducibility

Revisions: 2

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>>

TR13-047 | 27th March 2013
Christian Gla├čer, Dung Nguyen, Christian Reitwie├čner, Alan Selman, Maximilian Witek

Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

Comments: 1

We investigate the autoreducibility and mitoticity of complete sets for several classes with respect to different polynomial-time and logarithmic-space reducibility notions.

Previous work in this area focused on polynomial-time reducibility notions. Here we obtain new mitoticity and autoreducibility results for the classes EXP and NEXP with respect to some restricted ... more >>>

TR21-170 | 25th November 2021
Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda

Pseudorandom Self-Reductions for NP-Complete Problems

A language $L$ is random-self-reducible if deciding membership in $L$ can be reduced (in polynomial time) to deciding membership in $L$ for uniformly random instances. It is known that several "number theoretic" languages (such as computing the permanent of a matrix) admit random self-reductions. Feigenbaum and Fortnow showed that NP-complete ... more >>>

ISSN 1433-8092 | Imprint