Showing cs.CCShow all
2 papers · 1 filter
cs.CC2009
Measuring communication complexity using instance complexity with oracles
Armando Matos, Andreia Teixeira, Andre Souto
We establish a connection between non-deterministic communication complexity and instance complexity, a measure of information based on algorithmic entropy. Let , $\o…
cs.CC2008
Depth as Randomness Deficiency
Luis Antunes, Armando Matos, Andre Souto +1
Depth of an object concerns a tradeoff between computation time and excess of program length over the shortest program length required to obtain the object. It gives an uncondition…