Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with hardness-randomness tradeoffs:
TR02-008 | 11th January 2002
Valentine Kabanets

Derandomization: A Brief Overview

This survey focuses on the recent (after 1998) developments in
the area of derandomization, with the emphasis on the derandomization of
time-bounded randomized complexity classes.

more >>>

TR15-071 | 23rd April 2015
Mrinal Kumar, Shubhangi Saraf

Sums of products of polynomials in few variables : lower bounds and polynomial identity testing

We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form $$P = \sum_{i = 1}^T \prod_{j = 1}^d Q_{ij}$$
such that each $Q_{ij}$ is an arbitrary polynomial that depends on at most $s$ variables.

... more >>>

ISSN 1433-8092 | Imprint