Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with hierarchy theorems:
TR17-176 | 15th November 2017
Kamil Khadiev, Aliya Khadiev, Alexander Knop

Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies

In this paper, we study quantum OBDD model, it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present ... more >>>

TR18-098 | 17th May 2018
Oded Goldreich

Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity

Revisions: 1

Focusing on property testing tasks that have query complexity that is independent of the size of the tested object (i.e., depends on the proximity parameter only), we prove the existence of a rich hierarchy of the corresponding complexity classes.
That is, for essentially any function $q:(0,1]\to\N$, we prove the existence ... more >>>

TR21-039 | 15th March 2021
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam

Pseudodeterministic Algorithms and the Structure of Probabilistic Time

We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of $BPTIME$: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows.

1. A new pseudorandom generator and its consequences: We build on techniques developed to ... more >>>

TR21-043 | 15th March 2021
Peter Dixon, A. Pavan, N. V. Vinodchandran

Promise Problems Meet Pseudodeterminism

The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high ... more >>>

ISSN 1433-8092 | Imprint