Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR24-049 | 7th March 2024
Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

Oblivious Classes Revisited: Lower Bounds and Hierarchies

In this work we study oblivious complexity classes. Among our results:
1) For each $k \in \mathbb{N}$, we construct an explicit language $L_k \in O_2P$ that cannot be computed by circuits of size $n^k$.
2) We prove a hierarchy theorem for $O_2TIME$. In particular, for any function $t:\mathbb{N} \rightarrow \mathbb{N}$ ... more >>>


TR24-048 | 4th March 2024
Kuan Cheng, Yichuan Wang

$BPL\subseteq L-AC^1$

Whether $BPL=L$ (which is conjectured to be equal), or even whether $BPL\subseteq NL$, is a big open problem in theoretical computer science. It is well known that $L-NC^1\subseteq L\subseteq NL\subseteq L-AC^1$. In this work we will show that $BPL\subseteq L-AC^1$, which was not known before. Our proof is based on ... more >>>


TR24-047 | 8th March 2024
Oded Goldreich

On the query complexity of testing local graph properties in the bounded-degree graph model

Revisions: 1

We consider the query complexity of testing local graph properties in the bounded-degree graph model.
A local property is defined in terms of forbidden subgraphs that are augmented by degree information, where the latter account also for neighbors that are not in the subgraph.
Indeed, this formulation yields a generalized ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint