Next

__
TR22-136
| 21st September 2022
__

Sepehr Assadi, Gillat Kol, Zhijun Zhang#### Rounds vs Communication Tradeoffs for Maximal Independent Sets

__
TR22-135
| 18th September 2022
__

Rahul Chugh, Supartha Poddar, Swagato Sanyal#### Decision Tree Complexity versus Block Sensitivity and Degree

__
TR22-134
| 23rd September 2022
__

Greg McLellan, Alexey Milovanov#### Some Games on Turing Machines and Power from Random Strings

Next

Sepehr Assadi, Gillat Kol, Zhijun Zhang

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 >>>

Rahul Chugh, Supartha Poddar, Swagato Sanyal

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 >>>

Greg McLellan, Alexey Milovanov

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