Under the auspices of the Computational Complexity Foundation (CCF)

LATEST > REPORTS:
PreviousNext

TR21-135 | 6th September 2021
Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl

#### Strong (D)QBF Dependency Schemes via Implication-free Resolution Paths

We suggest a general framework to study dependency schemes for dependency quantified Boolean formulas (DQBF). As our main contribution, we exhibit a new infinite collection of implication-free DQBF dependency schemes that generalise the reflexive resolution path dependency scheme. We establish soundness of all these schemes, implying that they can be ... more >>>

TR21-134 | 19th August 2021

#### A refinement of the Meyer-McCreight Union Theorem

For a function $t : 2^\star \to 1^\star$, let $C_t$ be the set of problems decidable on input $x$ in time at most $t(x)$ almost everywhere. The Union Theorem of Meyer and McCreight asserts that any union $\bigcup_{i < \omega} C_{t_i}$ for a uniformly recursive sequence of bounds $t_i$ is ... more >>>

TR21-133 | 12th September 2021
Oded Goldreich, Dana Ron

#### Testing Distributions of Huge Objects

Revisions: 1

We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings.
Specifically, the new model refers to testing properties of distributions, but these are distributions over huge objects (i.e., very long strings).
Accordingly, the ... more >>>

PreviousNext

ISSN 1433-8092 | Imprint