Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

RSS-FeedNext 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 next

ISSN 1433-8092 | Imprint