Under the auspices of the Computational Complexity Foundation (CCF)

LATEST > REPORTS:
Next

TR23-040 | 28th March 2023
Edward Pyne, Ran Raz, Wei Zhan

Certified Hardness vs. Randomness for Log-Space

Let $\mathcal{L}$ be a language that can be decided in linear space and let $\epsilon >0$ be any constant. Let $\mathcal{A}$ be the exponential hardness assumption that for every $n$, membership in $\mathcal{L}$ for inputs of length~$n$ cannot be decided by circuits of size smaller than $2^{\epsilon n}$.
We ... more >>>

TR23-039 | 28th March 2023

Query Complexity of Search Problems

We relate various complexity measures like sensitivity, block sensitivity, certificate complexity for multi-output functions to the query complexities of such functions. Using these relations, we improve upon the known relationship between pseudo-deterministic query complexity and deterministic query complexity for total search problems: We show that pseudo-deterministic query complexity is at ... more >>>

TR23-038 | 28th March 2023
Rahul Ilango, Jiatu Li, Ryan Williams

Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit $C:\{0,1\}^n\to\{0,1\}^m$, where $m>n$. Although at least half of the strings of length $m$ are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS'21) ... more >>>

Next

ISSN 1433-8092 | Imprint