Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with algebrization:
TR16-040 | 16th March 2016
Baris Aydinlioglu, Eric Bach

Affine Relativization: Unifying the Algebrization and Relativization Barriers

Revisions: 3

We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure ... more >>>

ISSN 1433-8092 | Imprint