Under the auspices of the Computational Complexity Foundation (CCF)

LATEST > REPORTS:
Next

TR22-136 | 21st September 2022
Sepehr Assadi, Gillat Kol, Zhijun Zhang

#### Rounds vs Communication Tradeoffs for Maximal Independent Sets

We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex -- this way, each edge is known by both ... more >>>

TR22-135 | 18th September 2022
Rahul Chugh, Supartha Poddar, Swagato Sanyal

#### Decision Tree Complexity versus Block Sensitivity and Degree

Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It ... more >>>

TR22-134 | 23rd September 2022
Greg McLellan, Alexey Milovanov

#### Some Games on Turing Machines and Power from Random Strings

Denote by $R$ the set of strings with high Kolmogorov complexity. In [E. Allender, H. Buhrman, M. Kouck\'y, D. van Melkebeek, and D. Ronneburger.
Power from random strings.
\emph{SIAM Journal on Computing}, 35:1467--1493, 2006.] the idea of using $R$ as an oracle for resource-bounded computation models was presented. This idea ... more >>>

Next

ISSN 1433-8092 | Imprint