Under the auspices of the Computational Complexity Foundation (CCF)

LATEST > REPORTS:
Next

TR22-073 | 18th May 2022
Itay Kalev, Amnon Ta-Shma

#### Unbalanced Expanders from Multiplicity Codes

In 2007 Guruswami, Umans and Vadhan gave an explicit construction of a lossless condenser based on Parvaresh-Vardy codes. This lossless condenser is a basic building block in many constructions, and, in particular, is behind the state of the art extractor constructions.

We give an alternative construction that is based on ... more >>>

TR22-072 | 15th May 2022
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

#### Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

Understanding the relationship between the worst-case and average-case complexities of $\mathrm{NP}$ and of other subclasses of $\mathrm{PH}$ is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the ... more >>>

TR22-071 | 13th May 2022
We establish an $\epsilon$-sensitive hierarchy separation for monotone arithmetic computations. The notion of $\epsilon$-sensitive monotone lower bounds was recently introduced by Hrubes [Computational Complexity'20]. We show the following:
(1) There exists a monotone polynomial over $n$ variables in VNP that cannot be computed by $2^{o(n)}$ size monotone ... more >>>